4
$\begingroup$

This question is about the birthday problem: the probability that in a group of n people, at least two of them have the same birthday (https://en.wikipedia.org/wiki/Birthday_problem).

An easy way to calculate the probability is to calculate first the probability that no two people have the same birthday.

Let's say that I want to calculate the probability that in a group of 20 people, NO two people have the same birthday.

So, for 20 people with different birthdays, I can choose the first birthday in 365 ways, the second in 364 ways and so on, while for 20 people who can have the same birthday, I can choose the first birthday in 365 ways, the second also in 365 ways, and so on. At the end:

$p={365 \cdot 364 \cdot 363 \cdot ... \cdot 346 \over 365 \cdot 365 \cdot 365 \cdot ... \cdot 365}\approx 0.59$

This is the right method and I understand it. I don't understand why the following method is wrong:

The probability that in a group of 20 people NO two people have the same birthday is the ratio between the combination without repetition of 20 birthdays and the combination with repetition of 20 birthdays:

$$p={C_{365,20} \over C'_{365,20}}={\binom{365}{20} \over \left(\binom{365}{20}\right)}={\binom{365}{20} \over \binom{365+20-1}{20}}=\frac{{{365!}\over {20!\cdot(365-20)!}}}{{(365+20-1)!}\over{20!\cdot{(365-1)!}}}\approx 0.35$$

I understand the mistake is in the denominator (as the numerator is the same of the other method, after simplifying that 20!), but why? Isn't it right to calculate the k-combination with repetition of 20 birthdays?

Thanks for helping!

$\endgroup$
3
  • $\begingroup$ To obtain the binomial coefficient $\binom{n}{k}$, type \binom{n}{k} when you are in math mode. $\endgroup$
    – N. F. Taussig
    Commented May 19, 2016 at 21:19
  • 3
    $\begingroup$ Order matters. Not all $20$-tuples of birthdays, ordered by date, are equally probable. Thus you can't compute the probability as $\frac{\#\text{cases with condition}}{\#\text{all cases}}$. $\endgroup$
    – Daniel Fischer
    Commented May 19, 2016 at 21:40
  • $\begingroup$ See question 21 : qbyte.org/puzzles/puzzle03.html $\endgroup$
    – N.S.JOHN
    Commented May 20, 2016 at 3:00

1 Answer 1

Reset to default
2
$\begingroup$

As you say, the problem is in the denominator

The number of equally probable ways of choosing $k$ distinguishable items without repetition from $n$ is $\frac{n!}{(n-k)!} = k!{n \choose k}$. If the items were not distinguishable, there would be ${n \choose k}$ ways, as you have in your numerator

The number of equally probable ways of choosing $k$ distinguishable items with repetition from $n$ is $n^k$ and this is the correct denominator to use in a counting calculation of probability

Meanwhile your ${n+k-1 \choose k}$ represents the number of ways of choosing $k$ indistinguishable items with repetition from $n$. But these ways are not (in the real world) equally probable and so cannot be used in a simple counting calculation of probability. As a simple example, flipping two coins, an unordered one heads and one tails outcome is twice as probable as a two heads outcome

$\endgroup$
3
  • $\begingroup$ So the key here is that the items are distinguishable, and not indistinguishable? I always thought that the difference between k-permutation and k-combination is that in the former the order matters, while in the latter it doesn't. And I thought that in this problem order doesn't matter. I mean: in a room with two people, the combination of 1st January and 2nd January is the same of 2nd Jan and 1st Jan, isn't it? I thought I shouldn't count it twice... $\endgroup$
    – Gio
    Commented Dec 3, 2017 at 8:26
  • $\begingroup$ @Gio: The key phrase is "not equally probable". In a room with two people, having a combination of 1st January and 2nd January (ignoring order) is presumably about twice as likely as having two cases of 1st January. So to get the correct probability by counting equally probable events, order matters $\endgroup$
    – Henry
    Commented Dec 3, 2017 at 12:06
  • $\begingroup$ Now I see. Thank you very much! $\endgroup$
    – Gio
    Commented Dec 8, 2017 at 13:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .