Изменения
→Вывод рекуррентной формулы
Пусть у нас есть некая перестановка <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\atop m- 1}\rangle </tex> раз).
# Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><tex dpi=190>\langle{n\atop m}\rangle</tex>.
