"Продвинутый" забор Тома Сойера

Модификация задачи про забор Тома Сойера.

Часто в математике какую то задачу проще решить погрузив ее в более общую задачу.
Покажем это на примере задачи про забор Тома Сойера.

Задача. На складе имеются крашеные доски для постройки зоборов. Каждая доска окрашена в один определенный цвет.
Все доски разбиты на две категории. В 1-й категории собраны доски p цветов, во 2-й - доски q цветов.
При постройке забора следует придерживаться следующего правила. Соседом доски 1-й категории может быть любая доска из обеих категорий, сосед доски 2-й категории должен отличаться от нее цветом.
Сколькими способами можно построить забор из n досок? Считать, что два забора отличны друг от друга, если отличаются цветом доски, стоящие на каком то определенном месте забора.

Решение. Для решения задачи составим схему-деревья.
Строим заборы из одной доски (на бумаге).Каждую доску изобразим прямоугольником соответствующего цвета и расположим их в один ряд. Это корни будущих деревьев. Ясно, что их N₁=n = p+q штук.
Из каждого корня выпустим столько веток, сколько досок совместимы с цветом корня и на концах веток прбибьем доску совместимого цвета. Получим второй ряд. Остальные ряды получим таким же способом.
В к-том ряду будет столько досок, сколько различных заборов можно построить из к досок. Последовательность цветов прибиваемых досок для конкретного забора можно получить руководствуясь этой схемой.
Выбираем перую доску - конкретный корень. Следующие доски (цвета) получаем спускаясь по ветками из этого корня до самого нижнего ряда.
Пусть P(k), Q(k) - числа досок 1-й и 2-й категории соответственно в к-том ряду, N(k) = P(k)+Q(k) - число всех досок в к-том ряду. Поскольку из доски 1-й категории отходят n=p+q ветвей, то в следующем ряду их будет P(k+1)=n*P(k). Аналогично
Q(k+1)=(n-1)*Q(k).
В частности, P(1)=p, Q(1) = q. N(1)=p+q,
P(2)=(p+q)*P(1)= (p+q)*p, Q(2)=(p+q-1)*q, N(2)= (p+q)*p+ Q(2)=(p+q-1)*q ...
Продолжая, получим общую формулу

N(k)=(P+q)^k-1*p+(p+q-1)_k-1*q

Для забора Тома Сойера p=2, q=1.
Тогда N(1)=3, N(2)=8, N(3)=22, N(4)=62. ...
Деревья см. здесь
Забор.zip

1

Сообщение от Symon N(k)=(P+q)k-1*p+(p+q-1)k-1*q

Очепятка. Следует читать:N(k)=(p+q)^k-1p+(p+q-1)^k-1q

0