Угадывание карт и задача о днях рождения при выборке без возвращения

Рассмотрим равновероятно случайную колоду, состоящую из карт, помеченных числами от 1 до n, причем некоторые числа могут повторяться. Игрок угадывает верхнюю карту, после чего она открывается и удаляется, а игра продолжается. Каково ожидаемое число правильных угадываний при наилучшей и наихудшей стратегиях? Мы получаем точные асимптотические оценки для обеих стратегий. Для наихудшего случая это дает ответ на недавний вопрос Диакониса, Грэма, Хе и Спайро, установивших правильный порядок величины. В рамках доказательства мы исследуем задачу о днях рождения для выборки без возвращения с использованием метода Штейна.