Birthday Problem (At most 3 share a birthday)

[TaliskerBA]

I have started a course on probability and the lecturer, after explaining how to work out the classic problem of the likelihood that at least 2 people share a birthday out of a field of N people (which I understood fine), issued the challenge of working out what the probability of at most 3 people sharing a birthday (out of N people) is. I have had a think about this and am at a loss at how to work this out. Can anyone offer any advice about how to tackle this problem?

Thanks,

Talisker

 

[gerben]

I have started a course on probability and the lecturer, after explaining how to work out the classic problem of the likelihood that at least 2 people share a birthday out of a field of N people (which I understood fine), issued the challenge of working out what the probability of at most 3 people sharing a birthday (out of N people) is. I have had a think about this and am at a loss at how to work this out. Can anyone offer any advice about how to tackle this problem?

Thanks,

Talisker

The probability that at most two people share a birthday would be:

P(no people share birthday) + P(exactly 1 pair of people share a birthday) + P(exactly 2 pairs of people share different birthdays) + ...

To get at most 3 people share a birthday just extend this to get:

\text{P(no people share birthday)} + \sum_{i=1}^{N/2} \text{P(exactly i pairs of people share different birthdays)} + \sum_{i=1}^{N/3} \text{P(exactly i triples of people share different birthdays)}

 

[bpet]

I have started a course on probability and the lecturer, after explaining how to work out the classic problem of the likelihood that at least 2 people share a birthday out of a field of N people (which I understood fine), issued the challenge of working out what the probability of at most 3 people sharing a birthday (out of N people) is. I have had a think about this and am at a loss at how to work this out. Can anyone offer any advice about how to tackle this problem?

Thanks,

Talisker

It could be solved recursively in terms of N. In solving the original problem the lecturer would have (implicitly at least) kept track of the number of days with 0 or 1 birthdays as one more person is added to the group. Same idea applies for the new problem, but including the number of days with 2 or 3 birthdays as well. There's more combinations to consider here but really it's a finite-state Markov chain so in principle the solution could be written as a matrix product.