Числа Ейлера I роду

Значення чисел Ейлера ${\displaystyle \left\langle {n \atop k}\right\rangle }$ для малих значень ${\displaystyle n}$ і ${\displaystyle k}$ наведені в наступній таблиці (послідовність A008292 з Онлайн енциклопедії послідовностей цілих чисел, OEIS):

Легко зрозуміти, що значення на головній діагоналі матриці задаються формулою: ${\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 }$ при ${\displaystyle n>0}$. Тобто перестановка має ${\displaystyle n-1-k}$ тоді і тільки тоді, коли її«відбраження» має ${\displaystyle 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 \rho }$ дорівнює кількості підйомів в ${\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 x^{n}=\sum _{k}\left\langle {n \atop k}\right\rangle {x+k \choose n}}$

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

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

Оскільки рекурентність для чисел Ейлера достатньо складна, вони задовільняють лише небагатьом властивостям:

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

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

домножуючи першу тотожність на ${\displaystyle z^{n-m}}$ і сумуючи по ${\displaystyle m}$, отримуємо:

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

Заміняючи ${\displaystyle z}$ на ${\displaystyle z+1}$ і прирівнюючи коефіцієнти при ${\displaystyle z^{k}}$, отримуємо другу тотожність. Таким чином, ці дві тотожності еквівалентні. Перша тотожність приміняється при малих значеннях ${\displaystyle m}$:

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

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

${\displaystyle \left\{{n \atop 2}\right\}=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.}$

Також справедливі такі тотожності:

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

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

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