23.05 Количество программ из A в B смешанное

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 3.

— если число делится на 3.

Заполним таблицу по формулам до 11:

По условию сказано, что траектория должна содержать число 12. Значит , так как число 13 можно получить только командой 1.

Продолжим заполнять таблицу:

По услолвию сказано, что траектория не должна содержать число 27. Значит .

Заполним таблицу до конца:

Отсюда получаме ответ — 27343

Рекурсия:

def f(c,m):
    if c > m or c == 27:
        return 0
    if c == m:
        return 1
    return f(c+1,m)+f(c+3,m)+f(c*3,m)

print(f(2,12)*f(12,33))