Числа Эйлера I и II рода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 311: Строка 311:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
[[Категория: Булевы функции ]]
+
[[Категория: Комбинаторика ]]

Версия 00:41, 19 декабря 2013

Числа Эйлера I рода (Eulerian numbers) — количество перестановок чисел от 1 до n таких, что в каждой из них существует ровно m подъемов. Числа Эйлера I рода обозначают как [math]\langle{n\atop m}\rangle [/math] или же [math]A(n, m)[/math].

Определение:
Пусть [math]a[/math] и [math]b[/math] - элементы некоторой перестановки порядка [math]n[/math] причем [math]a \gt b[/math]. Тогда пара [math](a, b)[/math] называется подъемом (ascent) данной перестановки.


Вывод рекуррентной формулы

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

1. Количество подъемов в перестановке [math]\theta[/math] равно количеству подъемов в [math]\pi[/math]. Этого можно добиться, вставляя элемент [math]n[/math] на самое первое место в [math]\theta[/math] (всего [math]\langle{n\atop m}\rangle [/math] возможностей) или перед последним последним элементом каждого подъема(еще [math]k \times [/math][math] \langle{n\atop m}\rangle [/math] раз).

2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента [math]n[/math] в конце каждой перестановки или после элемента перестановки со значением [math]n-1[/math]. Таких элементов, как не трудно догадаться, будет [math](n - k)[/math][math]\langle{n\atop m}\rangle[/math].

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

[math]\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[/math]

Примем также следующие начальные значения:

[math]\langle{n\atop m}\rangle = 0[/math], если [math]m \lt 0[/math] или если [math]n = 0[/math];


Пример

Рассмотрим все перестановки порядка [math]4[/math], в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд): [math] \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], [/math]

Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка [math]3[/math] с двумя подъемами, не увеличив количество подъемов:

[math] \left\langle{3\atop 2}\right\rangle = 1: [123] =\gt (4)[123], [1(4)][23], [12(4)]3 [/math]

Далее рассмотрим все перестановки порядка [math]3[/math] с одним подъемом, причем операцией вставки [math]4[/math] мы будем увеличивать количество перестановок на 1:

[math] \left\langle{3\atop 1}\right\rangle = 4:[/math]

[math][13]2 =\gt [13(4)]2, [13][2(4)];[/math]

[math]2[13] =\gt [2(4)][13], 2[13(4)];[/math]

[math][23]1 =\gt [23(4)]1, [23][1(4)];[/math]

[math]3[12] =\gt [3(4)][12], 3[12(4)];[/math]

Таким образом мы убеждаемся в верности формулы:

[math] \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;[/math]

Треугольник чисел Эйлера I рода и явная формула

Явная формула

Приведем также без вывода явную формулу для вычисления чисел Эйлера I рода:

[math]\left\langle{n\atop m}\right\rangle = \sum_{k=0}^{m}[ (-1)^k {n+1\choose k} (m+1-k)^n][/math]


Треугольник чисел Эйлера I рода

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

k = 0 1 2 3 4 5 6 7 8 9 10 11 12
n = 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0 0 0 0
3 1 4 1 0 0 0 0 0 0 0 0 0 0
4 1 11 11 1 0 0 0 0 0 0 0 0 0
5 1 26 66 26 1 0 0 0 0 0 0 0 0
6 1 57 302 302 57 1 0 0 0 0 0 0 0
7 1 120 1191 2416 1191 120 1 0 0 0 0 0 0
8 1 247 4293 15619 15619 4293 247 1 0 0 0 0 0
9 1 502 14608 88234 156190 88234 14608 502 1 0 0 0 0
10 1 1013 47840 455192 1310354 1310354 455192 47840 1013 1 0 0 0
11 1 2036 152637 2203488 9738114 15724248 9738114 2203488 152637 2036 1 0 0
12 1 4083 478271 10187685 66318474 162512286 162512286 66318474 10187685 478271 4083 1 0

Стоит отметить, что гистрограмма, построенная на значениях чисел Эйлера I рода аппроксимируется к гистограмме, построенной на биноминальных коээфициентах (оба графика, представленные справа, смасштабированы; масштаб указан на гистограмме):

Числа Эйлера I рода (m < 90)
Биномиальные коээфициенты (m < 60)

Полезные факты о числах Эйлера I рода

1. Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:

[math]\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. \, [/math]

2. Сумма всех значений каждого ряда равна [math] n! [/math]:

[math]\sum_{k=0}^{n} \left\langle{n\atop m}\right\rangle = n!,\ n \ge 0, \,[/math]

3. [math]\sum_{m=0}^n (-1)^m {\left\langle{n\atop m}\right\rangle}{n-1\choose m}^{-1}=0.[/math]

Числа Эйлера II рода

Ссылки