Решать перебором или как?

[Nikita432472]

Решать перебором или как? Такого типа задачи.
Сколько имеется разбиений отрезка длины 8 на отрезки длины 1, 2 и 3? (Разбиения, отли-
чающиеся порядком следования отрезков, считаются различными.)
Сделал перебором.

[iou]

Пусть $k_n -$ количество таких разбиений для отрезка длины $n \ge 4,$ тогда заметим, что $k_n=k_{n-1}+k_{n-2}+k_{n-3},$ поэтому достаточно посчитать $k_1, ~k_2$ и $k_3,$ а их просто посчитать.

[Nikita432472]

Точно! Спасибо.

[Andrey A]

Красиво. Для произвольных отрезков $a,b,c,d,...$ имеем $k_n=k_{n-a}+k_{n-b}+k_{n-c}+k_{n-d}+...$ , причем количество начальных членов, вычисляемых "вручную" определяется длиной наибольшего отрезка. Не ошибся?

p.s. $a,b,c,d,...$ попарно различны. $n$-ое Фибоначчи можно определить как число композиций $n-1$ из двоек и едениц.

[Andrey A]

ps ps

Тут даже не требуется "ручных" вычислений. Всё отлично формализуется правилом $k_n=k_{n-a}+k_{n-b}+k_{n-c}+k_{n-d}+...$ , если вести вычисления от $n=0$ и принять $t_0=1, t_{n<0}=0$.

Пример для $a=3, b=5, c=7, b=11$:

$n=0.$ $t_0=1$.

$n=1.\ 1-3=-2, 1-5=-4,1-7=-6, 1-11=-10;\ \mbox {t_1=t_{-2}+t_{-4}+t_{-6}+t_{-10}=0+0+0+0=0}$

$n=2.$ Аналогично $t_2=t_{-1}+t_{-3}+t_{-5}+t_{-9}=0+0+0+0=0$

$n=3.$ $t_3=t_{0}+t_{-2}+t_{-4}+t_{-8}=1+0+0+0=1$ И т.д.