Задача: сколькими способами можно покрыть прямоугольник 2 × n невращающимися доминошками 2 × 1 (доминошки можно класть вертикально или горизонтально)?

Ответ: число разбиений a_n удовлетворяет рекурренте
a_0 = 1, a_1 = 1, an = a{n-1} + a_{n-2} для n ≥ 2,
то есть an = F{n+1} (число Фибоначчи со сдвигом). Ниже — доказательства и дополнения.

1) Доказательство рекуррентного соотношения (разрез по первому столбцу)
Рассмотрим левую часть прямоугольника 2 × n. Первый (самый левый) столбец может быть покрыт либо

одной вертикальной доминошкой (1 способ в этой позиции). Тогда оставшаяся часть — 2 × (n−1), покрытий a_{n-1};либо двумя горизонтальными доминошками (они занимают верх и низ в столбцах 1 и 2). Тогда оставшаяся часть — 2 × (n−2), покрытий a_{n-2}.

Эти два случая взаимоисключают и дают все возможные покрытия, поэтому an = a{n-1} + a_{n-2}. Базовые значения: a_0 = 1 (пустое покрытие) и a_1 = 1 (только одна вертикальная доминошка).

2) Комбинаторный (биномиальный) подсчёт
В каждом покрытии можно рассматривать вертикальную доминошку как кусок «длины 1» по ширине, а пару горизонтальных доминошек, расположенных одна над другой, — как кусок «длины 2». Тогда каждая упаковка — это упорядоченное представление n как суммы 1 и 2 (композиция n с частями 1 и 2). Пусть в покрытии ровно k пар горизонтальных (то есть k «двойных» блоков). Тогда горизонтальные занимают ширину 2k, остаётся n − 2k единичных (вертикальных). Всего блоков (единичных + двойных) = (n − 2k) + k = n − k. Надо выбрать из этих n − k позиций k, где стоят «двойные» блоки: количество = C(n − k, k). Суммируем по k = 0..⌊n/2⌋:
an = Σ{k=0}^{⌊n/2⌋} C(n − k, k).
Эта сумма равна F_{n+1} (можно проверить, что она удовлетворяет той же рекурренте и тому же началу).

3) Замкнутая форма и производящая функция
Из рекурсии следует производящая функция
A(x) = Σ_{n≥0} a_n x^n = 1/(1 − x − x^2).
Из формулы для Фибоначчи (бинетова формула) получаем замкнутую форму
an = F{n+1} = (φ^{n+1} − ψ^{n+1})/√5,
где φ = (1+√5)/2, ψ = (1−√5)/2.

4) Сравнение методов

Рекурсивный (разделяй‑и‑властвуй по краю) — самый простой и наглядный: выбираем, как покрыть первый столбец/ячейку, и сводим задачу к меньшим n. Работает, когда можно выделить локальную конфигурацию, дающую небольшое число вариантов.Комбинаторный (разбиение на блоки, подсчёт позиций) даёт явную сумму в виде биномиального суммирования; полезен, когда покрытия соответствуют композициям/размещениям блоков.Генерирующие функции дают компактное аналитическое представление и позволяют получать явные формулы, асимптотики и т.д.Динамическое программирование / профильные методы: представлять состояние границы (какие клетки заняты/свободны в следующем столбце) и строить переходы — универсальный алгоритмический метод для m × n (фиксированное m).Линейная алгебра (матрица перехода) — для постоянного m переходные матрицы возводят в степень; даёт быстрый расчёт при большом n.Теория совершенных паросочетаний / Pfaffian (Kasteleyn) даёт детерминантные/произведенные формулы для числа покрытий на планарных графах — в частности существует явная (хотя и громоздкая) формула для m × n решётки в общем случае.

5) Обобщения и подходы к подобным задачам

Для высоты 2 (наш случай) всё просто: ответ — Фибоначчи, есть биноминальная сумма и простая рекурсия.Для высоты m > 2: обычно применяют профильный (state) DP. Число состояний порядка 2^m (каждая строка следующего столбца может быть занята/свободна), из них строят матрицу переходов; время O(n · 2^m · poly(m)). Для фиксированного m можно даже найти характерные многочлены и получить линейную рекурсию для зависимостей по n.Для больших прямоугольников и общих плоскостных графов применяют метод Кастелейна/Фишера для вычисления числа совершенных паросочетаний через детерминанты/Pfaffian.Комбинаторные трактовки (биекции с последовательностями, словами, матрицами) часто приводят к удобным формулировкам и явным суммам.

6) Примеры чисел
a_0 = 1, a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 5, a_5 = 8, ... — это последовательность Фибоначчи, смещённая на единицу: an = F{n+1}.

Краткое резюме: рекуррентное соотношение an = a{n-1} + a_{n-2} получается рассмотрением первого столбца; по комбинационной модели—сумма биномиальных коэффициентов Σ C(n − k, k); все эти методы эквивалентны в этом простом случае, а для более сложных высот применяют профильное DP, матричные методы и теорию Pfaffian/детерминантов.