5
правок
Изменения
м
Нет описания правки
Пусть у нас есть некая перестановка <tex> \pi = \pi_1, \pi_2\ldots \pi_{n-1} </tex>. Тогда операцией вставки элемента с номером <tex>n</tex> в какую-либо из позиций мы получим <tex>n</tex> перестановок вида <tex>\theta = \theta_1, \theta_2\ldots \theta_p, n, \theta_q\ldots \theta_{n-1}</tex>. Далее рассмотрим два случая:
# Количество подъемов в перестановке <tex>\theta</tex> равно количеству подъемов в <tex>\pi</tex>. Этого можно добиться, вставляя элемент <tex>n</tex> на самое первое место в <tex>\theta</tex> (всего <tex dpi=190>\langle{n - 1\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex>m \times </tex><tex dpi=190> \langle{n- 1\atop m - 1}\rangle </tex> раз).# Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><tex dpi=190>\langle{n- 1\atop m- 1}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
</tex>
Далее рассмотрим все перестановки порядка <tex>3</tex> с одним подъемом, причем операцией вставки <tex>4</tex> мы будем увеличивать количество перестановок подъемов на <tex>1</tex>:
:<tex dpi=190> \left\langle{3\atop 1}\right\rangle</tex> <tex> = 4:</tex>
| style="background:#FFDEAD; color:red;" | '''0'''
|}
== См. также ==
* [[Комбинаторные_объекты#.D0.9F.D0.B5.D1.80.D0.B5.D1.81.D1.82.D0.B0.D0.BD.D0.BE.D0.B2.D0.BA.D0.B8|Перестановки]]
* [[Числа_Стирлинга_первого_рода|Числа Стирлинга первого рода]]
* [[Числа_Стирлинга_второго_рода|Числа Стирлинга второго рода]]
* [[Числа_Каталана|Числа Каталана]]
==Примечания==
