Birthday Problem ( on combinatorics )

In summary, the question is asking for the probability of two or more people sharing the same birthday in a group of n people. Two approaches were explored: conditional probability and combinatorics. The correct solution involves using the formula (365 C n)/(365^n) to calculate the probability. This formula takes into account the fact that the order of birthdays matters. The probability of no one sharing a birthday is 365^n, so to get the probability of at least two people sharing a birthday, we subtract this from 1. The result is a much lower probability than expected, about 11% for a group of 40 people. Leap years can be accounted for by adjusting the formula slightly.
  • #1
LLT
16
0
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!?
 
Physics news on Phys.org
  • #2
The answer should be just this

P(no matching b-day for 2 people) = (365/365) * (364/365) = .9973

And then do 1 - .9973 = .0027, which is the the probability of having a matching birthday amongst two people
 
Last edited:
  • #3
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
 
  • #4
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.
 
  • #5
eddo said:
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.


Just realized that. My mistake :blushing:
 
  • #6
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
 
  • #7
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?
 
  • #8
i mean... what if leap years are consider? how would I work out the answer?/?
 
  • #9
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.
 

What is the Birthday Problem?

The Birthday Problem is a mathematical problem that calculates the probability of two people sharing the same birthday in a group of n people.

How do you solve the Birthday Problem?

To solve the Birthday Problem, you can use the formula: P = 1 - (365! / (365^n * (365-n)!)), where n is the number of people in the group. This formula calculates the probability of no shared birthdays and then subtracts it from 1 to get the probability of at least one shared birthday.

Why is the Birthday Problem important?

The Birthday Problem has practical applications in fields such as cryptography, where it is used to calculate the likelihood of two people having the same encryption key. It also serves as a good example of the counterintuitive nature of probability.

How does the size of the group affect the probability in the Birthday Problem?

The larger the group size, the higher the probability of two people sharing the same birthday. This is because as the number of people increases, the number of possible combinations of shared birthdays also increases.

Is the Birthday Problem always accurate?

The Birthday Problem assumes that all 365 days of the year are equally likely to be someone's birthday, which may not always be the case. Additionally, the problem does not account for leap years or the possibility of multiple people sharing the same birthday. Therefore, the calculated probability may not always be accurate in real-world scenarios.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
829
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
913
  • Precalculus Mathematics Homework Help
Replies
9
Views
3K
  • General Math
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
26K
  • Precalculus Mathematics Homework Help
Replies
3
Views
918
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top