Комбинаторика и вероятность

Задачи с ответом-числом: сколько способов раздать билеты, подобрать код, какова вероятность, что кому-то не хватит столика.

Правила суммы и произведения

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

Пример

Код из 4 различных чётных цифр. Чётных цифр пять (0, 2, 4, 6, 8), поэтому кодов 5·4·3·2 = 120. Если добавлено условие вроде «сумма цифр равна 12», удобнее выписать подходящие наборы цифр, а потом умножить на число их перестановок.

Основные формулы

Что считаем	Порядок важен?	Формула
Перестановки n объектов	да	`n!`
Упорядоченный выбор k из n без повторов	да	`n!/(n−k)!`
Сочетания: k из n без повторов	нет	`C(n,k) = n!/(k!(n−k)!)`
Строки длины k из n символов с повторами	да	`nᵏ`
n одинаковых предметов по k ящикам	нет	`C(n+k−1, k−1)`
Перестановки с повторами (a одинаковых, b одинаковых, …)	да	`n!/(a!·b!·…)`

Шары и перегородки

Сколькими способами разложить n одинаковых предметов по k ящикам, если ящик может остаться пустым? Ставим n шаров и k−1 перегородок в ряд и выбираем, где стоят перегородки:

C(n + k − 1, k − 1)

Если в каждом ящике должен быть хотя бы один предмет, сначала кладём по одному в каждый ящик, а оставшиеся n−k раскладываем так же: C(n−1, k−1).

Пример

6 одинаковых конфет трём детям: C(8, 2) = 28 способов. Если каждому хотя бы одну: C(5, 2) = 10.

Ловушка

Внимательно читайте, одинаковы ли предметы. Одинаковые билеты раскладываются шарами и перегородками. Каждый различимый предмет даёт свой множитель: один VIP-билет на 5 человек — это ×5. Запреты вроде «не все одному» вычитайте в конце.

Включения–исключения

|A ∪ B| = |A| + |B| − |A ∩ B|

Пример: каждый житель — клиент банка A или банка Б (или обоих). Тогда доля клиентов обоих банков равна P(A) + P(Б) − 1.

Классическая вероятность и «хотя бы один»

P = число благоприятных исходов / число всех равновозможных исходов

Вероятность «хотя бы одного» проще считать через противоположное событие:

P(хотя бы один) = 1 − P(ни одного)

Пример: свободные столики

Осталось 2 свободных столика, не пришли три компании с бронью. Независимо друг от друга они придут с вероятностями 0,8, 0,5 и 0,5. Столиков не хватит, только если придут все три: 0,8·0,5·0,5 = 0,2. Если бы столик был один, его не хватило бы при двух или трёх пришедших компаниях. Тогда перебирают все варианты, кто пришёл, и складывают их вероятности.

Математическое ожидание

E[X] = Σ xᵢ · P(X = xᵢ)

Свойство, которое очень упрощает задачи: E[X + Y] = E[X] + E[Y], причём всегда, даже для зависимых величин. Ожидаемое число пришедших компаний равно сумме вероятностей прихода каждого.

Пример: выручка в среднем

40% дней парковка стоит 400 ₽, 60% — 200 ₽. Средняя цена: 0,4·400 + 0,6·200 = 280 ₽. Если в разные дни разное число машин, считайте выручку по каждому периоду отдельно и складывайте. Перемножать среднюю цену на общее число машин нельзя.

Ещё примеры

Сколькими способами раздать 5 одинаковых бонусов 4 сотрудникам, если кто-то может ничего не получить?

C(5+4−1, 3) = C(8,3) = 56.

Какова вероятность хотя бы одной шестёрки за 4 броска кубика?

1 − (5/6)⁴ = 1 − 625/1296 ≈ 0,518.

Пять друзей садятся в ряд. Сколько рассадок, в которых Аня и Боря сидят рядом?

Склеиваем Аню и Борю в один «блок»: 4! = 24 рассадки, внутри блока 2 порядка. Итого 48.