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

Длина слова n = 5. Алфавит в порядке возрастания: А, Й, Л, М. Всего букв b = 4; повторения букв разрешены.

Сопоставим буквам цифры от 0 до b − 1: А → 0, Й → 1, Л → 2, М → 3. Алфавитное сравнение слов одинаковой длины совпадает со сравнением позиционных записей: решает первая различающаяся буква слева. Начальные нули сохраняем, поскольку длина слова фиксирована.

Номер в списке на единицу больше значения записи. Для цифр d₁, …, dₙ формула имеет вид N = 1 + d₁ · bⁿ⁻¹ + d₂ · bⁿ⁻² + … + dₙ. Единица нужна потому, что первое слово состоит из минимальных букв, его код равен нулю, а номер равен 1.

Условия отбора: число букв М от 0 до 1 включительно; запрещены соседние пары ЛЛ.

Докажем выбор слова последовательно слева направо. D(q) — число допустимых полных слов с началом q. Для полного слова D равно 1, если выполнены все ограничения, иначе 0. Для более короткого начала D(q) = сумма D(qc) по всем буквам c. Так перебираются все продолжения без пропусков и повторов; запрещённая буква, лишнее вхождение или запрещённая соседняя пара сразу дают ноль.

На каждом шаге выбираем наибольшую букву с положительным числом продолжений. Ниже числа D(qc) перечислены в порядке алфавита АЙЛМ. Нули у всех более подходящих букв доказывают невозможность улучшить выбор.

Начало «пусто»: А: 152, Й: 152, Л: 116, М: 60; выбираем М.
Начало «М»: А: 22, Й: 22, Л: 16, М: 0; выбираем Л.
Начало «МЛ»: А: 8, Й: 8, Л: 0, М: 0; выбираем Й.
Начало «МЛЙ»: А: 3, Й: 3, Л: 2, М: 0; выбираем Л.
Начало «МЛЙЛ»: А: 1, Й: 1, Л: 0, М: 0; выбираем Й.

Полученное слово: МЛЙЛЙ.

Код слова: 32121.
Место 1: М → 3; вклад = 3 · 4⁴ = 768.
Место 2: Л → 2; вклад = 2 · 4³ = 128.
Место 3: Й → 1; вклад = 1 · 4² = 16.
Место 4: Л → 2; вклад = 2 · 4¹ = 8.
Место 5: Й → 1; вклад = 1 · 4⁰ = 1.

N = 1 + 768 + 128 + 16 + 8 + 1 = 922.

Проверка: из N − 1 = 921 последовательным делением с остатком на 4 восстанавливается код 32121 длины 5, то есть слово МЛЙЛЙ. Оно удовлетворяет всем ограничениям. Таблица продолжений исключила все слова, которые могли бы дать лучший номер.

Ответ: 922.