Версия для печати темы

Автор: AlKrem 25.9.2011, 17:16

Приветствую и заранее благодарю за ответы

Всем известна данная задача:
http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%B4%D0%BD%D0%B5%D0%B9_%D1%80%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F

Под заголовком "Альтернативный метод" указано, как ее решить с использованием формул комбинаторики. Собственно вопрос: как написать формулу для ровно k совпадений? Все, что я родил, это A(365,23-k+1)C(23,k) подходящих вариантов из 365^23 возможных. Типа, в выборке имеем 23-k+1 уникальных дней рождения, которые умножаем на кол-во вариантов расстановок в группе тех людей, у которых ДР повторяются.

Для проверки взял, что в году 5 дней.
1. Проверял, когда идет выборка 3 человек, у 2-х одинаковые ДР:
{1,2,2},{1,3,3},{1,4,4},{1,5,5}
{2,1,1},{2,3,3},{2,4,4},{2,5,5}
...
{5,1,1},{5,2,2},{5,3,3},{5,4,4}
Это 20 вариантов. Умножаем на С(3,2)=3 (все варианты пар людей, у которых ДР совпадает), получаем 60.
A(5,3-2+1)C(3,2)=60
2. Проверял, когда идет выборка 3 человек, у 3-х одинаковые ДР:
очевидно, что вариантов 5, и формула дает верное решение.
3. Для 4-х человек и 3,4 совпадений тоже все верно.

Но если я возьму 365 дней, 23 человека, и просуммирую свою формулу по k от 2 до 23, то после деления на 365^23 получу 37.1%, а не 50.7%, как в вики. Причем вклад от первого члена - 36.3%. В чем моя ошибка, если тестовые данные верны?

Автор: malkolm 26.9.2011, 18:09

А где варианты, когда трое родились в один день, и ещё пятеро - в другой, и ещё семеро - в третий, и ещё по четыре пары - ещё в 4 каких-то дня? Это к примеру.

Автор: AlKrem 27.9.2011, 16:06

Спасибо. Я наивно полагал, что удастся вывести простую формулу зависимости от k. А тут сумма...

Автор: venja 27.9.2011, 16:53

Когда-то я тоже так полагал. И наступил на те же грабли