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

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

Пусть Fᵢ(k) — число способов заполнить первые i мест так, чтобы цифра 7 встретилась ровно 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 = 0; значения 3, 0.
i = 2: a = 7, z = 1; значения 21, 3, 0.
i = 3: a = 7, z = 1; значения 147, 42, 3, 0.
i = 4: a = 7, z = 1; значения 1029, 441, 63, 3, 0.
i = 5: a = 5, z = 1; значения 5145, 3234, 756, 78, 3, 0.

Суммируем разрешённые количества особой цифры: 5145 + 3234 + 756 = 9135.

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

Ответ: 9135.