Counting problem relatively hard I think.

[charmedbeauty]

Homework Statement

For this problem assume that the 365 dates of the year are equally likely as birthdays.

b)Find the probability that in a group of n people, at least two have the same birthday.

Homework Equations

The Attempt at a Solution

Well I am not really sure what method I should use here??

but... the total number of solutions is surely 365ⁿ

but at least two?

maybe something along the lines...

P(365,2)
so

the probability is P(365,2)/365ⁿ

But I have a feeling I'm missing something, but I don't understand what?

 

[RoshanBBQ]

A way to approach this problem is to notice the probability of at least a pair having the same birthday is the same as one minus the probability of no one having the same birthday.

 

[HallsofIvy]

To determine the probability that "at least two" things occur, look at the opposite event- that NO two people have the same birthday. The probability that "at least two people have the same birthday" is then 1 minus the probability that no two people have the same birthday.

And that calculation easy- imagine putting all n of the people in order- in a straight line. The first person can have any day of the year as a birthday. The probability of that is 365/365= 1, of course. The second person can have any day except that one day as birthday. The probability of that is 364/365. The third person can have any day except those two days. The probability of that is 363/365. Can you finish that?

 

[Curious3141]

Homework Statement

For this problem assume that the 365 dates of the year are equally likely as birthdays.

b)Find the probability that in a group of n people, at least two have the same birthday.

Homework Equations

The Attempt at a Solution

Well I am not really sure what method I should use here??

but... the total number of solutions is surely 365ⁿ

but at least two?

maybe something along the lines...

P(365,2)
so

the probability is P(365,2)/365ⁿ

But I have a feeling I'm missing something, but I don't understand what?

HallsofIvy's post is good, and works for n \leq 365 but what happens when n \geq 366? Hint: Pigeonhole principle.

So the answer is a formula dependent on n for the former case, and just a single answer for the latter case.

 

[RoshanBBQ]

HallsofIvy's post is good, and works for n \leq 365 but what happens when n \geq 366? Hint: Pigeonhole principle.

So the answer is a formula dependent on n for the former case, and just a single answer for the latter case.

365 choose 366 is zero, so the answer will work for n >365. Also, I wouldn't call it the pigeonhole principle. I'd call it the common sense principle.

 

[Curious3141]

365 choose 366 is zero, so the answer will work for n >365.

HallsofIvy's post did not introduce the combination operation. His post would directly have led to:

p(n) = 1 - \frac{(365)(364)...(365-n+1)}{365^n}

which clearly holds for n \leq 365. It also holds for n=366, because one can say the 366th person has zero "choice" of birthday to avoid a collision. However, when n > 366, the last terms of (365-n+1) stop making sense, because, for example, the 367th person does not have "-1" choices of birthday, etc., he simply has no (zero) choice. Even though the expression will evaluate to the correct answer (one) for n > 366 because exactly one of the terms in the product is zero, the expression is still not correct mathematically.

The next commonly taken step, which involves simplifying the expression and recasting it in terms of combinatorial notation, is what you're referring to. Of course, based on the definition nCr = 0 for r > n, this expression would hold for all n, but the fact remains that this is not a mathematically sound way of deriving that formula since the initial expression does not make sense for n > 366, as I explained.

Hence the usual way of working the problem, which is to break the problem up into two cases, n \leq 365 and n \geq 366. Mathematical rigour matters.

Also, I wouldn't call it the pigeonhole principle. I'd call it the common sense principle.

You can call it whatever you like, and it is common sense, but it IS called the pigeonhole principle.

 

[charmedbeauty]

HallsofIvy's post did not introduce the combination operation. His post would directly have led to:

p(n) = 1 - \frac{(365)(364)...(365-n+1)}{365^n}

which clearly holds for n \leq 365. It also holds for n=366, because one can say the 366th person has zero "choice" of birthday to avoid a collision. However, when n > 366, the last terms of (365-n+1) stop making sense, because, for example, the 367th person does not have "-1" choices of birthday, etc., he simply has no (zero) choice. Even though the expression will evaluate to the correct answer (one) for n > 366 because exactly one of the terms in the product is zero, the expression is still not correct mathematically.

The next commonly taken step, which involves simplifying the expression and recasting it in terms of combinatorial notation, is what you're referring to. Of course, based on the definition nCr = 0 for r > n, this expression would hold for all n, but the fact remains that this is not a mathematically sound way of deriving that formula since the initial expression does not make sense for n > 366, as I explained.

Hence the usual way of working the problem, which is to break the problem up into two cases, n \leq 365 and n \geq 366. Mathematical rigour matters.



You can call it whatever you like, and it is common sense, but it IS called the pigeonhole principle.

Thanks for all the replies cleared things up a lot I was really struggling to see where the 1 came from.

 

[HallsofIvy]

365 choose 366 is zero, so the answer will work for n >365. Also, I wouldn't call it the pigeonhole principle. I'd call it the common sense principle.

There are 365 days of the year (pigeon holes) and more than 365 people (pigeons) so the "pigeon hole principle" say that at least two people must have the same birthday. There are many "common sense principles", only one "pigeon hole principle".