Непонятная статистика Тайного Санты: 20 человек, 2,4 квинтиллиона возможностей

Когда наступает декабрь, многие офисные работники начинают готовиться ко ставшей уже и у нас традиционной игре Тайный Санта, в которой каждый должен купить подарок для случайно выбранного коллеги. Теоретически, это должно быть весело, но чаще — неловко, особенно если вы не знаете хорошо своего получателя. Но вы когда-нибудь задумывались, сколько возможных комбинаций подарков существует в вашем офисе? В этой статье мы попробуем ответить на этот вопрос с помощью математики.

Как посчитать перестановки?

Давайте начнем с простого случая, когда нет никаких ограничений на то, кто кому будет дарить подарок. То есть каждый может случайным образом выбрать себя или любого другого сотрудника. Тогда мы имеем дело с перестановками, то есть упорядоченными наборами элементов. Например, если в офисе четыре человека.

Чтобы посчитать, сколько всего перестановок, мы можем использовать принцип умножения. Сначала мы выбираем подарок для первого человека. У нас есть четыре варианта. Затем мы выбираем подарок для второго человека. У нас остается три варианта, так как мы не можем повторять уже выбранный подарок. Аналогично, для третьего человека у нас два варианта, а для последнего — один. Тогда общее количество перестановок равно произведению этих чисел:

4x3x2x1=24

Это число называется факториалом и обозначается как 4! Факториал n — это произведение всех натуральных чисел от 1 до n. Факториалы быстро растут с увеличением n. Например, 10! = 3 628 800, а 20! = 2 432 902 008 176 640 000. Это больше, чем количество песчинок на Земле!

Как посчитать размещения?

Однако мы обычно не хотим, чтобы кто-то покупал подарок сам для себя. Это неинтересно и несправедливо. Поэтому мы хотим исключить такие варианты из нашего подсчета. То есть мы хотим найти количество перестановок, в которых ни один элемент не остается на своем месте. Такие перестановки называются размещениями.

Найти количество размещений не так просто, как перестановок. Но существует формула, которая позволяет сделать это проще. Эта формула называется числом де Монмора и равна n!/e, округленному до ближайшего целого числа, где n — количество элементов, а e — особое математическое число, приблизительно равное 2,71828. Это число называется числом Эйлера и возникает во многих областях математики.

Например, если в офисе четыре человека, то количество размещений равно 4!/e, что равно 9, округленному до ближайшего целого числа. Это означает, что есть девять способов купить подарки так, чтобы никто не купил себе.

Можно показать, что для больших значений n примерно 63,2% всех перестановок не являются размещениями и поэтому исключаются из подсчета. Это существенно сокращает количество возможных комбинаций подарков. Например, для 20 человек количество размещений равно 895 014 631 192 902 121, что в 2,7 раза меньше, чем количество перестановок.

Уникальный сам-себе-Санта

Еще один интересный факт о Тайном Санте — это то, что в среднем только один человек из всех участников будет выбирать себя, независимо от того, сколько их. Это не зависит от того, есть ли у вас один человек (хотя это ужасно несекретный и отчаянно грустный Тайный Санта) или миллиард человек. Ожидаемое количество людей, которые выберут себя, всегда равно единице.

Почему это так? Для этого мы можем использовать простое рассуждение. Представьте, что вы удваиваете количество участников. Тогда у вас будет в два раза больше подарков, которые нужно купить, и в два раза больше людей, которые их получат. Но также у каждого человека будет в два раза меньше шансов выбрать себя, так как у него будет в два раза больше вариантов. Тогда в два раза больше людей, каждый из которых имеет в два раза меньше шансов выбрать себя, дает нам то же самое среднее количество людей, которые выберут себя — единицу.