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

Длина слова n = 6. Алфавит в порядке возрастания: Е, И, О, Р, Т, Я. Всего букв b = 6; повторения букв разрешены.

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

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

Условия отбора: первая буква не входит в Е, И, О; число букв Я от 1 до 1 включительно; номер чётный.

Основание b чётное: все позиционные слагаемые, кроме последнего, чётные. Поэтому чётность N определяется числом 1 + dₙ.

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

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

Начало «пусто»: Е: 0, И: 0, О: 0, Р: 1625, Т: 1625, Я: 1250; выбираем Я.
Начало «Я»: Е: 250, И: 250, О: 250, Р: 250, Т: 250, Я: 0; выбираем Т.
Начало «ЯТ»: Е: 50, И: 50, О: 50, Р: 50, Т: 50, Я: 0; выбираем Т.
Начало «ЯТТ»: Е: 10, И: 10, О: 10, Р: 10, Т: 10, Я: 0; выбираем Т.
Начало «ЯТТТ»: Е: 2, И: 2, О: 2, Р: 2, Т: 2, Я: 0; выбираем Т.
Начало «ЯТТТТ»: Е: 0, И: 1, О: 0, Р: 1, Т: 0, Я: 0; выбираем Р.

Полученное слово: ЯТТТТР.

Код слова: 544443.
Место 1: Я → 5; вклад = 5 · 6⁵ = 38880.
Место 2: Т → 4; вклад = 4 · 6⁴ = 5184.
Место 3: Т → 4; вклад = 4 · 6³ = 864.
Место 4: Т → 4; вклад = 4 · 6² = 144.
Место 5: Т → 4; вклад = 4 · 6¹ = 24.
Место 6: Р → 3; вклад = 3 · 6⁰ = 3.

N = 1 + 38880 + 5184 + 864 + 144 + 24 + 3 = 45100.

Проверка: из N − 1 = 45099 последовательным делением с остатком на 6 восстанавливается код 544443 длины 6, то есть слово ЯТТТТР. Оно удовлетворяет всем ограничениям. Таблица продолжений исключила все слова, которые могли бы дать лучший номер.

Ответ: 45100.