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

Числа Ейлера I роду(англ.Eulerian numbers) — кількість перестановок чисел від [math]1[/math] до [math]n[/math] таких, що у кожній їх існує рівно [math]m[/math] підйомів. Числа Ейлера I роду позначають як [math] \ langle \ rangle [ / math] або [math] A (n, m) [/ math] .

Висновок рекурентної формули [ред.]

Нехай у нас є перестановка [math] \pi = \pi_1, \pi_2\ldots \pi_ [/math] . Тоді операцією вставки елемента з номером [math]n[/math] в якусь із позицій ми отримаємо [math]n[/math] перестановок виду [math]\theta = \theta_1, \theta_2\ldots \theta_p, n, \theta_q\ldots \theta_[/math] . Далі розглянемо два випадки:

  1. Кількість підйомів у перестановці [math]\theta[/math] дорівнює кількості підйомів [math]\pi[/math] . Цього можна досягти, вставляючи елемент [math]n[/math] на перше місце в [math]\theta[/math] (всього [math]\langle\rangle [/math] можливостей) або перед останнім останнім елементом кожного підйому (ще [math]m \times [/math] [math] \langle\rangle [/math] разів).
  2. Кількість підйомів у новій перестановці на один більша за попередню кількість. Цього ефекту домагаємося вставкою елемента [math]n[/math] у всі місця, які не відповідають критерію першого пункту. Таких вставок, як не важко здогадатися, можна зробити [math] (n - m) [/ math] [ math] \ langle \ rangle [/ math] .

Тоді рекурентна формула має вигляд:

[math]\left\langle\right\rangle[/math] [math] = (m + 1)[/math] [math]\left\langle\right\rangle[/math] [math] + (n - m)[/math] [math]\left\langle\right\rangle[/math]

Приймемо також таке початкове значення:

[math]\left\langle\right\rangle[/math] [math] = [m = 0][/math] [1] .

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

Розглянемо всі перестановкипорядку [math]4[/math] , в яких є рівно [math]2[/math] підйому (у квадратних дужках один або більше підйомів поспіль):

[math] \ left \ langle \ right \ rangle [/ math] [math] = 11: [124] 3, [13] [24], [134] 2, [14] [23], 2 [134], [23][14], [23][41], [24][13], 3[124], [34][12], 4[123], [/math]

Відповідно до алгоритму виведення рекурентної формули ми можемо додати [math]4[/math] у наступні позиції всіх перестановок порядку [math]3[/math] з двома підйомами, не збільшивши кількість підйомів:

[math] \left\langle\right\rangle[/math] [math] = 1: [123] \Rightarrow (4)[123], [1(4)][23], [12(4)]3 [/math]

Далі розглянемо всі перестановки порядку [math]3[/math] з одним підйомом, причому операцією вставки [math]4[/math] ми збільшуватимемо кількість перестановок на [math]1[/math] :

[math] \left\langle\right\rangle[/math] [math] = 4:[/math] [math][13]2 \Rightarrow [13(4)]2, [13][2(4) ];[/math] [math]2[13] \Rightarrow [2(4)][13], 2[13(4)];[/math] [math][23]1 \Rightarrow [23(4 )]1, [23][1(4)];[/math] [math]3[12] \Rightarrow [3(4)][12], 3[12(4)];[/math]

Таким чином ми переконуємося у вірності формули:

[math] \left\langle\right\rangle[/math] [math] = (2 + 1)[/math] [math]\left\langle\right\rangle[/math] [math] + (4 - 2)[/math] [math]\left\langle\right\rangle[/math] [math] = 11;[/math]

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

На значеннях [math]n = m[/math] чисел Ейлера I роду можна побудувати масив [math]n \times m[/math] , нижньодіагональна частина якого названа трикутником чисел Ейлера I роду.

Явні формули [ред.]

Зв'язок чисел Ейлера I роду з перерізами гіперкубів [ред.]

Для доказу цього факту нам знадобиться така теорема:

  • [math]G_^ := \^ : (w \cdot x) \leqslantz \>[/math] - напівпростір;
  • [math]I^n: = [0,1]^n[/math];
  • [math][n] := \[/math];
  • [math]1_K[/math] , де [math]K[/math] - підмножина [math]\[/math] , - Вектор, де значення координат з номерами, що входять в [math]K[/math] , рівні [math] 1 [/ math], а інші - нулі;
  • Для [math]r \in \mathbb[/math] і [math]n \in \mathbb[/math] : [math]r^n_+ := (\max>)^n[/math] .

ейлера

ейлера

Розглянемо перетин гіперкуба напівпростором [math]G^n_,m>[/math]. Вектор [math]1_[/math] (усі координати якого рівні одиниці) з'являється тут через те, як ми визначили у формулюванні січучі гіперплощини ([math]x_1+x_2+\ldots +x_n = m m+1[/math] ) — це вектор нормалі до [math]\mathrm[/math]. Вочевидь, що з даному значенні вектора твір [math]\prod\limits_^w_i[/math] дорівнює одиниці (вектор [math]w_i[/math] тут — одиничний вектор [math]1_[/math] , тобто розглядається твір всіх його координат – одиниць). Розглянемо вираз, що стоїть під знаком суми. При ітерації за підмножинами [math][n][/math] рівної потужності виходитимуть однакові доданки, оскільки вираз [math](-1)^(z-w \cdot 1_K)^n_+[/math] залежить лише від потужності ітерованого у сумі підмножини [math]K[/math] — скалярне твір [math]w \cdot 1_K[/math] однаково за рахунок того лише факту, що воно обчислюється як сума творів відповідних координат, де рівно [math]n - K[ /math] їх звертаються у нуль. Такий скалярний добуток буде дорівнює потужності [math]K[/math]. Замінимо ітератор суми значенням потужності множини [math]K[/math]. Також обмежимо верхній індекс підсумовування значенням [math]m+1[/math] , тому що при великих значеннях [math]j[/math] доданок буде звертатися в нуль ([math]r^n_+[/math]). Звідси маємо [math][/math] таких однакових доданків, де [math]j = K[/math].

