Моделирование и обработка данных
Комбинаторика: подсчёт слов и кодов
Два главных правила
- Правило умножения. Если первый выбор можно сделать a способами, а второй — b способами независимо от первого, то пара выборов делается
a · bспособами. - Правило сложения. Если объект можно выбрать a способами или b способами и эти способы не пересекаются, всего их
a + b.
Формулы
| Что считаем | Формула | Пример |
|---|---|---|
| Слова длины k из n букв, буквы можно повторять | n^k | 3 буквы, длина 4: 3⁴ = 81 |
| Перестановки n различных элементов | n! | 5! = 120 |
| Размещения: k разных из n, порядок важен | A(n, k) = n! / (n − k)! | A(5, 2) = 20 |
| Сочетания: k из n, порядок не важен | C(n, k) = n! / (k! · (n − k)!) | C(5, 2) = 10 |
| Перестановки с повторениями | n! / (k₁! · k₂! · …) | слово из букв Л, О, Л, А: 4! / 2! = 12 |
Идея решения задач № 8
Часто нужно посчитать слова длины k из заданного алфавита, которые удовлетворяют ограничению: определённая буква стоит или не стоит на каком-то месте, две одинаковые буквы не стоят рядом, слово содержит нужную букву и т. п.
Пошагово по позициям:
- Определите, сколько вариантов у каждой позиции с учётом ограничения.
- Если выборы независимы, перемножьте.
- Если ограничения связывают позиции, разбейте задачу на случаи и сложите.
Пример. Сколько слов длины 4 можно составить из букв А, Б, В так, чтобы никакие две соседние буквы не были одинаковыми?
Первую букву выбираем 3 способами. Каждую следующую — любую, кроме предыдущей, то есть 2 способами. Всего 3 · 2 · 2 · 2 = 24.
Проверка перебором
Для небольших размеров перебор на Python — самый быстрый способ получить ответ или проверить рассуждение.
from itertools import product, permutations
from math import comb, factorial
# Слова длины 4 из А, Б, В без одинаковых соседних букв
count = 0
for w in product('АБВ', repeat=4):
if all(w[i] != w[i + 1] for i in range(3)):
count += 1
print(count) # 24
# Различные перестановки букв слова ЛОЛА
print(len(set(permutations('ЛОЛА')))) # 12
print(factorial(5), comb(5, 2)) # 120 10Если в условии нужны слова с дополнительным свойством («есть хотя бы одна буква А», «ровно две Б»), добавьте это свойство в условие if и посчитайте.
Типичные ошибки
- Считают порядок существенным там, где он не важен (путают размещения и сочетания).
- Не учитывают, что одинаковые буквы в слове дают одинаковые перестановки: нужно делить на факториалы повторов.
- Складывают числа вместо умножения для независимых выборов, и наоборот.