Числа Эйлера 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)$. Таким образом,

$\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}$. Количество подъёмов в $\rho$ равняется количеству подъёмов в $\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\geq0} \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.