Числа Ейлера 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 з Енциклопедії цілочисельних послідовностей):

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</math> перестановок вигляду\{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\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^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) ) }

Література[ред.ред. код]