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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В комбінаториці числом Ейлера I роду із по , що позначається чи , називається кількість перестановок порядку з , тобто таких перестановок , що існує рівно індексів , для яких .

Числа Ейлера I роду мають також геометричну і імовірнісну інтерпретацію: число виражає -мірний об'єм частини -мірного гіперкуба, обмеженого -мірними гіперплощинами і ; воно виражає імовірність того, що сума n незалежних змінних з рівномірним розподілом на відрізку лежить між .

Приклад[ред.ред. код]

Перестановки четвертого порядку, повинні задовільняти одній із двох нерівностей: чи . Таких перестановок рівно 11 штук:

1324 1423 2314 2413 3412 1243 1342 2341 2134 3124 4123

Тому .

Властивості[ред.ред. код]

Для заданого натурального числа існує єдина перестановка тобто . Також існуж єдина перестановка, яка має тобто . Таким чином,

для всіх натуральних .

Дзеркальним відображенням перестановки з є перестановка з . Таким чином,

Трикутник чисел Ейлера першого роду[ред.ред. код]

Значення чисел Ейлера для малих значень і наведені в наступній таблиці (Послідовність 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

Легко зрозуміти, що значення на головній діагоналі матриці задаються формулою:

Трикутник Ейлера, як і трикутник Паскаля, симетричний зліва і справа. Але в цьому випадку закон симетрії відмінний: при . Тобто перестановка має тоді і тільки тоді, коли її«відбраження» має .

Рекурентна формула[ред.ред. код]

Кожна перестановка із набору пр <водить до>n</math> перестановок вигляду, якщо ми вставляємо новий елемент n всіма можливими способами. Вставляючи в -ту позицію, отримуємо перестановку . Кількість підйомів в дорівнює кількості підйомів в , якщо чи, якщо ; і воно більше кількості підйомів в , якщо чи ,якщо . Тому, в сумі має способів побудови перестановок із , які мають підйомів, плюс способів побудови перестановок із , які мають підйомів. Тоді рекурентна формула для цілих має вигляд:

Покладемо також, що (для цілих ), і припустимо, що при .

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

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

для цілих .

і т. д. Ці тотожності легко доводяться методом математичної індукції.

Варто відмітити, що ця формула представляє ще один спосіб знаходження суми перших квадратів:

Явні формули для чисел Ейлера[ред.ред. код]

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

домножуючи першу тотожність на і сумуючи по , отримуємо:

Заміняючи на і прирівнюючи коефіцієнти при , отримуємо другу тотожність. Таким чином, ці дві тотожності еквівалентні. Перша тотожність приміняється при малих значеннях :

Сумування чисел Ейлера I роду[ред.ред. код]

Із комбінаторного визначення очевидно, що сума чисел Ейлера I роду, розміщених в n-му рядку дорівнює , так як вона дорівнює кількості всіх перестановок порядку :

Знакозмінні суми чисел Ейлера I роду при фиксованому значенні n зв'язані з числами Бернуллі :

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

Генератриса і тотожність Ворпицького[ред.ред. код]

Генератриса чисел Ейлера I роду має вигляд:

Числа Ейлера I роду зв'язані також з генератрисою послідовності -х степенів:

Крім того, Z-перетворення із

є генератором перших 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) ) }

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