Задание EGEINF591A7D: Подсчёт слов и последовательностей

Основание системы 9, число разрядов 6. Цифра 8 должна встретиться от 2 до 6 раз включительно. Ведущий ноль исключаем. Разрешённые цифры первого места: 2, 4, 6, 8; последнего: 0, 3, 4, 5, 6, 7, 8. На промежуточных местах разрешены все цифры от 0 до 8.

Пусть Fᵢ(k) — число способов заполнить первые i мест так, чтобы цифра 8 встретилась ровно k раз. До заполнения F₀(0) = 1, остальные значения нулевые. Для очередного места обозначим через a число разрешённых обычных цифр, через z — возможность поставить особую цифру (0 или 1).

Общая формула перехода: Fᵢ(k) = a · Fᵢ₋₁(k) + z · Fᵢ₋₁(k − 1). Первое слагаемое добавляет обычную цифру, второе добавляет особую и увеличивает её количество на один. Для отрицательных k принимаем значение ноль. Случаи не пересекаются и охватывают все способы заполнить очередное место.

В строке i указаны значения Fᵢ(0), …, Fᵢ(i):
i = 1: a = 3, z = 1; значения 3, 1.
i = 2: a = 8, z = 1; значения 24, 11, 1.
i = 3: a = 8, z = 1; значения 192, 112, 19, 1.
i = 4: a = 8, z = 1; значения 1536, 1088, 264, 27, 1.
i = 5: a = 8, z = 1; значения 12288, 10240, 3200, 480, 35, 1.
i = 6: a = 6, z = 1; значения 73728, 73728, 29440, 6080, 690, 41, 1.

Суммируем разрешённые количества особой цифры: 29440 + 6080 + 690 + 41 + 1 = 36252.

Проверка: сумма всей последней строки равна 183708 = 4 · 9 · 9 · 9 · 9 · 7, то есть числу всех записей с допустимыми крайними цифрами. Независимый прямой перебор с ограничением на количество цифр 8 даёт 36252. Числа с ведущим нулём в расчёт не попадают.

Ответ: 36252.