Продолжаем тему комбинаторики, и я понимаю, что тема обсуждалась уже сто раз. Попробую чуть по-своему посмотреть на вопрос.
Итак, есть группа из n человек; какова вероятность, что хотя бы у двоих совпадут дни рождения? Имеется в виду день-месяц, причем исключаем високосные годы для простоты. Точнее, интересно, при каком n эта вероятность превысит ½?
Ясно, что если народу много, более 365 человек, то совпадение будет точно. Другая крайность - два человека: совпадение очень маловероятно. В самом деле, у одного день рождения любой, у второго должен быть такой же, это дает 365 вариантов. А всего вариантов 365². В итоге вероятность 1/365, что совсем немного.
Потому и парадокс: кажется, что вероятность будет расти с ростом n как-то линейно, достигая уровня ½ где-то на полдороге, то есть ближе ко второй сотне.
А на самом деле, это n=23, то есть численность класса в школе, группы в детском саду или университете, да застолья бывают с большим числом участников.
Что же такое, вероятность ½? Это означает, что если взять много независимых групп по 23 человека, то совпадение (хотя бы одно) найдется примерно в половине групп. Это не значит, что в любой группе из 23 человек оно есть.
Зато в каждой группе из 50 человек оно почти наверняка есть.
Самый сложный вопрос здесь - это почему надо использовать формулы для упорядоченного выбора, а не для неупорядоченного. Далее всё просто.
Число способов "раздать" дни рождения n людям равно 365ⁿ, если повторы допускаются. А вот без повторов это уже число размещений, и оно получается делением 365! на (365-n)!. Это, по сути, перемножение чисел от 365 до 365-n+1 в порядке убывания: первый может взять любой день, второй может взять любой из оставшихся, и так далее. Деление одного на другой и дает вероятность, что совпадения ни одного нет, и её вычтем из единицы.
Проблема в том, как вычислять такое, ибо числа большие. Можно аккуратно перемножать в цикле (365-i)/365 n раз. Например, так:
perl -E '$n=23;$S=1;map {$S*=(365-$_)/365} 0..$n-1; say 1-$S'
Получится 0.5079723.
А вот так в R:
1-prod((365+1-seq(23))/365)
Можно применить формулу Стирлинга: n!~nⁿ/eⁿ и прийти к приближенной формуле (конечно, это опасно, можно получить неправильное n, но всё равно где-то близко):
Это вероятность, что совпадений нет. При n=23 она дает 0.47693, то есть вероятность хотя бы одного совпадения 0.523. Завысили, но несильно. Для n=22 получаем 0.4917, то есть ответ в итоге нашли правильный.
Давайте посмотрим, как эта вероятность растет. Для n=30 получаем около 0.7; для n=50 уже 0.97. Для n=60 будет более 0.99. А для интуитивно предполагаемого n=180 получается неотличимо от единицы: десятичный логарифм вероятности "совпадений нет" около -23.
В принципе, если в классе 30 человек, то можно смело ставить один к одному, что совпадение найдется. А в параллели, в которой от 50 до 100 человек, можно рисковать многим: совпадение найдется почти наверняка.
График показывает, что рост действительно близок к линейному на промежуточном этапе (между 20 и 40), но куда быстрее, чем казалось. Наклон около 3%, вместо предполагаемых интуицией 0.5%.
Давайте заодно решим родственные задачи: сколько нужно человек, чтобы вероятность совпадения месяца превысила 0.5, и аналогично для дня недели. Это очень просто получается исправлением 365 в формуле выше на 12 и 7, соответственно. Имеем табличку:
0.08 0.236 0.427 0.618 0.777 0.888 0.95 0.98 0.996 0.999 0.9999
Это от 2 до 12 человек. Для дней недели:
0.143 0.388 0.65 0.85 0.957 0.99
Это от 2 до 7 человек. Здесь интуиция близка к правде, 5 человек для месяца и 4 для дня недели.
Важный вывод. Эта ситуация очень типична для вероятностных дел. Гарантировать наличие совпадения в данной задаче можно, но только для n>356. Но риск его не найти может быть пренебрежимо мал значительно раньше, при n порядка сотни, а то и 50.
Давайте напоследок посчитаем, при какой численности будет не менее двух совпадений.
Число способов выбрать n человек без единого совпадения, мы уже знаем: это 365!/(365-n)!. Теперь вычислим, сколько способов устроить ровно одно совпадение. Надо выбрать n-1 человека без совпадений (365!/(365-n+1)! вариантов); потом выбрать одного: его день рождения потворится (n-1 вариант); последнего из компании поместить в любую из n позиций (n вариантов); поделить на два, так как двух совпадающих можно менять местами без изменения расклада. В итоге имеем
½n(n-1)365!/(365+1-n)!
вариантов.
В сумме это число вариантов, что совпадений не больше одного. Поделим на 365ⁿ, получив вероятность, что совпадений не больше одного. Вычтем из единицы, получив вероятность хотя бы двух.
Эта вероятность равна 0.48 при n=35 и 0.51 при n=36. При n=60 она больше 0.96, а при n=90 отличается от единицы в пятом знаке.
То есть, в параллели на 90 человек можно смело ставить на то, что и два совпадения найдутся.
Интересно посчитать дальше: не менее трех, четырех, семнадцати совпадений... Я пока не знаю ответа, но, может, когда-нибудь выясню.
И напишу.