8 мин чтениякомбинаторикаперестановкисочетаниясловаКЕГЭ

Комбинаторика и подсчёт вариантов

Правила суммы и произведения, перестановки, размещения, сочетания, подсчёт слов и кодов, перебор через itertools.

Открываем тему…

Основные правила

Правило произведения: если выбор можно выполнить в k шагов и на i-м шаге есть nᵢ вариантов независимо от предыдущих, всего вариантов n₁·n₂·…·n_k. Правило суммы: если варианты разбиваются на непересекающиеся группы, их количества складываются. Включения-исключения нужны, когда группы пересекаются.

P_n=n!,\qquad A_n^k=\frac{n!}{(n-k)!},\qquad C_n^k=\frac{n!}{k!(n-k)!}

Перестановки, размещения, сочетания.

|A\cup B|=|A|+|B|-|A\cap B|

Принцип включения-исключения для двух множеств.

Слова длины k над алфавитом из m букв: mᵏ (повторения разрешены).
Слова из различных букв: размещения A_m^k.
Слова из букв с повторами по числам k₁, k₂, …: n! / (k₁!·k₂!·…).
Условие «не начинается с…» удобно считать как «все минус те, что начинаются».

ПримерСлова с ограничениями

Сколько пятибуквенных слов можно составить из букв А, Б, В, Г, Д так, что буква Б встречается ровно один раз и не стоит первой (остальные — любые из оставшихся 4 букв)?

Решение

Место для Б — одна из 4 позиций (кроме первой). Остальные 4 места заполняем буквами из 4 оставшихся: 4⁴ = 256. Всего 4·256 = 1024.

ПримерНумерация слов по алфавиту

Выпишите по алфавиту все слова из букв А, К, Р, Т длины 4 с разными буквами. Какой номер у слова РАКТ?

Решение

from itertools import permutations words = [''.join(p) for p in permutations('АКРТ')] words.sort() print(words.index('РАКТ') + 1) Вручную: слов на А — 3! = 6, на К — 6, итого 12 слов стоят раньше любого слова на Р. Среди слов на Р первым идёт РАКТ (буквы после Р расположены по алфавиту). Номер: 12 + 1 = 13.

ПримерВключения-исключения

Сколько натуральных чисел от 1 до 100 не делятся ни на 2, ни на 3, ни на 5?

Решение

Пусть A₂, A₃, A₅ — множества кратных 2, 3, 5. |A₂| = 50, |A₃| = 33, |A₅| = 20; пересечения: |A₂∩A₃| = 16, |A₂∩A₅| = 10, |A₃∩A₅| = 6; |A₂∩A₃∩A₅| = 3. Кратны хотя бы одному: 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74. Не делятся ни на одно: 100 − 74 = 26. Проверка: print(sum(1 for n in range(1, 101) if n % 2 and n % 3 and n % 5))

ПримерРазмещения: PIN-код без повторов

Сколько существует четырёхзначных PIN-кодов (цифры 0–9), в которых все цифры различны, а первая цифра не равна 0?

Решение

Первая цифра — 9 вариантов (1–9), вторая — 9 (любая из оставшихся, включая 0), третья — 8, четвёртая — 7: 9·9·8·7 = 4536.

ПримерСочетания: слова с заданным числом единиц

Сколько существует двоичных слов длины 6, содержащих ровно две единицы?

Решение

Выбираем 2 позиции из 6 для единиц, порядок выбора не важен: C(6, 2) = 6·5/2 = 15. Проверка: from math import comb print(comb(6, 2)) # 15

← Графы и основы алгоритмов на графах Компьютерные сети: IP-адреса, маски и маршрутизация →