Комбинаторика и порядок слов
Правила суммы и произведения, выбор позиций и связь алфавитного списка с позиционной записью числа.
Подсчёт последовательностей опирается на два вопроса: сколько вариантов есть на каждом шаге и не посчитан ли один результат несколько раз. Упорядоченный список добавляет третий вопрос: сколько последовательностей находится перед выбранной. Одни и те же правила помогают считать слова, цифровые коды и записи чисел.
Алфавит, слово и запись числа
Алфавит — набор допустимых символов. Его размер обозначается q. Слово длины n — последовательность из n символов алфавита. Порядок существенен: АБ и БА — разные слова. Повторение символа допустимо, пока условие его не запрещает.
Цифровой код и запись числа могут подчиняться разным правилам. Для кода начало 0 само по себе допустимо. Для многозначного числа начальный ноль запрещён, потому что не создаёт нового разряда. Например, 007 — трёхсимвольная строка, но запись однозначного числа 7 с лишними нулями.
Когда количества перемножаются
Правило произведения: если первый шаг имеет a вариантов и после каждого из них второй шаг имеет b вариантов, всего есть ab результатов. Для трёх позиций из букв А и Б это 2\cdot2\cdot2=8 слов. В общем случае без ограничений получается q^n.
Без повторений число доступных символов уменьшается: для слова длины n\leq q получается q(q-1)\cdots(q-n+1). Это выбор с учётом порядка. Если четыре позиции заполняются четырьмя различными символами, число порядков равно 4\cdot3\cdot2\cdot1=24.
При зависимых ограничениях количество продолжений может различаться. Тогда нельзя просто перемножить размеры исходных наборов. Например, для двухзначных десятичных чисел с различными чётными цифрами первая позиция имеет четыре варианта, а вторая — тоже четыре: ноль разрешён, использованная цифра исключена. Получается 4\cdot4=16, а не 5\cdot5.
Когда количества складываются
Правило суммы применяется к непересекающимся случаям. Если слово содержит не более одной А, можно отдельно посчитать слова без А и с ровно одной А. Они не пересекаются, поэтому их количества складываются.
В собственном учебном примере из А, Б, В составляются трёхбуквенные слова. Без А получается 2^3=8 слов. С одной А выбираются её место и две другие буквы: 3\cdot2^2=12. Всего с не более одной А — 8+12=20 слов. Подсчёт только второго случая потерял бы слова, где А отсутствует.
Иногда проще считать дополнение: из всех слов вычесть неподходящие. Например, число слов с хотя бы одной А равно 3^3-2^3=19. Из 27 слов удалены ровно те восемь, в которых А нет.
Выбор мест для особого символа
Если одна конкретная буква должна встречаться ровно r раз, сначала выбираются её r позиций среди n. Количество таких наборов мест обозначается \binom nr и называется числом сочетаний.
На оставшиеся места эта буква уже не допускается. При алфавите из q символов и разрешённых повторениях остальных букв получается \binom nr(q-1)^{n-r}. Например, ровно две А в четырёхбуквенных словах из А, Б, В дают шесть пар мест: 12, 13, 14, 23, 24, 34. Для каждой пары остальные места имеют 2^2 заполнения; всего 6\cdot4=24.
Формула предполагает, что нет дополнительных запретов на первую позицию или соседство. Если А нельзя ставить рядом, из шести пар мест остаются только 13, 14 и 24; число слов уменьшается до 3\cdot4=12. Сначала выбираются допустимые места, затем заполняются остальные.
Почему алфавитный список похож на систему счисления
При лексикографическом порядке слова одинаковой длины сравниваются слева направо до первого различия. Раньше стоит слово, у которого в этой позиции символ раньше в заданном алфавите. Символам назначаются коды 0,1,\ldots,q-1 в том же порядке.
Пусть коды букв слова — d_1,d_2,\ldots,d_n. Перед ним стоят все слова с меньшей первой буквой: d_1q^{n-1}. Затем добавляются слова с той же первой, но меньшей второй буквой: d_2q^{n-2}. Продолжение рассуждения даёт число предшествующих слов:
z=d_1q^{n-1}+d_2q^{n-2}+\cdots+d_n.
Это значение позиционной записи по основанию q. Если нумерация начинается с 1, номер равен z+1. Для обратного перехода из номера вычитается единица, результат переводится в основание q и дополняется слева нулями до n цифр.
Собственный пример для алфавита А, Б, В: слово БАВ имеет цифры 102_3. Перед ним 1\cdot9+0\cdot3+2=11 слов, поэтому его номер 12. Соответствие работает для полного списка слов фиксированной длины с разрешёнными повторениями. Если список сначала сокращён дополнительными ограничениями, простая формула номера в сокращённом списке уже не действует.
Чётность номера и проверяемый перебор
При чётном q все положительные степени основания чётные. Поэтому чётность z определяется последней цифрой, а чётность номера z+1 противоположна ей. При нечётном основании все разрядные веса нечётные; чётность значения определяется суммой всех цифр.
Перебор позволяет применить ограничения непосредственно, если число вариантов достаточно мало. Каждая последовательность должна возникнуть ровно один раз, а проверка должна сохранять слова «ровно», «не более», «не менее» и оба направления соседства. Для поиска номера нумеруется исходный список; для подсчёта увеличивается число прошедших проверку последовательностей. Ручной подсчёт по случаям даёт независимую проверку программы.
Как по алфавитному порядку восстановить номер слова и учесть чётность этого номера? Как отдельно посчитать числа с различными цифрами и запретом соседства? Эти способы применяются в статье «Подсчёт слов и чисел, порядок в списке».