Количество замощений

[khammisha]

Пусть $x_{n}$ — количество способов замостить прямоугольник 1 × n плитками 1 × 1 (которые бывают a=1 разных цветов), плитками 1 × 2 (которые бывают b=10 разных цветов) и плитками 1 × 3 (которые бывают c=8 разных цветов)

Замощение производится без наложения одной плитки на другую; в наличии имеется неограниченное количество плиток каждого размера и каждого цвета
(но если c = 0, то это означает, что плиток 1×3 в наличии нет).
1) Вывести рекуррентное соотношение для чисел $x_{n}$

Пытаюсь сделать явно:
$x_{0}=0$
$x_{1}=1$, тк только цветами a можно замостить
$x_{2}=11$, тк есть варианты aa-1шт, b-10 штук
$x_{3}=29$, тк есть варианты: aaa-1шт, ab-10шт, ba-10 шт, c-8 шт
$x_{4}=47$, тк есть варианты: aaaa-1шт, ac-8шт, ca-8шт, aab-10шт, baa-10шт, aba-10шт

никак не могу найти общую закономерность. Можете подсказать что я делаю не так?

[mihaild]

khammisha в сообщении #1521143 писал(а):

Можете подсказать что я делаю не так?

Ищете закономерность вместо поиска формулы.

(Оффтоп)

А еще неправильно записываете формулы.

Пусть мы хотим замостить прямоугольник $1 \times 50$, т.е. найти $x_{50}$. Давайте посмотрим на самую левую плитку - какой она может оказаться? Для каждого варианта самой плитки - какую часть прямоугольника нам останется замостить, и сколькими способами это можно будет сделать? ($x_i$ при $i < 50$ считаем известными)

khammisha в сообщении #1521143 писал(а):

$x_{0}=0$

Неправда. Пустой прямоугольник замостить очень легко, нужно просто ничего не делать (и это единственный способ его замостить).

[TOTAL]

khammisha в сообщении #1521143 писал(а):

(но если c = 0, то это означает, что плиток 1×3 в наличии нет).

Как нет в наличии? Ведь всего навалом, в неограниченном количестве?

[mihaild]

(Оффтоп)

TOTAL в сообщении #1521147 писал(а):

Ведь всего навалом, в неограниченном количестве?

В наличии, конечно. Можете взять сколько хотите плиток любого из $0$ цветов.