определить количество способов

[Алька2206]

нужно написать программу на Delphi, которая определяет количество способов выложить пол 4х10 плиткой размером 1х2.
Желательно сделать с помощью чисел Фибоначчи, но каким образом, не знаю. Да и если даже делать перебором, не пойму как это сделать.
Заранее спасибо )

[evg_m]

размер и число вариантов
(1,2) =1
(2,2) =2
(3,2) =3
(4,2) =5
(4,3) =8
...........
продолжаем, замечаем закономерность, доказываем ее, получаем ответ.

[Алька2206]

если продолжить, получается что если квадрат 4х4, то количество способов 13.. но их гораздо больше, я проверяла.
такое соотношение верно для прямоугольников 2хN, где количество способов равно N-му номеру чисел Фибоначчи

[vlad_light]

У нас прямоугольник 4х10, что эквивалентно двум 2х10. Назовём н-ое число последовательности Фибоначчи F(n) Тогда кол-во вариантов для одного прямоугольника равно F(10), поскольку его размер равен 2х10. Для второго прямоугольника - аналогично. Теперь зафиксируем один способ расстановки в 1-ом прямоугольнике, а во втором переберём все возможные варианты. Тоже самое проделаем для второго, третьего и т. д. В итоге у нас получится F(n) вариантов выбора для 1-ого прямоугольника по F(n) вариантов размещения второго. Ответ: F(n)*F(n)=F(n)^2.

[Алька2206]

все равно это будет не все количество вариантов. вы поделили прямоугольник на два вертикальных, а можно также выделить один прямоугольник 2х10 посередине, тогда по бокам останутся два прямоугольника 1х10. И некоторые из этих вариантов не входят в число тех, про которые говорите вы.
получается, количество F[10]^2+F[10], но как учесть повторяющиеся и, следовательно, избавиться от них?

[Somebody]

Рассмотрим 3 случая на краю:
tile.png
Количество способов для случая t размера x (x - длина части шириной 4).

f(x, 0) = f(x - 1, 1) + f(x - 2, 2) + f(x - 2, 1) + f(x - 2, 0);
f(x, 1) = f(x, 0) + f(x - 1, 1);
f(x, 2) = f(x, 0) + f(x - 2, 2);

Для 4×4 будет 36 вариантов - проверено вручную.

О, нашёл:
http://oeis.org/classic/b005178.txt
Последовательность A005178
a(n)=a(n-1)+5a(n-2)+a(n-3)-a(n-4)

[Алька2206]

спасибо, но может кто-то сможет помочь с выводом формулы через производящую функцию? буду очень признательна.