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