85
правок
Изменения
Новая страница: «'''''Числа Эйлера I рода''''' (''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]...»
'''''Числа Эйлера I рода''''' (''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]] чисел от 1 до ''n'' таких, что в каждой из них существует ровно ''m'' подъемов. Числа Эйлера I рода обозначают как <tex dpi = "160">\langle{n\atop m}\rangle </tex> или же <tex dpi = "160">A(n, m)</tex>.
{{Определение
|definition=
Пусть <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">k \times </tex><tex dpi = "160"> \langle{n\atop m}\rangle </tex> раз).
2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex dpi = "130">n</tex> между последним символом <tex dpi = "130">a</tex> любого подъема и <tex dpi = "130">b</tex> (если <tex dpi = "130">(a, b)</tex> - не подъем) или после элемента перестановки со значением <tex dpi = "130">n-1</tex>. Таких элементов, как не трудно догадаться, будет <tex dpi = "130">(n - k)</tex><tex dpi = "160">\langle{n\atop m}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
<tex dpi = "180">\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 = "180">\langle{n\atop m}\rangle = 0</tex>, если <tex dpi = "130">m < 0</tex> или если <tex dpi = "130">n = 0</tex>;
{{Определение
|definition=
Пусть <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">k \times </tex><tex dpi = "160"> \langle{n\atop m}\rangle </tex> раз).
2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex dpi = "130">n</tex> между последним символом <tex dpi = "130">a</tex> любого подъема и <tex dpi = "130">b</tex> (если <tex dpi = "130">(a, b)</tex> - не подъем) или после элемента перестановки со значением <tex dpi = "130">n-1</tex>. Таких элементов, как не трудно догадаться, будет <tex dpi = "130">(n - k)</tex><tex dpi = "160">\langle{n\atop m}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
<tex dpi = "180">\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 = "180">\langle{n\atop m}\rangle = 0</tex>, если <tex dpi = "130">m < 0</tex> или если <tex dpi = "130">n = 0</tex>;
