Сколькими способами можно уложить N доминошек размером 2x1 на доску размером 2xN клеток?

Пусть ответ на эту задачу #(N). Очевидно, #(1) = 1. Будет удобно считать, что #(0) = 1. Найдём #(N) при N >= 2. Каждый способ замостить доску 2xN получается из предыдущих: либо самая правая стоит вертикально, тогда слева нужно замостить доминошками часть доски размером 2x(N - 1) (это можно сделать #(N - 1) способами), либо справа стоят две доминошки горизонтально, при этом оставшаяся часть имеет размер 2x(N - 2), и её можно покрыть #(N - 2) способами. Значит, #(N) = #(N - 1) + #(N - 2), при этом #(0) = #(1) = 1. Получились числа Фибоначчи Fib(N). Для них, например, существует формула Бине: Fib(N) = (ф^N - (-1/ф)^N)/sqrt(5), где ф - золотое сечение. Ответ. #(N) = Fib(N).