комбинаторика - Как решать рекуррентные соотношения?

Здесь тоже получается рекуррентная последовательность, но несколько более сложная.

Обычно в таких случаях приходится рассматривать несколько "близкородственных" последовательностей, выражая их друг через друга. Прежде всего, пусть $%a_n$% есть количество тех расстановок, которое мы ищем. Будем их анализировать с конца. Число $%n$% находится либо на последнем месте, и тогда это даёт $%a_{n-1}$% расстановок, или на предпоследнем, или на третьем с конца.

Рассмотрим случай, когда $%n$% предпоследнее. Тогда у нас имеется $%n-1$% мест, на которых стоят числа от $%1$% до $%n-1$%, причём места мы нумеруем по порядку, и тогда ситуация слегка отличается от того, что было в оригинале. А именно, число $%n-3$% в исходной ситуации не могло быть на последнем месте. Так как у нас последнее место в результате перенумерации стало считаться $%(n-1)$%-м, появляется ограничение, что $%n-3$% не находится на $%(n-1)$%-м месте, а все остальные ограничения те же. Тогда количество случаев равно $%b_{n-1}$%, где через $%b_n$% мы обозначаем количество допустимых расстановок на $%n$% символах, в которых $%n-2$% не занимает последнее место.

Теперь проанализируем случай, когда $%n$% в исходной перестановке идёт третьим с конца. Здесь $%n-3$% не может идти на последнем месте, а $%n-4$% не идёт ни на одном из двух последних. Как и выше, сдвигаем номера мест, считая, что они занумерованы подряд числами от $%1$% до $%n-1$% после исключения символа $%n$% из перестановки. Тогда новое ограничение гласит, что $%n-3$% не занимает $%(n-1)$%-е место, а $%n-4$% не занимает $%(n-2)$%-е место. Эту величину мы считаем равной $%c_{n-1}$%, где через $%c_n$% обозначено число перестановок на $%n$% символах с дополнительными ограничениями, что $%n-2$% не может быть на $%n$%-м месте, а $%n-3$% не стоит на $%(n-1)$%-м.

Из сказанного выше следует, что $%a_n=a_{n-1}+b_{n-1}+c_{n-1}$%. Свяжем теперь аналогичными рекуррентными соотношениями две другие последовательности.

Пусть имеется перестановка на $%n$% символах, где $%n-2$% не находится на последнем месте. Если на последнем месте находится $%n$%, то предыдущие символы расставляются $%a_{n-1}$% способами, так как дополнительное ограничение исчезает. Пусть $%n$% находится на предпоследнем месте. Тогда на самом последнем может идти только $%n-1$%, и вариантов получается $%a_{n-2}$%. Наконец, если $%n$% находится на третьем справа месте, то на последнем месте по-прежнему $%n-1$%, а второе справа место не может занимать $%n-4$%. Легко видеть, что после обычного сдвига мест мы приходим к величине $%b_{n-2}$%, откуда $%b_n=a_{n-1}+a_{n-2}+b_{n-2}$%.

Наконец, анализируем соотношение для $%c_n$%. Если $%n$% находится на последнем месте, то одно из ограничений пропадает, и оказывается, что $%n-3$% не занимает $%(n-1)$%-е место; таких вариантов $%b_{n-1}$%. Если $%n$% на предпоследнем месте, то в самом конце стоит $%n-1$%, и вариантов оказывается $%a_{n-2}$%. Наконец, если $%n$% на третьем месте справа, то последним идёт $%n-1$%, а между ними может быть только $%n-2$%, что приводит к $%a_{n-3}$% вариантам и формуле $%c_n=b_{n-1}+a_{n-2}+a_{n-3}$%.

Теперь всё определено однозначно, и остальное лишь дело техники. Фактически, здесь всё сводится к задачам о матрицах. Из формул, указанных выше, путём исключения неизвестных можно прийти к формуле $%a_{n+1}=a_n+2(a_{n-1}+a_{n-2}+a_{n+3})-(a_{n-4}+a_{n-5})$%. Характеристическое уравнение здесь разложимо на множители, и если этим воспользоваться, то получается далее не упрощаемое рекуррентное выражение одного члена последовательности через пять предыдущих. Вот как оно выглядит: $%a_{n+5}=2a_{n+4}+2a_{n+2}-a_n$%. Сама последовательность, начиная с нулевого члена, при этом такова: 1, 1, 2, 6, 14, 31, 73, 172, ... и так далее. Заметим, что только $%a_0=a_1=1$% можно задавать в качестве начальных условий, а далее действует рекуррентное соотношение, если члены с отрицательными номерами считать равными нулю.