Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Birthday Problem (need help on combinatorics )

  1. Jun 16, 2005 #1

    LLT

    User Avatar

    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!!!!!!!!!!!!!!!!!?????????????
     
  2. jcsd
  3. Jun 16, 2005 #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: Jun 16, 2005
  4. Jun 16, 2005 #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
     
  5. Jun 17, 2005 #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 noone has the same birthday when n=40. Random things have a tendency to group together.

    Hope the explanation made sense.
     
  6. Jun 17, 2005 #5

    Just realized that. My mistake :blushing:
     
  7. Jun 17, 2005 #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
     
  8. Jun 18, 2005 #7

    LLT

    User Avatar

    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???
     
  9. Jun 19, 2005 #8

    LLT

    User Avatar

    i mean... what if leap years are consider??? how would I work out the answer?/?
     
  10. Jun 19, 2005 #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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Birthday Problem (need help on combinatorics )
  1. Combinatorics help (Replies: 1)

  2. Combinatorics problem (Replies: 3)

  3. Combinatorics problem (Replies: 8)

  4. Combinatorics problem (Replies: 4)

Loading...