Probability of unique cards drawn from a deck of cards

Question

Problem

Let $N$ be the number of cards in a deck. Each card is different and unique. One after the other each player:

• draws $M$ many cards from the deck
• writes down/memorizes what cards (s)he got
• puts the cards back in the deck
• shuffles the deck
• and passes it to the next player

If there are $X$ many players in the game, what is the probability of one or more cards having been drawn by more than 1 player?

Question

I would like to know a formula for how to calculate the probability for a given combination of $(N, M, X)$. It would be really nice to get an example calculation too, for $N = 100, M = 5, X = 3$.

Motivation

Just for fun I am working on a little card game. I need to find out how many cards I need in the deck to maximize the probability of "fun" gameplay interactions. My assumption is that the game would be most fun if it was possible for two players to have drawn the same card, but unlikely for them to have drawn the same hand.

Thank you all very much.

Answer 1

Suppose no two players have drawn the same card. The probability you seek is the complement.

So, this gives the probability you are looking for as:

$$1-\dfrac{\displaystyle \prod_{k=0}^{X-1}\dbinom{N-kM}{M}}{\dbinom{N}{M}^X} = 1- \dfrac{(N-M)!}{(N-MX)!\left( M!\dbinom{N}{M} \right)^{X-1}}$$

So, given your sample values:

$$1-\dfrac{95!}{85!\left(5!\dbinom{100}{5}\right)^2} \approx 55\%$$

So, there is a better than average chance that at least two people will have drawn at least one card the same.