Пусть у нас есть некая перестановка <tex> \pi = \pi_1, \pi_2...\pi_{n-1} </tex>. Тогда операцией вставки элемента с номером n в какую-либо из позиций мы получим <tex>n</tex> перестановок вида <tex>\theta = \theta_1, \theta_2...\theta_p, n, \theta_q...\theta_{n-1}</tex>. Далее рассмотрим два случая:
1. # Количество подъемов в перестановке <tex>\theta</tex> равно количеству подъемов в <tex>\pi</tex>. Этого можно добиться, вставляя элемент <tex>n</tex> на самое первое место в <tex>\theta</tex> (всего <tex>\langle{n\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex>m \times </tex><tex> \langle{n\atop m}\rangle </tex> раз). 2. # Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><tex>\langle{n\atop m}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
