Дано:
- Размеры прямоугольника: 2 х n (где n — натуральное число).
- Замостить прямоугольник домино 2 х 1.
Найти:
- Количество способов замостить прямоугольник 2 х n.
Решение:
1. Обозначим количество способов замостить прямоугольник 2 х n как a(n).
2. Рассмотрим, как можно начать замощение:
- Если первым положить домино вертикально, то оставшаяся часть будет прямоугольником 2 х (n-1). Это дает a(n-1) способов.
- Если первым положить два домино горизонтально, то оставшаяся часть будет прямоугольником 2 х (n-2). Это дает a(n-2) способов.
3. Составим рекуррентное соотношение:
a(n) = a(n-1) + a(n-2)
4. Начальные условия:
- a(1) = 1 (один способ: одно вертикальное домино).
- a(2) = 2 (два способа: два вертикальных или два горизонтальных домино).
5. Вычислим a(n) для различных n:
a(3) = a(2) + a(1) = 2 + 1 = 3
a(4) = a(3) + a(2) = 3 + 2 = 5
a(5) = a(4) + a(3) = 5 + 3 = 8
a(6) = a(5) + a(4) = 8 + 5 = 13
a(7) = a(6) + a(5) = 13 + 8 = 21
a(8) = a(7) + a(6) = 21 + 13 = 34
a(9) = a(8) + a(7) = 34 + 21 = 55
a(10) = a(9) + a(8) = 55 + 34 = 89
6. Таким образом, количество способов замостить прямоугольник 2 х n можно вычислить по рекуррентной формуле, начиная с заданных начальных условий.
Ответ:
Количество способов замостить прямоугольник 2 х n равно a(n), где n — количество колонок. Например, для n = 10, a(10) = 89.