Main content

### Course: Statistics and probability > Unit 8

Lesson 4: Combinatorics and probability- Probability using combinations
- Probability & combinations (2 of 2)
- Example: Different ways to pick officers
- Example: Combinatorics and probability
- Getting exactly two heads (combinatorics)
- Exactly three heads in five flips
- Generalizing with binomial coefficients (bit advanced)
- Example: Lottery probability
- Probability with permutations and combinations
- Conditional probability and combinations
- Mega millions jackpot probability
- Birthday probability problem

© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Birthday probability problem

The probability that at least 2 people in a room of 30 share the same birthday. Created by Sal Khan.

## Want to join the conversation?

- The total # of possible outcomes of different birthday is n!/(n-k)! as presented.

I am ok with that.

But what happens to combination rule (where order is not important) - using the combination rule I thought this # would be n!/k!(n-k)!

What happens to the k!

I know we end up using permutation where order is important - but why order is important in this problem? I thought order is NOT IMPORTANT so we should use combination, NOT permutation.(49 votes)- Hi site2n2. Order is important in this problem because we care about treating each person as a distinct person. For example, if there were three people in the room, namely Alice, Bob, and Eve, then assuming we have one possibility where Alice was born on 8/18, Bob was born on 4/13, and Eve was born on 8/10, we want to count all the permutations of these three dates since it's very possible for Alice to be born on 8/10, Bob to be born on 8/18, and Eve to be born on 4/13 instead. Notice that n!/(n-k)! treats the k objects as distinct (and hence does not count permutations of the k objects as only 1 possibility) while nCk = n!/(n-k)!*k! divides by k! and counts permutations of the k objects as 1 possibility.(81 votes)

- I can see that this is a permutation: n!/(n-k)! but I don't really understand then why he divides by 365^30 as this is not in the permutation ula we have learnt? Can anybody explain this?(14 votes)
- Jennifer,

This is not a permutation problem.

Matthew,

This is not a combination problem.

