Підлога має 3 рядки і 10 стовпців. Її повністю, без перекриття, вкривають плитки розміру 1 × 2, які можуть лежати в будь-якій орієнтації. Скільки існує укладань?

Навчання / Бібліотека / Комбінаторика

Укладання ширшої підлоги

КомбінаторикаСкладне

Підлога має $3$ рядки і $10$ стовпців. Її повністю, без перекриття, вкривають плитки розміру $1 \times 2$ , які можуть лежати в будь-якій орієнтації. Скільки існує укладань?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Розріж підлогу по першій вертикальній лінії, яку не перетинає жодна плитка, і порахуй блоки.

Розв’язок

Нехай $a (n)$ — кількість укладань із $n$ стовпцями; воно дорівнює $0$ для непарного $n$ , бо площа непарна, а $a (0) = 1$ .
Розріж по першій вертикальній лінії, яку не перетинає жодна плитка: перший блок ширини $2$ має $3$ укладання, а кожен ширший блок без такої лінії має $2$ укладання, тож $a (n) = 3 a (n - 2) + 2 (a (n - 4) + a (n - 6) + \dots + a (0))$ .
Віднімання тієї самої формули для $n - 2$ дає $a (n) = 4 a (n - 2) - a (n - 4)$ з $a (2) = 3$ .
Значення для $n = 4, 6, 8, 10$ — це $11, 41, 153, 571$ , тож $a (10) = 571$ .

Відповідь: $571$

Наступна задача Назад до бібліотеки