Сколькими способами можно уложить 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).