85
правок
Изменения
→Вывод рекуррентной формулы
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">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 - m)</tex><tex dpi = "160">\langle{n\atop m}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
Также для четных <tex dpi = "130">k</tex>:
:<tex dpi = "160">\left\langle{n\atop m}\right\rangle = [k m = 0]</tex>,
Запись [выражение] означает нотацию Айверсона, где
:<tex dpi = "160"> [statement] =</tex><tex dpi = "140"> \begin{cases} 1 & \text{statement} \\ 0 & \text{!statement} \end{cases}</tex>
