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

Основание системы 8, число разрядов 5. Цифра 7 должна встретиться от 0 до 2 раз включительно. Ведущий ноль исключаем. Разрешённые цифры первого места: 1, 2, 3, 4, 5, 6, 7; последнего: 0, 1, 2, 3, 4, 5, 6, 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 = 6, z = 1; значения 6, 1.
i = 2: a = 7, z = 1; значения 42, 13, 1.
i = 3: a = 7, z = 1; значения 294, 133, 20, 1.
i = 4: a = 7, z = 1; значения 2058, 1225, 273, 27, 1.
i = 5: a = 7, z = 1; значения 14406, 10633, 3136, 462, 34, 1.

Суммируем разрешённые количества особой цифры: 14406 + 10633 + 3136 = 28175.

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

Ответ: 28175.