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

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

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

ПрикладРедагувати

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

1324 1423 2314 2413 3412 1243 1342 2341 2134 3124 4123

Тому  .

ВластивостіРедагувати

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

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

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

 

Трикутник чисел Ейлера першого родуРедагувати

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

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

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

Рекурентна формулаРедагувати

Кожна перестановка   із набору   приводить до   перестановок вигляду , якщо ми вставляємо новий елемент 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) ) }

ЛітератураРедагувати