Числа Эйлера I рода

Не следует путать с Эйлеровыми числами.

В комбинаторике числом Эйлера I рода из n по k, обозначаемым $\left\langle {n \atop k}\right\rangle$ или $E(n,k)$, называется количество перестановок порядка n с k подъёмами, то есть таких перестановок $\pi =(\pi _{1},\pi _{2},\dots ,\pi _{n})$, что существует ровно k индексов j, для которых $\pi _{j}<\pi _{j+1}$.

Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число ${\frac {1}{n!}}\left\langle {n \atop k}\right\rangle$ выражает:

• объём части n-мерного гиперкуба, ограниченного гиперплоскостями $x_{1}+x_{2}+\dots +x_{n}=k$ и $x_{1}+x_{2}+\dots +x_{n}=k-1$;
• вероятность того, что сумма n независимых равномерно распределённых в отрезке $[0,1]$ переменных лежит между k-1 и k.

Пример

Перестановки $\pi$ четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств: $\pi _{1}<\pi _{2}>\pi _{3}<\pi _{4}$, $\pi _{1}<\pi _{2}<\pi _{3}>\pi _{4}$ или $\pi _{1}>\pi _{2}<\pi _{3}<\pi _{4}$. Таких перестановок ровно 11:

1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.

Поэтому $\left\langle {4 \atop 2}\right\rangle =11$.

Свойства

Для заданного натурального числа $n$ существует единственная перестановка без подъёмов, то есть $(n,n-1,n-2,\dots ,1)$. Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть $(1,2,3,\dots ,n-1,n)$. Таким образом,

$\left\langle {n \atop 0}\right\rangle =\left\langle {n \atop n-1}\right\rangle =1$ для всех натуральных $n$.

Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,

$\left\langle {n \atop m}\right\rangle =\left\langle {n \atop n-m-1}\right\rangle .$

Треугольник чисел Эйлера первого рода

Значение чисел Эйлера $\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

Легко понять, что значения на главной диагонали матрицы задаются формулой: $\left\langle {n \atop n}\right\rangle =[n=0].$

Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен:

$\left\langle {n \atop k}\right\rangle =\left\langle {n \atop n-1-k}\right\rangle$ при n > 0.

То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.

Рекуррентная формула

Каждая перестановка $\rho =\rho _{1}\dots \rho _{n-1}$ из набора $\{1,2,3,n-1\}$ приводит к $n$ перестановкам из $\{1,2,3,n\}$, если мы вставляем новый элемент n всеми возможными способами. Вставляя $n$ в $j$-ю позицию, получаем перестановку $\pi =\rho _{1}\dots \rho _{j-1}n\rho _{j}\dots \rho _{n-1}$. Количество подъёмов в $\pi$ равняется количеству подъёмов в $\rho$, если $j=1$ или если $\pi _{j-1}<\pi _{j}$; и оно больше количества подъёмов в $\rho$, если $j=n$ или если $\rho _{j-1}>\rho _{j}$. Следовательно, $\pi$ в сумме имеет $(k+1)\left\langle {n-1 \atop k}\right\rangle$ способов построения перестановок из $\rho$, которые имеют $k$ подъёмов, плюс $((n-2)-(k-1)+1)\left\langle {n-1 \atop k-1}\right\rangle$ способов построения перестановок из $\rho$, которые имеют $k-1$ подъёмов. Тогда искомая рекуррентная формула для целых $n>0$ имеет вид:

$\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 .$

Положим также, что

$\left\langle {0 \atop k}\right\rangle =[k=0]$ (для целых $k$),

и при $k<0$:

$\left\langle {n \atop k}\right\rangle =0.$

Явные формулы

Явная формула для чисел Эйлера I рода:

$\left\langle {n \atop m}\right\rangle =\sum _{k=0}^{m}{n+1 \choose k}(m+1-k)^{n}(-1)^{k}$

позволяет получить относительно простые выражения при малых значениях m:

$\left\langle {n \atop 0}\right\rangle =1;$

$\left\langle {n \atop 1}\right\rangle =2^{n}-n-1;$

$\left\langle {n \atop 2}\right\rangle =3^{n}-(n+1)2^{n}+{n+1 \choose 2}.$

Формулы суммирования

Из комбинаторного определения очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке, равна $n!$, так как она равна количеству всех перестановок порядка $n$:

$\sum _{m=0}^{n}\left\langle {n \atop m}\right\rangle =n!$

Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли $B_{n+1}$:

$\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}},$

$\sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n \choose m}^{-1}=(n+1)B_{n},$

$\sum _{m=0}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n-1 \choose m}^{-1}=0.$

Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода:

$\sum _{k=n-m}^{n}\left\langle {n \atop k}\right\rangle {k \choose n-m}=m!\left\{{n \atop m}\right\}$

$\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\}$

$\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 рода имеет вид:

${\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 рода связаны также с производящей функцией последовательности $n$-х степеней (полилогарифм целого отрицательного порядка):

$\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-преобразование из

$\left\{n^{k}\right\}_{k=1}^{N}$

является генератором первых N строк треугольник чисел Эйлера, когда знаменатель $n$-й элемента преобразования сокращается умножением на $(z-1)^{j+1}$:

$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 рода и обобщённых биномиальных коэффициентов:

$x^{n}=\sum _{m=0}^{n-1}\left\langle {n \atop m}\right\rangle {x+m \choose n}.$

В частности:

$x^{2}={x \choose 2}+{x+1 \choose 2}$

$x^{3}={x \choose 3}+4{x+1 \choose 3}+{x+2 \choose 3}$

$x^{4}={x \choose 4}+11{x+1 \choose 4}+11{x+2 \choose 4}+{x+3 \choose 4}$

и т. д. Эти тождества легко доказываются по индукции.

Тождество Ворпицкого даёт ещё один способ вычисления суммы первых $n$ квадратов:

$\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}=$

$=\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)=$

$={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.
• Д. Кнут. Основные алгоритмы  // Искусство программирования. — М.: Вильямс , 2006. — Т. 1.
• Weisstein, Eric W. Eulerian Number (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Worpitzky’s Identity (англ.) на сайте Wolfram MathWorld.
• Eulerian Numbers. MathPages.