Задание 13: количество программ исполнителя

Разбор: как решать задание 13

Авторское

Исполнитель преобразует число на экране.

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

Первая из этих команд увеличивает число на экране на 1. Вторая заменяет в записи числа каждую цифру 1 на цифру 3; она применяется только к числу, в записи которого есть хотя бы одна цифра 1.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 10 результатом является число 84?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы ABA при исходном числе 9 траектория состоит из чисел 10, 30, 31.