Вопрос школьника
Имеется n писем n разным людям и n подписанных конвертов. Сколькими способами можно вложить письма в конверты так, чтобы ни одно письмо не дошло до адресата.
Ответ от учителя
Для решения этой задачи можно использовать принцип включений-исключений.
Обозначим через A_i событие, что i-ое письмо попадет в конверт с адресатом i. Тогда вероятность того, что ни одно письмо не дошло до адресата, равна:
P = количество исходов, при которых ни одно событие A_i не произошло / общее количество исходов.
Общее количество исходов равно n!, так как каждое письмо можно положить в любой из n конвертов, а порядок вложения писем в конверты не важен.
Чтобы посчитать количество исходов, при которых хотя бы одно событие A_i произошло, воспользуемся принципом включений-исключений:
N(A_1 ∪ A_2 ∪ … ∪ A_n) = ∑ N(A_i) — ∑ N(A_i ∩ A_j) + ∑ N(A_i ∩ A_j ∩ A_k) — … + (-1)^n-1 N(A_1 ∩ A_2 ∩ … ∩ A_n),
где N(A_i) — количество исходов, при которых произошло событие A_i, N(A_i ∩ A_j) — количество исходов, при которых произошли события A_i и A_j одновременно, и т.д.
Количество исходов, при которых произошло событие A_i, равно (n-1)!, так как i-ое письмо не может быть положено в конверт с адресатом i.
Количество исходов, при которых произошли события A_i и A_j одновременно, равно (n-2)!, так как i-ое и j-ое письма не могут быть положены в конверты с соответствующими адресатами.
Аналогично, количество исходов, при которых произошли события A_i, A_j и A_k одновременно, равно (n-3)!, и т.д.
Таким образом, получаем:
N(A_1 ∪ A_2 ∪ … ∪ A_n) = n!(1/1! — 1/2! + 1/3! — … + (-1)^(n-1)/n!)
Искомая вероятность равна:
P = 1 — N(A_1 ∪ A_2 ∪ … ∪ A_n) / n!
P = 1 — (1/1! — 1/2! + 1/3! — … + (-1)^(n-1)/n!)
Например, для n=3 получаем:
P = 1 — (1/1! — 1/2! + 1/3!) = 1 — (1 — 1/2 + 1/6) = 1/3
То есть, при трех письмах и трех адресатах вероятность того, что ни одно письмо не дошло до адресата, равна 1/3.
Общая формула для любого n:
P = 1 — (1/1! — 1/2! + 1/3! — … + (-1)^(n-1)/n!)
