Сколькими способами можно выложить колонну кирпичами

[paul_simon]

Здравствуйте!

Подскажите, пожалуйста, сколькими способами можно выложить $2\times 2\times n$ колонну кирпичами размера $2\times 1\times 1$?

Заранее спасибо!

[jetyb]

Задачу можно решить через рекуррентные соотношения для колонн длины $n,n-1,n-2$.

[RIP]

http://www.research.att.com/~njas/sequences/A006253

[Бодигрим]

Решение можно подсмотреть в Грэхем Р., Кнут Д., Паташник О. — Конкретная математика. Основание информатики, задача 7.23. Там же в основной тексте разобраны более простые задачи этого рода, позволяющие подступиться к предложенной вами.