Числа Ейлера 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$-мірний об'єм частини $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$.

Приклад

Перестановки $\pi$ четвертого порядку, повинні задовільняти одній із двох нерівностей: $\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$.

Зв'язок з біноміальними коефіцієнтами і степеневими формулами

Зв'язок між звичайними степенями та узагальненими біноміальними коефіцієнтами:

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

для цілих $n\geq 0$.

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

Тотожність Ворпицького виражає $x^{n}$ як суму узагальнених біноміальних коефіцієнтів:

$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