Разбор задачи про «Тайного Санту»

Для начала немного терминологии.

В комбинаторике есть понятие перестановка. Это способ последовательного расположения объектов с учётом порядка. Например, буквы abc можно расположить как abc, acb, bac, bca, cab, cba — всего 6 перестановок длины 3 (то есть состоящих из трёх элементов).

Отдельный вид перестановок — беспорядки. Это когда ни один элемент не стоит на своём месте. В примере выше это перестановки bca и cab — всего 2 беспорядка для перестановки длины 3.

Подробнее об этом можно прочесть в уроках «Задача о беспорядках» и «Задача о беспорядках (возвращение!)». А пока вернёмся к разбору.

Первый вопрос задачи звучал так:

1) Сколько существует вариантов, при которых ни один из участников не вытягивает своё имя?

Ни один из участников не вытягивает своё имя — значит, ни один из элементов не стоит на своём месте. То есть надо найти число беспорядков длины 4 (так как друзей четверо).

Как это сделать? Есть разные способы

1) Можно «в лоб» — выписать все 4! = 24 перестановки длины 4 и вычеркнуть все, в которых хоть какой-то элемент стоит на своём месте. Получится 9. Но уже для n = 5 этот способ займёт очень много времени.
2) Можно воспользоваться рекуррентной формулой из второго упомянутого выше урока. Вот она: !n =(n−1)⋅(!(n−1)+!(n−2)). Результат будет тем же: (4−1)(2+1)=9.
3) Можно воспользоваться формулой включений-исключений — про этот способ как-нибудь расскажем отдельно!

А ещё есть сайты, которые выдают список всех беспорядков по заданному n — вот пример.

Ответ на первую часть задачи: 9 вариантов. Теперь перейдём ко второй.

2) Какова при этом вероятность, что Аня с Вовой дарят подарки друг другу и Борис с Галей друг другу? Ответ округлите до сотых.

Мы уже выяснили, что есть 9 вариантов, подходящих под исходные условия задачи. Предлагается найти вероятность одного конкретного из них. Так как все исходы равновероятны, то вероятность каждого равна
1/9 = 0.(1) ≈ 0.11.