Три размера шага на лестнице

Если убрать последний шаг, на какой ступени мог закончиться оставшийся путь?

Разбейте пути на три группы по последнему шагу. Как выразить размер каждой группы через числа способов для меньших высот?

1. Задаём начальные значения

Пусть $A(n)$ — число способов подняться ровно на $n$ ступеней. Сначала перечислим короткие пути:

• на одну ступень: только шаг $1$, поэтому $A(1)=1$;
• на две: шаг $2$ или два шага $1+1$, поэтому $A(2)=2$.

Ещё понадобится $A(0)=1$: не сделать ни одного шага — единственный пустой путь. Он нужен, например, перед одним прыжком сразу на третью ступень.

2. Разбиваем пути по последнему шагу

Вместо перечисления всех длинных путей посмотрим, чем путь заканчивается. Если убрать последний шаг, получится уже более короткая задача того же вида.

При $n\ge3$ последний шаг равен 1, 2 или 3. До него нужно подняться соответственно на $n-1$, $n-2$ или $n-3$ ступеней. К каждому короткому пути можно дописать соответствующий последний шаг. Группы не пересекаются, поскольку последние шаги различны. Поэтому

$$\begin{aligned} A(n)&=A(n-1)+A(n-2)\\ &\quad+A(n-3). \end{aligned}$$

Например, пути на три ступени группируются так:

• последний шаг 1: $1+1+1$ и $2+1$ — два пути из $A(2)$;
• последний шаг 2: $1+2$ — один путь из $A(1)$;
• последний шаг 3: $3$ — один путь из $A(0)$.

Итого $A(3)=2+1+1=4$. Порядок шагов учитывается.

3. Последовательно заполняем таблицу

Каждое новое число — сумма предыдущих трёх. Например,

$$A(6)=13+7+4=24.$$

Последний переход даёт

$$\begin{aligned} A(13)&=927+504+274\\ &=1705. \end{aligned}$$

$1705$

Последний шаг превращает полный список путей в три непересекающихся группы, которые уже посчитаны на меньших высотах.

Если объект строится последовательностью разрешённых ходов, группируйте его по последнему ходу и считайте более короткие объекты.

Считать только количества шагов каждого размера, забывая, что $1+2$ и $2+1$ — разные способы.

Если в новой задаче нужно посчитать последовательности разрешённых ходов, попробуйте разделить их по последнему ходу. После его удаления должна остаться такая же задача меньшего размера. Проверьте, что группы не пересекаются и охватывают все варианты; затем задайте начальные значения, не забыв пустую последовательность.

Все пути имеют ровно один из трёх последних шагов; удаление/добавление последнего шага — взаимно обратные операции. Граница $n=0$ задана пустым путём. Число 1705 дополнительно подтверждено суммой мультиномиальных коэффициентов по всем неотрицательным решениям $n_1+2n_2+3n_3=13$.