Задача
COM-B1-M10-P021 Квадраты и домино
#21
★★★★☆ Уровень 4 из 5
Доску \(2\times6\) замощают вертикальными домино, парами горизонтальных домино и квадратами \(2\times2\). Сколько замощений возможно?
Последний блок имеет ширину \(1\) или \(2\); блок ширины \(2\) бывает двух типов.
Пусть \(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\).
Первое место, где коэффициент в рекурсии не равен \(1\).