Birthday Problem ( on combinatorics )

[LLT]

Birthday Problem (need help on combinatorics...) URGENT!

Question:

There are ''n'' ppl in a room. What's the probability of 2 or more ppl sharing the same birthday?

My Answer: (Looking at 2 ways...)

Let E be Event of 2 or more ppl sharing the same birthday...
then: P(E) = 1 - P(E')

1) Conditional Probability:

n P(E')
1 1
2 364/365
3 364/365 * 363/365
.
.
.
n (364!/365n)/(364-n+1)!

it works for 0<n<366

this is definitely right...
but my combinatorics answer doesn't agree...

2) Combinatorics:

P(E') = 365C(n)/366C(n)

Top part of fraction gives me the no. of ways that n ppl can have completely different birthday.
Bottom part gives me the total no. of ways of possible birthday that n ppl can have.

if my appraoach is not clear for bottom part... try using the analogy of a question: there are 2 balls and 5 baskets, what are the total no. of ways that the balls can be distributed into 5 baskets providing basket can hold 0,1,2 balls:

try putting the basket space as | | | | | |
there are 5 spaces between those lines...
then using ''.'' to represent balls:
so balls can be distributed in these ways:
| . | . | | | |
| . | | . | | |
| . . | | | | |
| | | | . | . |
| | | | . . | |
etc etc...
notice if u ignored the outward most lines:
|( . | . | | | )|
|( . | | . | | )|
|( . . | | | | )|
|( | | | . | . )|
|( | | | . . | )|
etc etc...
u get 6 objects within the brackets and u're actually only trying to fit 2 ''.''s in those 6 objects, hence u get 6C2 for the no. of possible arrangement.

using the same analogy, there are 365 days and ''n'' ppl, the total no. of ways to fit ''n'' ppl in 365 days should be (365-1+n)C(n) = (364+n)C(n)
that's how I get the bottom part. but then... if you try for n = 2
it doesn't fit with the conditional probability...

WHYYYYYYYYY!?

 

[snoble]

The number of ways n people can have birthdays is simply 365^n. To be honest I didn't really understand your argument for why you could use 2C6 but I would guess your problem is you assumed things extended when there is infact no justification for it. Also the number of ways for n people to have distinct birthdays is (365 C n)*n! since every set of dates has to be permuted across all the people. Remember order matters here.

Hope that helps
Steven

 

[eddo]

KataKoniK, the way you solved it only applies to 2 people, his question was referring to a class with n people. Clearly the answer is going to involve n, since the more people there are, the more likely two of them share a birthday.

You can think of it as each person "chosing" a birthday. Than the number of ways n people can chose different birthdays out of 365 is 365Cn, and the total of number of ways for people to chose any birthday is 365^n, so the answer is 365Cn/(365^n). To answer your question, simply do 1 - 365Cn/(365^n).

This number can't be put into most calculators, but you can easily write a program to calculate it by noticing that both the top and bottom have n terms, so if you group these together you can multiply a bunch of numbers which will each be smaller than 1. There's also a formula which approximates it very well, if you are curious I will look it up because I don't remember the derivation.

The probability ends up being a lot lower than you think, about 11% chance that no one has the same birthday when n=40. Random things have a tendency to group together.

Hope the explanation made sense.

 

[LittleWolf]

Wouldn't you count the number of ways n people could have different birthdays as
365!/(365-n)!=365*364*363*...*(365-n+1). First person can be born on any date (365 ways) in the year, second person must be born on a different date ( 364 ways ) , third person must be born on a date different that the first two people (363 ways), etc.
The probability that a least two people have the same birthday then becomes
1-365!/(365-n)!/365^n

 

[LLT]

thank you very much :)
It does helps a lot...

I got a 2nd question though... how would I go to prove it's 365^n?
I know it's trivial for a binary system... with n digits, it'll just be 2^n...
but is there any way of proving this result? or reasoning for this reasult?

 

[LLT]

i mean... what if leap years are consider? how would I work out the answer?/?

 

[LittleWolf]

The probability that N people have different birthdays is (365/365)*(364/365)*(363/365)*...*((366-N)/365) assuming that the events are independent of each other.
A leap year calc is (366/366)*(365/366)*(364/366)*...*((367-N)/366) for N people.