Меню Главная Случайная статья Настройки Числа Эйлера I рода Материал из https://ru.wikipedia.org В комбинаторике числом Эйлера I рода из n по k, обозначаемым ${\displaystyle \left\langle {n \atop k}\right\rangle }$ или ${\displaystyle E(n,k)}$, называется количество перестановок порядка n с k подъёмами, то есть таких перестановок ${\displaystyle \pi =(\pi _{1},\pi _{2},\dots ,\pi _{n})}$, что существует ровно k индексов j, для которых ${\displaystyle \pi _{j}<\pi _{j+1}}$. Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число ${\displaystyle {\frac {1}{n!}}\left\langle {n \atop k}\right\rangle }$ выражает: объём части n-мерного гиперкуба, ограниченного гиперплоскостями ${\displaystyle x_{1}+x_{2}+\dots +x_{n}=k}$ и ${\displaystyle x_{1}+x_{2}+\dots +x_{n}=k-1}$; вероятность того, что сумма n независимых равномерно распределённых в отрезке ${\displaystyle [0,1]}$ переменных лежит между k-1 и k. Содержание 1 Пример 2 Свойства 2.1 Треугольник чисел Эйлера первого рода 2.2 Рекуррентная формула 2.3 Явные формулы 2.4 Формулы суммирования 2.5 Производящая функция 2.6 Тождество Ворпицкого 3 Литература Пример Перестановки ${\displaystyle \pi }$ четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств: ${\displaystyle \pi _{1}<\pi _{2}>\pi _{3}<\pi _{4}}$, ${\displaystyle \pi _{1}<\pi _{2}<\pi _{3}>\pi _{4}}$ или ${\displaystyle \pi _{1}>\pi _{2}<\pi _{3}<\pi _{4}}$. Таких перестановок ровно 11: 1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123. Поэтому ${\displaystyle \left\langle {4 \atop 2}\right\rangle =11}$. Свойства Для заданного натурального числа ${\displaystyle n}$ существует единственная перестановка без подъёмов, то есть ${\displaystyle (n,n-1,n-2,\dots ,1)}$. Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть ${\displaystyle (1,2,3,\dots ,n-1,n)}$. Таким образом, ${\displaystyle \left\langle {n \atop 0}\right\rangle =\left\langle {n \atop n-1}\right\rangle =1}$ для всех натуральных ${\displaystyle n}$. Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом, ${\displaystyle \left\langle {n \atop m}\right\rangle =\left\langle {n \atop n-m-1}\right\rangle .}$ Треугольник чисел Эйлера первого рода Значение чисел Эйлера ${\displaystyle \left\langle {n \atop k}\right\rangle }$ для малых значений n и k приведены в следующей таблице (последовательность A008292 в OEIS): n\k 0 1 2 3 4 5 6 7 8 9 0 1 1 1 0 2 1 1 0 3 1 4 1 0 4 1 11 11 1 0 5 1 26 66 26 1 0 6 1 57 302 302 57 1 0 7 1 120 1191 2416 1191 120 1 0 8 1 247 4293 15619 15619 4293 247 1 0 9 1 502 14608 88234 156190 88234 14608 502 1 0 Легко понять, что значения на главной диагонали матрицы задаются формулой: ${\displaystyle \left\langle {n \atop n}\right\rangle =[n=0].}$ Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен: ${\displaystyle \left\langle {n \atop k}\right\rangle =\left\langle {n \atop n-1-k}\right\rangle }$ при n > 0. То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов. Рекуррентная формула Каждая перестановка ${\displaystyle \rho =\rho _{1}\dots \rho _{n-1}}$ из набора ${\displaystyle \{1,2,3,n-1\}}$ приводит к ${\displaystyle n}$ перестановкам из ${\displaystyle \{1,2,3,n\}}$, если мы вставляем новый элемент n всеми возможными способами. Вставляя ${\displaystyle n}$ в ${\displaystyle j}$-ю позицию, получаем перестановку ${\displaystyle \pi =\rho _{1}\dots \rho _{j-1}n\rho _{j}\dots \rho _{n-1}}$. Количество подъёмов в ${\displaystyle \pi }$ равняется количеству подъёмов в ${\displaystyle \rho }$, если ${\displaystyle j=1}$ или если ${\displaystyle \pi _{j-1}<\pi _{j}}$; и оно больше количества подъёмов в ${\displaystyle \rho }$, если ${\displaystyle j=n}$ или если ${\displaystyle \rho _{j-1}>\rho _{j}}$. Следовательно, ${\displaystyle \pi }$ в сумме имеет ${\displaystyle (k+1)\left\langle {n-1 \atop k}\right\rangle }$ способов построения перестановок из ${\displaystyle \rho }$, которые имеют ${\displaystyle k}$ подъёмов, плюс ${\displaystyle ((n-2)-(k-1)+1)\left\langle {n-1 \atop k-1}\right\rangle }$ способов построения перестановок из ${\displaystyle \rho }$, которые имеют ${\displaystyle k-1}$ подъёмов. Тогда искомая рекуррентная формула для целых ${\displaystyle n>0}$ имеет вид: ${\displaystyle \left\langle {n \atop k}\right\rangle =(k+1)\left\langle {n-1 \atop k}\right\rangle +(n-k)\left\langle {n-1 \atop k-1}\right\rangle .}$ Положим также, что ${\displaystyle \left\langle {0 \atop k}\right\rangle =[k=0]}$ (для целых ${\displaystyle k}$), и при ${\displaystyle k<0}$: ${\displaystyle \left\langle {n \atop k}\right\rangle =0.}$ Явные формулы Явная формула для чисел Эйлера I рода: ${\displaystyle \left\langle {n \atop m}\right\rangle =\sum _{k=0}^{m}{n+1 \choose k}(m+1-k)^{n}(-1)^{k}}$ позволяет получить относительно простые выражения при малых значениях m: ${\displaystyle \left\langle {n \atop 0}\right\rangle =1;}$ ${\displaystyle \left\langle {n \atop 1}\right\rangle =2^{n}-n-1;}$ ${\displaystyle \left\langle {n \atop 2}\right\rangle =3^{n}-(n+1)2^{n}+{n+1 \choose 2}.}$ Формулы суммирования Из комбинаторного определения очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке, равна ${\displaystyle n!}$, так как она равна количеству всех перестановок порядка ${\displaystyle n}$: ${\displaystyle \sum _{m=0}^{n}\left\langle {n \atop m}\right\rangle =n!}$ Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли ${\displaystyle B_{n+1}}$: ${\displaystyle \sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle ={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}},}$ ${\displaystyle \sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n \choose m}^{-1}=(n+1)B_{n},}$ ${\displaystyle \sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n-1 \choose m}^{-1}=0.}$ Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода: ${\displaystyle \sum _{k=n-m}^{n}\left\langle {n \atop k}\right\rangle {k \choose n-m}=m!\left\{{n \atop m}\right\}}$ ${\displaystyle \sum _{k=0}^{n}2^{k}\left\langle {n \atop k}\right\rangle =\sum _{k=1}^{\infty }{\frac {k^{n}}{2^{k}}}=\sum _{k=1}^{n}k!\left\{{n \atop k}\right\}}$ ${\displaystyle \sum _{k=0}^{n}3^{k}\left\langle {n \atop k}\right\rangle =2^{n+1}\sum _{k=1}^{\infty }{\frac {k^{n}}{3^{k}}}}$ Производящая функция Производящая функция чисел Эйлера I рода имеет вид: ${\displaystyle {\frac {1-w}{e^{(w-1)z}-w}}=\sum _{m,n\geq 0}\left\langle {n \atop m}\right\rangle w^{m}{\frac {z^{n}}{n!}}}$ Числа Эйлера I рода связаны также с производящей функцией последовательности ${\displaystyle n}$-х степеней (полилогарифм целого отрицательного порядка): ${\displaystyle \sum _{k=1}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n-1}\left\langle {n \atop m}\right\rangle x^{m+1}}{(1-x)^{n+1}}}.}$ Кроме того, Z-преобразование из ${\displaystyle \left\{n^{k}\right\}_{k=1}^{N}}$ является генератором первых N строк треугольник чисел Эйлера, когда знаменатель ${\displaystyle n}$-й элемента преобразования сокращается умножением на ${\displaystyle (z-1)^{j+1}}$: ${\displaystyle Z\left[\{n^{k}\}_{k=1}^{3}=\left\{{\frac {z}{(z-1)^{2}}},{\frac {z+z^{2}}{(z-1)^{3}}},{\frac {z+4z^{2}+z^{3}}{(z-1)^{4}}}\right\}\right]}$ Тождество Ворпицкого Тождество Ворпицкого выражает степенную функцию в виде суммы произведений чисел Эйлера I рода и обобщённых биномиальных коэффициентов: ${\displaystyle x^{n}=\sum _{m=0}^{n-1}\left\langle {n \atop m}\right\rangle {x+m \choose n}.}$ В частности: ${\displaystyle x^{2}={x \choose 2}+{x+1 \choose 2}}$ ${\displaystyle x^{3}={x \choose 3}+4{x+1 \choose 3}+{x+2 \choose 3}}$ ${\displaystyle x^{4}={x \choose 4}+11{x+1 \choose 4}+11{x+2 \choose 4}+{x+3 \choose 4}}$ и т. д. Эти тождества легко доказываются по индукции. Тождество Ворпицкого даёт ещё один способ вычисления суммы первых ${\displaystyle n}$ квадратов: ${\displaystyle \sum _{k=1}^{n}k^{2}=\sum _{k=1}^{n}\left\langle {2 \atop 0}\right\rangle {k \choose 2}+\left\langle {2 \atop 1}\right\rangle {k+1 \choose 2}=\sum _{k=1}^{n}{k \choose 2}+{k+1 \choose 2}=}$ ${\displaystyle =\left({1 \choose 2}+{2 \choose 2}+\dots +{n \choose 2}\right)+\left({2 \choose 2}+{3 \choose 2}+\dots +{n+1 \choose 2}\right)=}$ ${\displaystyle ={n+1 \choose 3}+{n+2 \choose 3}={\frac {n(n+1)(2n+1)}{6}}.}$ Литература Дональд Кнут, Роналд Грэхем, Орен Паташник. Числа Эйлера // Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7. Weisstein, Eric W. Eulerian Number (англ.) на сайте Wolfram MathWorld. Weisstein, Eric W. Worpitzky’s Identity (англ.) на сайте Wolfram MathWorld. Eulerian Numbers. MathPages.