Правила умножения и сложения
Сложение. Если объект можно выбрать $a$ способами или $b$ способами, причём случаи не пересекаются, то всего $a + b$ способов.
Пример. Из города А в город Б ведут 3 дороги, из Б в В — 4. Маршрутов А → Б → В: 3 · 4 = 12. А чтобы купить один предмет — ручку (5 видов) или карандаш (4 вида) — способов 5 + 4 = 9.
Проверь себя. Сколько существует четырёхбуквенных слов из букв А, Б, В (буквы могут повторяться)? Ответьте числом.
Ответ: 81
Размещения, перестановки, сочетания
| Ситуация | Формула | Пример |
|---|---|---|
| Слова длины $n$ из $k$ букв, повторы разрешены | $k^n$ | PIN из 4 цифр: $10^4$ |
| Размещения без повторов (важен порядок) | $A_n^k = \dfrac{n!}{(n-k)!}$ | трёхзначные числа из цифр 1–5 без повторов: $5\cdot4\cdot3 = 60$ |
| Перестановки (все элементы, порядок важен) | $P_n = n!$ | 5 книг на полке: $5! = 120$ |
| Сочетания (порядок не важен) | $C_n^k = \dfrac{n!}{k!\,(n-k)!}$ | выбрать 3 из 7: $C_7^3 = 35$ |
ЕГЭ-8: слова с ограничениями и номер слова
Типичные ограничения: «буква встречается ровно $m$ раз», «две гласные не стоят рядом», «все буквы разные». Разбивайте задачу на случаи и применяйте правила умножения и сложения.
Пример. Пятибуквенные слова из букв А, Б, В, Г, где Б встречается ровно 2 раза. Выбираем 2 позиции из 5 для буквы Б: $C_5^2 = 10$. Остальные три места заполняем любыми из трёх букв (А, В, Г): $3^3 = 27$. Итого $10 \cdot 27 = 270$.
Слово РИКА в алфавите А, И, К, Р: цифры Р=3, И=1, К=2, А=0; число $3\cdot4^3 + 1\cdot4^2 + 2\cdot4 + 0 = 216$; номер = $216 + 1 = 217$.
Перебор в Python
Если формула не очевидна, переберите все слова программой. Модуль itertools даёт готовые генераторы.
from itertools import product, permutations
# все слова длины 4 из букв "АИКР", в алфавитном порядке
words = [''.join(w) for w in product('АИКР', repeat=4)]
print(words.index('РИКА') + 1) # номер слова: 217
# все перестановки букв слова
perm = sorted(''.join(p) for p in permutations('АНОРТ'))
print(len(perm)) # 120product(s, repeat=n) — слова с повторами (размещения с повторениями); permutations(s, k) — без повторов; combinations(s, k) — сочетания. Порядок вывода product и permutations — как в алфавитном списке, если исходная строка отсортирована.