Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: Прибавить 1 Умножить

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: Прибавить 1 Умножить на 2 Умножить на 3 Сколько существует программ, для которых при исходном числе 1 результатом является число 39 и при этом траектория вычислений содержит число 12 и не содержит числа 18?

Нужно сначала преобразовать 1 в 12, а затем 12 в 39, не заходя в 18.
Пусть F(b) – количество программ, преобразующих исходное число 1 в число b. Это число равно сумме F(x) для всех х, из которых можно одной командой получить b. Будем находить значения F(b) последовательно для всех от 1 до 12:
F(1) = 1 (единственная программа, сохраняющая исходное число, – пустая)
F(2) = F(1) + F(1) = 2 (от 1 можно перейти к 2 двумя способами)
F(3) = F(2) + F(1) = 2 + 1 = 3
F(4) = F(3) + F(2) = 3 + 2 = 5
F(5) = F(4) = 5
F(6) = F(5) + F(3) + F(2) = 5 + 3 + 2 = 10
F(7) = F(6) = 10
F(8) = F(7) + F(4) = 10 + 5 = 15
F(9) = F(8) + F(3) = 15 + 3 = 18
F(10) = F(9) + F(5) = 18 + 5 = 23
F(11) = F(10) = 23
F(12) = F(11) + F(6) + F(4) = 23 + 10 + 5 = 38
Рассмотрим теперь переход от 12 к 39

. «Обойти» число 18 можно следующим образом:
можно умножить 12 на 2 или на 3, получится 24 или 36. В любом из этих случаев дальнейшее умножение невозможно, т.к. получится число больше 39, поэтому придётся прибавлять по 1 до 39. Это два варианта получения числа 39.
можно увеличить 12 на 1, получится 13