Изменения

'''''Числа Эйлера I рода''''' (''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]] чисел от 1 до ''n'' таких, что в каждой из них существует ровно ''m'' подъемов. Числа Эйлера I рода обозначают как <tex dpi = "160">\langle{n\atop m}\rangle </tex> или же <tex dpi = "160">A(n, m)</tex>.{{Определение

Пусть <tex dpi = "130">a</tex> и <tex dpi = "130">b</tex> - соседние элементы некоторой перестановки порядка <tex dpi = "130">n</tex> причем <tex dpi = "130">a > b</tex>. Тогда пара <tex dpi = "130">(a, b)</tex> называется '''подъемом''' (''ascent'') данной перестановки.

Пусть у нас есть некая перестановка <tex dpi = "160"> \pi = \pi_1, \pi_2...\pi_{n-1} </tex>. Тогда операцией вставки элемента с номером n в какую-либо из позиций мы получим <tex dpi = "160">n</tex> перестановок вида <tex dpi = "160">\theta = \theta_1, \theta_2...\theta_p, n, \theta_q...\theta_{n-1}</tex>. Далее рассмотрим два случая:

1. Количество подъемов в перестановке <tex dpi = "130">\theta</tex> равно количеству подъемов в <tex dpi = "130">\pi</tex>. Этого можно добиться, вставляя элемент <tex dpi = "130">n</tex> на самое первое место в <tex dpi = "130">\theta</tex> (всего <tex dpi = "160">\langle{n\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex dpi = "130">m \times </tex><tex dpi = "160"> \langle{n\atop m}\rangle </tex> раз).

2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex dpi = "130">n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex dpi = "130">(n - m)</tex><tex dpi = "160">\langle{n\atop m}\rangle</tex>.

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

:<tex dpi = "160">\left\langle{n\atop m}\right\rangle = (m + 1)\left\langle{n - 1\atop m}\right\rangle + (n - m)\left\langle{n - 1\atop m - 1}\right\rangle</tex>

Примем также следующие начальные значенияследующее начальное значение: :<tex dpi = "160">\langle{n\atop m}\rangle = 0</tex>, если <tex dpi = "130">m < 0</tex>  Также для четных <tex dpi = "130">k</tex>::<tex dpi = "160">\left\langle{n\atop m}\right\rangle = [m = 0]</tex>, Запись [выражение] означает [http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D0%90%D0%B9%D0%B2%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0 нотацию Айверсона, где:<tex dpi = "160"> [statement] =</tex><tex dpi = "140"> \begin{cases} 1 & \text{statement} \\ 0 & \text{!statement} \end{cases}</tex>.

Рассмотрим все перестановки порядка <tex dpi = "130">4</tex>, в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд)::<tex dpi = "140"> \left\langle{4\atop 2}\right\rangle = 11: [124]3, [13][24], [134]2, [14][23], 2[134], [23][14], [23][41], [24][13], 3[124], [34][12], 4[123], </tex>

Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка <tex dpi = "130">3</tex> с двумя подъемами, не увеличив количество подъемов:

:<tex dpi = "140">

Далее рассмотрим все перестановки порядка <tex dpi = "130">3</tex> с одним подъемом, причем операцией вставки <tex dpi = "130">4</tex> мы будем увеличивать количество перестановок на 1:

:<tex dpi = "140"> \left\langle{3\atop 1}\right\rangle = 4:</tex>

:<tex dpi = "140">[13]2 => [13(4)]2, [13][2(4)];</tex>

:<tex dpi = "140">2[13] => [2(4)][13], 2[13(4)];</tex>

:<tex dpi = "140">[23]1 => [23(4)]1, [23][1(4)];</tex>

:<tex dpi = "140">3[12] => [3(4)][12], 3[12(4)];</tex>

:<tex dpi = "160"> \left\langle{4\atop 2}\right\rangle = (2 + 1) \left\langle{3\atop 2}\right\rangle + (4 - 2)\left\langle{3\atop 1}\right\rangle = 11;</tex>

:<tex dpi = "180">\left\langle{n\atop m}\right\rangle = \sum_sum\limits_{k=0}^{m}[ (-1)^k {n+1\choose k} (m+1-k)^n]</tex>

На значениях <tex dpi = "130">n = m</tex> чисел Эйлера I рода можно построить массив <tex dpi = "130">n \times m</tex>, нижнедиагональная часть которого названа треугольником чисел Эйлера I рода.

::{| class="number_triangle"

| style="background:#FFDEAD; color:black;" | '''2036'''

| style="background:#FFDEAD; color:black;" | '''4083'''

:<tex dpi = "160">\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle,\ n \ge 1,\ 0 \le k \le n-1. \, </tex>

2. Сумма всех значений каждого ряда равна <tex dpi = "130"> n! </tex>::<tex dpi = "160">\sum_sum\limits_{k=0}^{n} \left\langle{n\atop m}\right\rangle = n!,\ n \ge 0, \,</tex>

3. Еще одно условие равенства нулюСвязь чисел Эйлера I рода с числом сочетаний::<tex dpi = "160">\sum_sum\limits_{m=0}^n (-1)^m {\left\langle{n\atop m}\right\rangle}{n-1\choose m}^{-1}=0.</tex>

'''''Числа Эйлера II рода''''' (''Eulerian numbers of the second kind'') — количество перестановок мультимножества от <tex dpi = "130">1</tex> до <tex dpi = "130">n</tex> вида <tex dpi = "130">\{1,1,2,2..n,n\}</tex>, обладающих свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex dpi = "130">z</tex> для любого <tex dpi = "130">z</tex>, больше, чем <tex dpi = "130">z</tex>", таких, что в каждой из них существует ровно <tex dpi = "130">m</tex> подъемов. Числа Эйлера II рода обозначаются как <tex dpi = "160"> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>

Рассмотрим <tex dpi = "130"> n = 3</tex>. Тогда существует 15 перестановок такого вида, среди которых одна не имеет подъемов, 8 штук имеют всего 1 подъем, и 6 перестановок имеют 2 подъема:

:<tex dpi = "140"> 332211,\; </tex>:<tex dpi = "140"> 221[13]3,\; 22[13]31,\; 2[23]311,\; [23]3211,\; 1[13]322,\; [13]3221,\; 331[12]2,\; 33[12]21, </tex> :<tex dpi = "140">1[12][23]3,\; [12]2[13]3,\; 1[123]32,\; [123]321,\; [13]3[12]2,\; [12][23]31. </tex>

|statement=Количество перестановок мультимножества <tex dpi = "130">\{1,1,2,2..n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex dpi = "130">z</tex> для любого <tex dpi = "130">z</tex>, больше, чем

:<tex dpi = "160"> \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle = (2n-m-1) \left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle + (m+1) \left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, </tex>

С начальным условием для <tex dpi = "130>n = 0</tex>::<tex dpi = "160"> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle = [m=0]. </tex>

Значения чисел Эйлера II рода для <tex dpi = "130">0 <= \le n <= \le m <= \le 9</tex> представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.

:::{| class="number_triangle"

| style="background:#FFDEAD; color:black;" | '''1'''