The birthday problem should be treated as a series of independent events. Any one person’s birthday does not have an influence on anybody else’s birthday (we will assume no twins, triplets, etc. are in the same class). In finding the probability that no one has the same birthday, Sal took the probability that each member of the class, in turn, did not have the same birthday as all the other members of the class before them. It would be like finding the probability that in five separate rolls of a six-sided die you did not get the same number (which would be (6/6)*(5/6)*(4/6)*(3/6)*(2/6) . There are no combinations or permutations there. Likewise there is no combination or permutation in the thirty terms of (365/365)*(364/365)*(363/365)* … (338/365)*(337/365)*(336/365) for the birthday problem. Sal only wanted to simplify the numerator of that series of numbers. Looking at just the numerator (the denominator becomes 365^30), Sal has 365*364*363*… 338*337*336. Another way to write this is 365!/335!, which is also 365!/(365-30)! which looks like the n!/(n-k)! permutation formula. Just because it looks like the permutation formula does not mean we are using the permutation formula.

I wish Sal had explained that the factorials he was using was not an attempt to apply the permutation formula. This is fooling a number of people.(72 votes)

- Shouldn't we keep in mind leap years? Meaning, the probability that 1 person was born on a specific day is 1/366, not 1/365?(16 votes)
- Except that that wouldn't be the correct probability if we were to consider it. Leap years only happen every fourth year (more or less), so the probability that a person was born on February 29 is 1/1461 and the probability of every other day would be 4/1461. Since the events aren't all equiprobable in this new system, calculating the probability that lots of people all have different birthdays is far more complicated, which is why people traditionally ignore leap years for a reasonable estimate.(28 votes)

- How would this calculation change if we wanted to know the probability of at least 3 people out of 30 share the same birthday?(16 votes)
- I think that I follow xcrypt, but why would the problem become increasingly more complicated to ask whether 4 of 30 share? Would it not be:

P(At least 4 of 30 share the same birthday) = 1 - (P(X) *(30 choose 3) - P(X)*(30 choose 2) - P(none share the same birthday) ??(3 votes)

- I know how to do the problem, but just thnking about the answer, it seems really high. There are 30 people in a class, 360ish days in a year and if you think about it like 360 spots for people to stand in and the 30 kids need to stand in a spot, it'd seem really hard for 2 people to stand in the same spot given ALL the possible spaces there are. I know this logic isn't "holeproof" but still, it seems that the probability should be like much less than such a high number like 70%.(11 votes)
- One way I like to think of it:

If you had say 100 kids or 120 kids with all different birthdays at that point each additional kid would have about a 1/3 probability of having a duplicate birthday.

So looking at it that way at some point the probability becomes extremely extremely low of everyone having a different birthday.(9 votes)

- Could you instead just work out the probability that one person has a birthday on one day and then times it by the probability that another person has a birthday on that day.(2 votes)
- that must be 1/365 * 1/365

and it is surely far lower than what we get here

think about why(2 votes)

- How do you calculate factorials greater than 170 on the calculator? Mine keeps showing up with 'error'.(7 votes)
- Most calculators can't handle such large numbers.

Here is a website that allows you to calculate that and much much larger integer calculations - even up to answers that have a million digits! (though that might take some time :)

http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm(7 votes)

- May I ask for example the number of people is more than 365? what equation will be used instead?(2 votes)
- The birthday probability problem is trivial if the number of people is greater than 365, as then there is a 100% chance that 2 people share a birthday.(26 votes)

- Why does Sal assume the year is not a leap year? (He says 365 instead of 366)(2 votes)
- Well, the proportion of people born on Feb 29 is pretty small. And that's what we care about: What day people are born on, not how many days there are in the current year. Hence, assuming the 365 day year isn't such a bad assumption.(4 votes)

- I understood absolutely nothing.(3 votes)

## Video transcript

One of you all sent a fairly
interesting problem, so I thought I would work it out. The problem is I have a
group of 30 people, so 30 people in a room. They're randomly
selected 30 people. And the question is what is the
probability that at least 2 people have the same birthday? This is kind of a fun question
because that's the size of a lot of classrooms. What's the probability that at
least someone in the classroom shares a birthday with someone
else in the classroom? That's a good way
to phrase as well. This is the same thing as
saying, what is the probability that someone shares with
at least someone else. They could share it with 2
other people or 4 other people in the birthday. And at first this problem seems
really hard because there's a lot of circumstances
that makes this true. I could have exactly 2 people
have the same birthday. I could have exactly 3 people
have the same birthday. I could have exactly 29 people
have the same birthday and all of these make this true, so do
I add the probability of each of those circumstances? And then add them up and then
that becomes really hard. And then I would have to
say, OK, whose birthdays and I comparing? And I would have to
do combinations. It becomes a really difficult
problem unless you make kind of one very simplifying
take on the problem. This is the opposite of--
well let me draw the probability space. Let's say that this is
all of the outcomes. Let me draw it with
a thicker line. So let's say that's all
of the outcomes of my probability space. So that's 100% of the outcomes. We want to know-- let me draw
it in a color that won't be offensive to you. That doesn't look that
great, but anyway. Let's say that this is the
probability, this area right here-- and I don't know
how big it really is, we'll figure it out. Let's say that this is the
probability that someone shares a birthday with
at least someone else. What's this area over here? What's this green area? Well, that means if these are
all the cases where someone shares a birthday with someone
else, these are all the area where no one shares a
birthday with anyone. Or you could say, all 30 people
have different birthdays. This is what we're
trying to figure out. I'll just call it the
probability that someone shares. I'll call it the probability
of sharing, probability of s. If this whole area is area 1 or
area 100%, this green area right here, this is going
to be 1 minus p of s. This is going to be
1 minus p of s. Or if we said that this is the
probability-- or another way we could say it, actually this is
the best way to think about it. If this is different, so
this is the probability of different birthdays. This is the probability
that all 30 people have 30 different birthdays. No one shares with anyone. The probability that someone
shares with someone else plus the probability that no one
shares with anyone-- they all have distinct birthdays--
that's got to be equal to 1. Because we're either going to
be in this situation or we're going to be in that situation. Or you can say they're
equal to 100%. Either way, 100% and 1
are the same number. It's equal to 100%. So if we figure out the
probability that everyone has the same birthday we could
subtract it from 100. So let's see. We could we just rewrite this. The probability that someone
shares a birthday with someone else, that's equal to 100%
minus the probability that everyone has distinct,
separate birthdays. And the reason why I'm doing
that is because as I started off in the video, this is
kind of hard to figure out. You know, I can figure out the
probability that 2 people have the same birthday, 5 people,
and it becomes very confusing. But here, if I wanted to just
figure out the probability that everyone has a distinct
birthday, it's actually a much easier probability
to solve for. So what's the probability
that everyone has a distinct birthday? So let's think about it. Person one. Just for simplicity, let's
imagine the case that we only have 2 people in the room. What's the probably that they
have different birthdays? Let's see, person one, their
birthday could be 365 days out of 365 days of the year. You know, whenever
their birthday is. And then person two, if we
wanted to ensure that they don't have the same birthday,
how many days could person two be born on? Well, it could be born
on any day that person one was not born on. So there are 364
possibilities out 365. So if you had 2 people, the
probability that no one is born on the same
birthday-- this is just 1. It's just going to be
equal to 364/365. Now what happens if
we had 3 people? So first of all the
first person could be born on any day. Then the second person could
be born on 364 possible days out of 365. And then the third person,
what's the probability that the third person isn't
born on either of these people birthdays? So 2 days are taken up, so
the probability is 363/365. You multiply them out. You get 365 times 36-- actually
I should rewrite this one. Instead of saying this is 1,
let me write this as-- the numerator is 365 times
364 over 365 squared. Because I want you
to see the pattern. Here the probability is 365
times 364 times 363 over 365 to the third power. And so, in general, if you just
kept doing this to 30, if I just kept this process for 30
people-- the probability that no one shares the same birthday
would be equal to 365 times 364 times 363-- I'll have
30 terms up here. All the way down to what? All the way down to 336. That'll actually be 30
terms divided by 365 to the 30th power. And you can just type this into
your calculator right now. It'll take you a little time to
type in 30 numbers, and you'll get the probability that no one
shares the same birthday with anyone else. But before we do that let
me just show you something that might make it a
little bit easier. Is there any way that I can
mathematically express this with factorials? Or that I could mathematically
express this with factorials? Let's think about it. 365 factorial is what? 365 factorial is equal to 365
times 364 times 363 times-- all the way down to 1. You just keep multiplying. It's a huge number. Now, if I just want the 365
times the 364 in this case, I have to get rid of all of
these numbers back here. One thing I could do is I
could divide this thing by all of these numbers. So 363 times 362-- all
the way down to 1. So that's the same thing as
dividing by 363 factorial. 365 factorial divided by 363
factorial is essentially this because all of these
terms cancel out. So this is equal to 365
factorial over 363 factorial over 365 squared. And of course, for this case,
it's almost silly to worry about the factorials, but it
becomes useful once we have something larger than
two terms up here. So by the same logic, this
right here is going to be equal to 365 factorial over 362
factorial over 365 squared. And actually, just another
interesting point. How did we get this 365? Sorry, how did we get
this 363 factorial? Well, 365 minus 2
is 363, right? And that makes sense because we
only wanted two terms up here. We only wanted two
terms right here. So we wanted to divide by a
factorial that's two less. And so we'd only get the
highest two terms left. This is also equal to-- you
could write this as 365 factorial divided by 365 minus
2 factorial 365 minus 2 is 363 factorial and then you just end
up with those two terms and that's that there. And then likewise, this right
here, this numerator you could rewrite as 365 factorial
divided by 365 minus 3-- and we had 3 people-- factorial. And that should hopefully
make sense, right? This is the same thing as 365
factorial-- well 365 divided by 3 is 362 factorial. And so that's equal to
365 times 364 times 363 all the way down. Divided by 362 times
all the way down. And that'll cancel out with
everything else and you'd be just left with that. And that's that right there. So by that same logic, this top
part here can be written as 365 factorial over what? 365 minus 30 factorial. And I did all of that just so
I could show you kind of the pattern and because this is
frankly easier to type into a calculator if you know where
the factorial button is. So let's figure out what
this entire probability is. So turning on the calculator,
we want-- so let's do the numerator. 365 factorial divided by--
well, what's 365 minus 30? That's 335. Divided by 335 factorial and
that's the whole numerator. And now we want to divide
the numerator by 365 to the 30th power. Let the calculator think
and we get 0.2936. Equals 0.2936. Actually 37 if you rounded,
which is equal to 29.37%. Now, just so you remember what
we were doing all along, this was the probability that no one
shares a birthday with anyone. This was the probability of
everyone having distinct, different birthdays
from everyone else. And we said, well, the
probability that someone shares a birthday with someone else,
or maybe more than one person, is equal to all of the
possibilities-- kind of the 100%, the probability space,
minus the probability that no one shares a birthday
with anybody. So that's equal to
100% minus 29.37%. Or another way you could write
it as that's 1 minus 0.2937, which is equal to-- so if I
want to subtract that from 1. 1 minus-- that just
means the answer. That means 1 minus 0.29. You get 0.7063. So the probability that someone
shares a birthday with someone else is 0.7063--
it keeps going. Which is approximately
equal to 70.6%. Which is kind of a neat result
because if you have 30 people in a room you might say,
oh wow, what are the odds that someone has the same
birthday as someone else? It's actually pretty high. 70% of the time, if you have a
group of 30 people, at least 1 person shares a birthday
with at least one other person in the room. So that's kind of
a neat problem. And kind of a neat result
at the same time. Anyway, see you in
the next video.