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

Система счисления имеет основание 9, длина записи 5. Цифра 3 встречается ровно один раз. Её соседи не могут входить в набор 5, 6, 7, 8. Первая цифра должна быть ненулевой.

Разобьём варианты по положению особого символа. При фиксированном положении исключаем его из всех остальных мест. Затем применяем ограничения начала, конца и соседства. После этого выборы на разных местах независимы: число вариантов равно произведению размеров разрешённых наборов.

В каждой строке слева направо перечислены разрешённые символы на всех местах. Пустой набор означает, что случай невозможен. Одноэлементный набор фиксирует нужный символ. Повторение обычного символа допускается и не создаёт дополнительного запрета.

Положение 1: {3}; {0, 1, 2, 4}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}.
Способов = 1 · 4 · 8 · 8 · 8 = 2048.

Положение 2: {1, 2, 4}; {3}; {0, 1, 2, 4}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}.
Способов = 3 · 1 · 4 · 8 · 8 = 768.

Положение 3: {1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4}; {3}; {0, 1, 2, 4}; {0, 1, 2, 4, 5, 6, 7, 8}.
Способов = 7 · 4 · 1 · 4 · 8 = 896.

Положение 4: {1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4}; {3}; {0, 1, 2, 4}.
Способов = 7 · 8 · 4 · 1 · 4 = 896.

Положение 5: {1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4, 5, 6, 7, 8}; {0, 1, 2, 4}; {3}.
Способов = 7 · 8 · 8 · 4 · 1 = 1792.

Всего = 2048 + 768 + 896 + 896 + 1792 = 6400.

Проверка: непосредственный перебор всех записей заданной длины с проверкой количества символов и ограничений даёт 6400. Случаи не пересекаются: единственный особый символ однозначно задаёт свою позицию. Внутри случая каждый выбор наборов соответствует ровно одной последовательности. Поэтому правило умножения внутри строк и правило сложения между строками применены корректно.

Ответ: 6400.