Тоді перейдемо від початкового формулювання теореми до наступного:

Покладемо [math]W_n^m[/math] - фігура, утворена перетином гіперкуба [math][0,1]^[/math] площинами [math]\sum\limits_^ x_= m[/math] і [math]\sum\limits_^ x_= m+1[/math] .

[math]W_n^m := \ < x \in \mathbb: m \leqslant x \cdot 1_ \leqslant m+1 \> \cap I^[/math]

Тоді перейдемо до наступної рівності:

[math]\mathrm_(W_n^m) = \mathrm_n(G_,m+1>^ \cap I^n) - \mathrm_n(G_,m>^ \cap I^n)[/math] [math]= \dfrac[\sum\limits_^(-1)^(m+1-j)^ - \sum\limits_^(-1)^(m-j)^][/math] [math] = \dfrac\sum\ limits_^(-1)^j(m+1-j)^n[/math] [math] = \dfrac\sum\limits_^(-1)^j(m+1-j)^n[/math ] (елемент суми з номером [math]j=m+1[/math] звертається в нуль) [math] = [/math] [math]\dfrac[/math] [math]\left\langle\right\rangle [/math] (друга явна формула)

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

  1. Неважко побачити, що кожен ряд ненульових значень симетричний щодо своєї середини, тобто: [math] \ left \ langle \ right \ rangle = \ left \ langle \ right \ rangle [/ math] [math], \ \ 0 \ leqslant k \ leqslant n-1. \, [/math]
  2. Сума всіх значень кожного ряду дорівнює [Math] n! [/math] : [math]\sum\limits_^[/math] [math] \left\langle\right\rangle[/math] [math] = n!,\ n \geqslant 0, \,[/math ]
  3. Зв'язок чисел Ейлера I роду з числом поєднань: [math]\sum\limits_^n(-1)^m[/math] ]
  4. Імовірність того, що сума [math]n[/math] незалежних рівномірно розподілених у відрізку [math][0,1][/math] змінних лежить між [math]m-1[/math] та [math]m[/ math] дорівнює [math]\dfrac\left\langle\right\rangle[/math] .

Числа Ейлера IIроду(англ.Eulerian numbers of the second kind) — кількість перестановок мультимножини від [math]1[/math] до [math]n[/math] виду [math]\ [/math] , що мають властивість "всі елементи перестановки, що зустрічаються між двома входженнями [math]z[/math] для будь-якого [math]z[/math] , більше, ніж [math]z[/math] ", таких, що у кожній їх існує рівно [math]m[/math] підйомів. Числа Ейлера II роду позначаються як [math] \ scriptstyle \ left \ langle \! \! \left\langle \right\rangle \!\! \right\rangle [/math]

Розглянемо [math] n = 3[/math]. Тоді існує [math]15[/math] перестановок такого виду, серед яких одна не має підйомів, [math]8[/math] штук мають всього [math]1[/math] підйом, і [math]6[/math ] перестановок мають [math]2[/math] підйому:

[Math] 332211, \; [/ Math] [Math] 221 [13] 3, \; 22 [13] 31, \; 2 [23] 311, \; [23] 3211, \; 1 [13] 322, \; [13] 3221, \; 331 [12] 2, \; 33[12]21, [/math] [math]1[12][23]3,\; [12] 2 [13] 3, \; 1 [123] 32, \; [123] 321, \; [13] 3 [12] 2, \; [12] [23] 31. [/math]

Доведемо лему методом математичної індукції.

  • База. Для [math]n=1[/math] очевидно, що є тільки одна така перестановка.
  • Перехід. Розглянемо якусь перестановку довжини [math] 2n [/ math]. Таких перестановок[math](2n-1)!![/math]. Тепер доведемо, що перестановок довжини [math]2(n+1)[/math] буде [math](2(n+1)-1)!![/math] . Спробуємо вставити два числа [math]n + 1[/math]. Очевидно, що їх не можна вставити не на сусідні місця, тому що в такому разі між ними точно будуть менші елементи. Але їх можна вставити в будь-які два сусідні місця, тому що вони найбільше чисел у перестановці, а значить вони не порушать властивості для інших елементів. Таким чином, два нових елементи можна вставити в [math]2n+1[/math] місце. В підсумкуперестановок довжини [math]2(n+1)[/math] буде [math](2n-1)!!\cdot (2n+1)=(2n+1)!!=(2(n+1)- 1)!![/math].

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

Числа Ейлера II роду можна висловити рекурсивно так:

[math] \ left \ langle \! \! \left\langle \right\rangle \!\! \right\rangle[/math] [math] = (2n-m-1) [/math] [math]\left\langle \!\! \left\langle \right\rangle \!\! \right\rangle[/math] [math] + (m+1) [/math] [math]\left\langle \!\! \left\langle \right\rangle \!\! \right\rangle, [/math]

З початковим умовою для [math]n = 0[/math] :

[math] \ left \ langle \! \! \left\langle \right\rangle \!\! \right\rangle[/math] [math] = [m=0]. [/math]

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

Значення чисел Ейлера II роду для [math] 0 \ leqslant n \ leqslant m \ leqslant 9 [/ math] представлені в даному масиві. Нижньодіагональна його частина називається трикутником чисел Ейлера II роду.