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

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

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

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

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

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

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

Начало «пусто»: А: 24, Л: 0, П: 48, Ц: 80, Я: 48; выбираем А.
Начало «А»: А: 0, Л: 0, П: 6, Ц: 12, Я: 6; выбираем П.
Начало «АП»: А: 0, Л: 0, П: 1, Ц: 4, Я: 1; выбираем П.
Начало «АПП»: А: 0, Л: 0, П: 0, Ц: 1, Я: 0; выбираем Ц.
Начало «АППЦ»: А: 0, Л: 0, П: 0, Ц: 1, Я: 0; выбираем Ц.

Полученное слово: АППЦЦ.

Код слова: 02233.
Место 1: А → 0; вклад = 0 · 5⁴ = 0.
Место 2: П → 2; вклад = 2 · 5³ = 250.
Место 3: П → 2; вклад = 2 · 5² = 50.
Место 4: Ц → 3; вклад = 3 · 5¹ = 15.
Место 5: Ц → 3; вклад = 3 · 5⁰ = 3.

N = 1 + 0 + 250 + 50 + 15 + 3 = 319.

Проверка: из N − 1 = 318 последовательным делением с остатком на 5 восстанавливается код 02233 длины 5, то есть слово АППЦЦ. Оно удовлетворяет всем ограничениям. Таблица продолжений исключила все слова, которые могли бы дать лучший номер.

Ответ: 319.