Вы слышали про задачу о рассеянной секретарше ? Тут надо PIE применить ? Секретарше нужно отправить n различных писем по n различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Какова вероятность того, что ни одно письмо не дойдет до своего адресата?

Предыдущий
вопрос Следующий
вопрос

Да, для решения этой задачи можно использовать принцип включений и исключений (PIE).

Для начала посчитаем общее количество способов разложить письма по конвертам. Очевидно, что общее количество способов равно n!, так как у нас n различных писем, которые надо разложить по n различным адресам.

Теперь посчитаем количество способов, когда ни одно письмо не доходит до своего адресата. Для этого воспользуемся PIE.

Пусть A_i - i-ое письмо дошло до своего адресата. Тогда количество способов, когда i-ое письмо дошло, равно (n-1)!.

С помощью PIE можно выразить количество способов, когда хотя бы одно письмо дошло
n! - C(n,1)(n-1)! + C(n,2)(n-2)! - ... + (-1)^n C(n,n)(0)!.

Теперь найдем вероятность того, что ни одно письмо не достигнет своего адресата, это будет равно количеству таких способов, деленному на общее количество способов
P = 1 - (n! - C(n,1)(n-1)! + C(n,2)(n-2)! - ... + (-1)^n C(n,n)(0)!) / n!.

Это и будет вероятностью того, что ни одно письмо не достигнет своего адресата.