#10 Рекурсии и последовательности

Пусть \(a_n\) - число способов. Тогда \(a_0=1\), \(a_1=1\), и \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_2=2\), \(a_3=3\), \(a_4=5\), \(a_5=8\).

Пусть \(a_n\) - число замощений \(2\times n\). Тогда \(a_0=1\), \(a_1=1\), \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_2=2\), \(a_3=3\), \(a_4=5\).

Пусть \(a_n\) - число таких строк. Тогда \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_2=3\), \(a_3=5\), \(a_4=8\).

Нужно сделать \(2\) шага вправо и \(3\) вверх. Всего \(5\) шагов, выбираем места для \(2\) шагов вправо: \(\binom{5}{2}=10\).

Получаем \(a_3=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\).

При \(a_0=1\), \(a_1=1\), \(a_n=a_{n-1}+a_{n-2}\) получаем: \(1,1,2,3,5,8,13,21,34,55,89\). Значит \(a_{10}=89\).

Для \(2\times n\) домино имеем \(a_n=a_{n-1}+a_{n-2}\). Значения: \(a_0=1\), \(a_1=1\), \(a_2=2\), \(a_3=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\), \(a_7=21\), \(a_8=34\).

Рекурсия \(a_n=a_{n-1}+a_{n-2}\). Получаем \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\), \(a_7=34\), \(a_8=55\).

Всего \(7\) шагов. Выбираем места для \(4\) шагов вправо: \(\binom{7}{4}=35\).

До \((2,1)\): \(\binom{3}{1}=3\). От \((2,1)\) до \((5,4)\): нужно \(3\) вправо и \(3\) вверх, поэтому \(\binom{6}{3}=20\). Итого \(3\cdot20=60\).

Пусть \(a_n\) - число замощений. Тогда \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=1\). Получаем \(a_9=55\).

Пусть \(a_n\) - число таких подмножеств для \(\{1,\ldots,n\}\). Если \(n\) не входит, есть \(a_{n-1}\) способов. Если \(n\) входит, то \(n-1\) не входит, и остается \(a_{n-2}\) способов. Значит \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Поэтому \(a_7=34\).

Если подмножество не содержит \(n\), оно является допустимым подмножеством \(\{1,\ldots,n-1\}\), таких \(a_{n-1}\). Если содержит \(n\), то не содержит \(n-1\), а оставшаяся часть является допустимым подмножеством \(\{1,\ldots,n-2\}\), таких \(a_{n-2}\). Эти случаи не пересекаются и покрывают все варианты, поэтому \(a_n=a_{n-1}+a_{n-2}\).

Если правая верхняя клетка покрыта вертикальным домино, то весь последний столбец закрыт, и остается \(2\times(n-1)\): \(a_{n-1}\) способов. Если она покрыта горизонтальным домино, то правая нижняя клетка тоже должна быть покрыта горизонтальным домино из предпоследнего столбца, и остаются \(2\times(n-2)\): \(a_{n-2}\) способов. Иных вариантов нет, случаи не пересекаются. Значит \(a_n=a_{n-1}+a_{n-2}\).

Пусть \(a_n\) - число строк длины \(n\). Допустимая строка заканчивается на \(1\), \(01\) или \(001\), если смотреть на последний блок нулей. Поэтому \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). Начальные значения \(a_0=1\), \(a_1=2\), \(a_2=4\). Тогда \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\), \(a_{10}=504\).

Всего путей \(\binom{9}{5}=126\). Через \((2,1)\) проходят \(\binom{3}{1}\cdot\binom{6}{3}=3\cdot20=60\). Значит не проходят через точку \(126-60=66\) путей.

Пусть \(a_n\) - число способов. Тогда \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\), \(a_0=1\), \(a_1=1\), \(a_2=2\). Последовательно получаем \(a_3=4\), \(a_4=7\), \(a_5=13\), \(a_6=24\), \(a_7=44\), \(a_8=81\), \(a_9=149\).

Для первой позиции есть \(3\) выбора. Каждая следующая буква должна отличаться от предыдущей, поэтому для нее есть \(2\) выбора. Итого \(3\cdot2^7=384\).

Пусть \(a_n\) - число способов. Тогда \(a_n=a_{n-1}+a_{n-3}\), где \(a_0=1\), \(a_1=1\), \(a_2=1\). Получаем \(a_3=2\), \(a_4=3\), \(a_5=4\), \(a_6=6\), \(a_7=9\), \(a_8=13\), \(a_9=19\), \(a_{10}=28\), \(a_{11}=41\), \(a_{12}=60\).

Пусть \(a_n\) - число замощений. Последняя плитка имеет длину \(1\), \(2\) или \(3\), значит \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). При \(a_0=1\), \(a_1=1\), \(a_2=2\) получаем \(a_8=81\).

Пусть \(a_n\) - число замощений \(2\times n\). Последний столбец может быть вертикальным домино: \(a_{n-1}\). Последние два столбца могут быть двумя горизонтальными домино или квадратом \(2\times2\): \(2a_{n-2}\). Значит \(a_n=a_{n-1}+2a_{n-2}\), \(a_0=1\), \(a_1=1\). Тогда \(a_2=3\), \(a_3=5\), \(a_4=11\), \(a_5=21\), \(a_6=43\).

Пусть \(a_n\) - число таких строк. Как обычно, \(a_n=a_{n-1}+a_{n-2}\): строка заканчивается на \(0\) или на \(01\). Начальные значения \(a_0=1\), \(a_1=2\). Для чисел Фибоначчи \(F_{2}=1\), \(F_{3}=2\). Значит \(a_0=F_2\), \(a_1=F_3\), и обе последовательности удовлетворяют одной рекурсии. Следовательно, \(a_n=F_{n+2}\).

Всего путей \(\binom{8}{4}=70\). Плохие пути - те, которые впервые попали выше диагонали после некоторого шага вверх. Отразим начальный участок до этого шага относительно прямой \(y=x+1\); получается взаимно однозначное соответствие с путями из \((-1,1)\) в \((4,4)\), где нужно сделать \(5\) шагов вправо и \(3\) вверх. Их \(\binom{8}{3}=56\). Значит хороших путей \(70-56=14\).

Пусть \(A_n\) - число полных замощений \(2\times n\), а \(B_n\) - число замощений доски \(2\times n\) с одной удаленной угловой клеткой справа. Тогда \(B_n=A_{n-2}+B_{n-1}\): дырку можно закрыть L-тримино, оставив полный прямоугольник ширины \(n-2\), или продолжить состояние дырки на один столбец. Для полной доски \(A_n=A_{n-1}+A_{n-2}+2B_{n-1}\): последний блок - вертикальное домино, две горизонтальные домино или два симметричных способа закрыть правую часть L-тримино с дырочным состоянием. Начальные значения: \(A_0=1\), \(A_1=1\), \(B_0=0\), \(B_1=0\). Получаем \(B_2=1\), \(A_2=2\); \(B_3=2\), \(A_3=5\); \(B_4=4\), \(A_4=11\); \(B_5=9\), \(A_5=24\); \(B_6=20\), \(A_6=53\). Ответ: \(53\).