Сколько программ переводят 2 в 26, проходя через 10 и не проходя через 17

Решение по шагам

1. 1

   Шаг 1. Разрезаем задачу в обязательной точке

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

   Если траектория обязана содержать 10, то она однозначно распадается на два независимых участка:

   $$2 \longrightarrow 10 \longrightarrow 26.$$

   Любую программу первого участка можно приписать к любой программе второго, и обратно — так получается каждая нужная программа ровно один раз. По правилу произведения

   $$N = N_{2\to10} \cdot N_{10\to26}.$$

   Важная деталь: на первом участке все числа лежат между 2 и 10, поэтому запрет на 17 там не работает — он ограничивает только второй участок.

2. 2

   Шаг 2. Формула подсчёта путей и учёт запрета

   Для участка с началом $s$ обозначим через $R(n)$ число программ, ведущих из $s$ в $n$. Смотрим на последнюю команду:

   $$R(n) = R(n-1) + \begin{cases} R(n/2), & n \text{ чётно},\\ 0, & n \text{ нечётно},\end{cases}$$

   при этом $R(s) = 1$ (пустая программа), $R(n) = 0$ для всех $n < s$ (такие числа недостижимы) и $R(17) = 0$ — через запрещённое число не проходит ни одна траектория.

   Обнуление $R(17)$ — это не «вычёркивание строки», а именно присвоение нуля: следующие строки таблицы продолжают ссылаться на неё и получают ноль в качестве слагаемого.