Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Числа Ейлера 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, для яких π jj + 1 .

Числа Ейлера I роду мають також геометричної та вероятностной інтерпретацією - число \ Frac {1} {n!} \ left \ langle {n \ atop k} \ right \ rangle висловлює:


1. Приклад

Перестановки π четвертого порядку, які мають рівно два підйоми, повинні відповідати одній з трьох нерівностей: π 12> π 34 , π 123> π 4 або π 1> π 234 . Таких перестановок рівно 11 штук:

1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.

Тому \ Left \ langle {4 \ atop 2} \ right \ rangle = 11 .

2. Властивості

Для заданого натурального числа 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 nm-1} \ right \ rangle.

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

Значення чисел Ейлера \ 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 підйомів.


2.2. Рекурентна формула

Кожна перестановка \ 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} . Кількість підйомів в ρ дорівнює кількості підйомів в ρ , Якщо j = 1 або якщо π j - 1j ; І воно більше кількості підйомів в ρ , Якщо j = n або якщо ρ j - 1> ρ j . Отже, π в сумі має (K +1) \ left \ langle {n-1 \ atop k} \ right \ rangle способів побудови перестановок з ρ , Які мають k підйомів, плюс ((N-2) - (k-1) +1) \ left \ langle {n-1 \ atop k-1} \ right \ rangle способів побудови перестановок з ρ , Які мають k - 1 підйомів. Тоді шукана рекуррентная формула для цілих n> 0 має вигляд:

\ Left \ langle {n \ atop k} \ right \ rangle = (k +1) \ left \ langle {n-1 \ atop k} \ right \ rangle + (nk) \ left \ langle {n-1 \ atop k-1} \ right \ rangle.

Покладемо також, що

\ Left \ langle {0 \ atop k} \ right \ rangle = [k = 0] (Для цілих k ),

і при k <0 :

\ Left \ langle {n \ atop k} \ right \ rangle = 0.

2.3. Явні формули

Явна формула для чисел Ейлера I роду:

\ Left \ langle {n \ atop m} \ right \ rangle = \ sum_ {k = 0} ^ {m} {n +1 \ choose k} (m +1- k) ^ n (-1) ^ k

дозволяє отримати відносно прості вирази при малих значеннях m:

\ Left \ langle {n \ atop 0} \ right \ rangle = 1;
\ Left \ langle {n \ atop 1} \ right \ rangle = 2 ^ n-n-1;
\ Left \ langle {n \ atop 2} \ right \ rangle = 3 ^ n-(n +1) 2 ^ n + {n +1 \ choose 2}.

2.4. Формули підсумовування

З комбінаторного визначення очевидно, що сума чисел Ейлера 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.

Також справедливі наступні тотожності, що зв'язують числа Ейлера I роду з числами Стірлінга II роду :

\ Sum_ {k = nm} ^ n \ left \ langle {n \ atop k} \ right \ rangle {k \ choose nm} = m! \ left \ {{n \ atop m} \ right \}
\ 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}

2.5. Твірна функція

Твірна функція чисел Ейлера 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 ^ nx ^ 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 +4 z ^ 2 + z ^ 3} {(z-1) ^ 4} \ right \} \ right]

2.6. Тотожність Ворпіцкого

Тотожність Ворпіцкого висловлює ступеневу функцію у вигляді суми добутків чисел Ейлера I роду і узагальнених біноміальних коефіцієнтів :

x ^ n = \ sum_ {m = 0} ^ {n-1} \ left \ langle {n \ atop m} \ right \ rangle {x + m \ choose n}.

Зокрема:

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} ^ nk ^ 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}.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Види і роду військ
Маршал роду військ
Блок (прізвище дворянського роду)
Головний маршал роду військ
Об'єднання членів роду Романових
Вовкодав з роду Сірих Псів
Фазові переходи першого роду
Помилки першого і другого роду
Фазові переходи другого роду
© Усі права захищені
написати до нас