Пять девушек приготовили по 1 подарку на вечеринку. Сколькими способами
можно распределить эти 5 подарка между 5 девушками так, чтобы ни одна из
них не получила свой подарок?
Ответы
Эта задача решается с помощью принципа включений-исключений.
Обозначим через A_i событие, при котором i-я девушка получает свой подарок. Тогда мы ищем количество способов распределения подарков, когда ни одна девушка не получает свой подарок, то есть требуется найти количество способов, когда ни одно из событий A_i не происходит.
Используя принцип включений-исключений, получаем:
|A_1 ∪ A_2 ∪ A_3 ∪ A_4 ∪ A_5| = Σ|A_i| - Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| - Σ|A_i ∩ A_j ∩ A_k ∩ A_m| + |A_1 ∩ A_2 ∩ A_3 ∩ A_4 ∩ A_5|
Здесь |S| обозначает количество элементов в множестве S.
Поскольку каждая девушка получает ровно один подарок, то |A_i| = (5-1)! = 4!, т.е. количество перестановок 4 предметов. Аналогично, |A_i ∩ A_j| = (5-2)! = 3!, |A_i ∩ A_j ∩ A_k| = (5-3)! = 2!, |A_i ∩ A_j ∩ A_k ∩ A_m| = (5-4)! = 1!.
Таким образом, мы имеем:
|A_1 ∪ A_2 ∪ A_3 ∪ A_4 ∪ A_5| = 5×4! - 10×3! + 10×2! - 5×1! + 1! = 120 - 60 + 20 - 5 + 1 = 76.
Ответ: количество способов распределения 5 подарков между 5 девушками так, чтобы ни одна из них не получила свой подарок, равно 76.