Эйлера числа

В комбинаторике числом Эйлера 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, для которых π_j < π_{j + 1}.

Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией: число $\frac{1}{n!}\left\langle{n\atop k}\right\rangle$ выражает n-мерный объём части n-мерного гиперкуба, ограниченного (n − 1)-мерными гиперплоскостями $x_1+x_2+\dots+x_n=k$ и $x_1+x_2+\dots+x_n=k-1$; оно же выражает вероятность того, что сумма n независимых переменных с равномерным распределением в отрезке [0,1] лежит между k − 1 и k.

Пример

Перестановки π четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из двух неравенств: π₁ < π₂ < π₃ > π₄ или π₁ > π₂ < π₃ < π₄. Таких перестановок ровно 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}$. Количество подъёмов в ρ равняется количеству подъёмов в ρ, если j = 1 или если π_{j − 1} < π_j; и оно больше количества подъёмов в ρ, если j = n или если ρ_{j − 1} > ρ_j. Следовательно, π в сумме имеет $(k+1)\left\langle{n-1\atop k}\right\rangle$ способов построения перестановок из ρ, которые имеют k подъёмов, плюс $((n-2)-(k-1)+1)\left\langle{n-1\atop k-1}\right\rangle$ способов построения перестановок из ρ, которые имеют 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.

Связь с биномиальными коэффициентами и степенными функциями

Применение чисел Эйлера главным образом состоит в предоставлении замечательной связи между обычными степенями и последовательными биномиальными коэффициентами:

$x^n = \sum_k \left\langle{n\atop k}\right\rangle {x+k\choose n}$

для целых $n\geq0$. (Это тождество также известно под названием тождества Верпинского). В частности:

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

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

Поскольку рекуррентность для чисел Эйлера достаточно сложная, они удовлетворяют лишь немногим свойствам:

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

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

Умножая первое тождество на z^{n − m} и суммируя по m, получаем:

$\sum_m \left\{ {n\atop m} \right\} m!z^{n-m} = \sum_{k} \left\langle{n\atop k}\right\rangle (z+1)^k.$

Заменяя z на z + 1 и уравнивая коэффициенты при z^k, получаем второе тождество. Таким образом, эти два тождества эквивалентны. Первое тождество применяется при малых значениях m:

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

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

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

Суммирование чисел Эйлера I рода

Из комбинаторного определения очевидно, что сумма чисел Эйлера 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.$

Также справедливы следующие тождества:

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

Тождество Ворпицкого выражает xⁿ как сумму обобщенных биномиальных коэффициентов:

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

Программы на PARI/GP для вычисления чисел Эйлера

 \\ рекуррентная формула
 { E(n, k) =                 
     if(k<1|k>n, 0, 
       if(n==1, 1, k*E(n-1,k) + (n-k+1)*E(n-1,k-1) )
     )
 }
 
 \\ явная формула
 { E(n, k) = sum(j=0, k, (-1)^j * (k-j)^n * binomial(n+1,j) ) }

Литература

• Дональд Кнут, Роналд Грэхем, Орен Паташник Числа Эйлера // Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7
• Д. Кнут. Искусство программирования. Т.1: Основные алгоритмы — М.: Вильямс — 2006 г.
• Eric W. Weisstein, Eulerian Number at MathWorld
• Eric W. Weisstein, Worpitzky’s Identity at MathWorld
• Eulerian Numbers at MathPages