Задание 8: Перебор слов и системы счисления

Типичная формулировка: задан алфавит (обычно цифры системы счисления с основанием $b$, то есть $0,1,\dots,b-1$) и длина слова $n$. Дополнительно накладывается условие — например, конкретная цифра встречается ровно $k$ раз, или сумма одних цифр больше/меньше других, или цифры идут строго по возрастанию/убыванию. Нужно найти количество слов (чисел), удовлетворяющих условию. Задание оценивается в 1 балл, относится к базовому или повышенному уровню сложности, на решение стоит закладывать 3–5 минут.

• Правило умножения: если выбор на каждой из $n$ независимых позиций можно сделать $k_1, k_2, \dots, k_n$ способами, то общее число вариантов равно $k_1 \cdot k_2 \cdot \dots \cdot k_n$.
• Правило сложения: если варианты разбиваются на непересекающиеся группы, общее число равно сумме количеств в каждой группе.
• Число сочетаний: $C_n^k = \dfrac{n!}{k!(n-k)!}$ — количество способов выбрать $k$ элементов из $n$ без учёта порядка.
• Число размещений: $A_n^k = \dfrac{n!}{(n-k)!}$ — количество способов выбрать и упорядочить $k$ элементов из $n$.
• В системе счисления с основанием $b$ используются цифры $0, 1, \dots, b-1$, всего $b$ различных цифр.
• Если речь о $n$-значном числе (а не о произвольной последовательности символов), первая цифра не может быть равна $0$.
• Строго возрастающая или строго убывающая последовательность из $k$ различных цифр однозначно определяется набором этих цифр — порядок в ней фиксирован, поэтому количество таких последовательностей равно $C_b^k$.
• Если условие «символ $x$ встречается ровно $m$ раз», решение строится в два шага: выбор позиций для $x$ — $C_n^m$, и заполнение оставшихся $n-m$ позиций символами из алфавита без $x$.

1. Определить алфавит: если это система счисления с основанием $b$, зафиксировать множество цифр $0,\dots,b-1$.
2. Установить длину слова (числа) $n$.
3. Проверить, идёт ли речь о числе — если да, первая цифра не может быть $0$.
4. Внимательно прочитать условие: есть ли требование «ровно $k$ раз», есть ли требование строгого порядка цифр, есть ли сравнение (сумма, разность) между цифрами на конкретных позициях.
5. Выбрать подходящий метод из раздела выше (произведение, сочетания, выбор позиций, группировка).
6. Разбить задачу на независимые этапы, посчитать количество вариантов на каждом этапе.
7. Перемножить или сложить результаты этапов в зависимости от того, независимы они (умножение) или взаимоисключающие случаи (сложение).
8. Проверить, не пересчитаны ли одинаковые варианты несколько раз, и сверить порядок полученного числа со здравым смыслом.