**Warning**: Missing argument 2 for ted_filter_oembed_amp_iframe() in

**/home/kawalski/public_html/torontotutorteam.ca/wp-content/plugins/jetpack/modules/shortcodes/ted.php**on line

**108**

The Birthday Problem can basically be stated as: in a group on n randomly chosen people, what is the chance that some pair will have the same birthday?

Just for some context, in a random group of 23 people there is a 50% probability that two people will have the same birthday. In a group of 70 people there is a 99% probability!

### Solving the Birthday Problem

Let P_{n} represent the probability that some pair will have the same birthday in a group of “n” random people

We know that there are 365 days in a year, so there are 365 possible birthdays (ignoring leap years). Given this, the chance that any 2 people have the same birthday is ^{1}/_{365}

This means that P_{2} = ^{1}/_{365}, the probability of 2 people having the same birthday in a group of 2 people

The solution space for this problem can be divided into 2 distinct possibilities, either a pair of matching birthdays exists, or there are no matching birthdays. Given this we can say:

P(birthday match exists) + P(no birthday matches) = 1

Rearranging:

P(birthday match exists) = 1 – P(no birthday matches)

So

P_{n} = 1 – P(no birthday matches amongst n people)

We established that P_{2} = ^{1}/_{365}

Put another way, if you have two people, there are 364 possible days where they do not match

P(no birthday matches, n=2) = ^{364}/_{365}

So P_{2} = 1 – ^{364}/_{365}

Now if we add in a third person, there are 363 possibilities that the third person’s birthday does not match with the first 2.

So the probability that the third person does not match with either of the first 2 is ^{363}/_{365}

In order for there to be no matches between all 3 people, the first 2 must not match, AND the third person must not match with the first 2. In probability, if A **and** B must happen, we take the product of their probabilities, so:

P(no birthday matches, n=3) = ^{364}/_{365} * ^{363}/_{365}

Which means: P_{3} = 1 – ^{364}/_{365} * ^{363}/_{365}

Following the same logic, if we introduce a 4th person who does not match with the first 3

P_{4} = 1 – ^{364}/_{365} * ^{363}/_{365} * ^{362}/_{365}

Following this trend:

P_{n} = 1 – ^{365-1}/_{365} * ^{365-2}/_{365} * ^{365-3}/_{365} … * ^{365-n+1}/_{365}

The reason it is -n+1 (instead of -n) is because we begin comparing when there are 2 people, meaning if there are 2 people then there is 1 potential day they could match. The number of days that could match is always one less than the number of people there are.

### Factorials

Before we can continue with the birthday problem we need to quickly cover factorials. Factorials are denoted by an exclamation mark, and is the product of all of the integers up to and including any integer.

n! = 1 x 2 x 3 x … x n

Our goal now is to express Pn in terms of factorials.

Consider ^{365!}/_{(}_{365-n)!} = ^{1*2*…*(365-n)*(365-n+1)*…*(365-1)*365}/_{1*2*…*(365-n)}

Notice how the numerator has all the same terms as the denominator, and more,

So we can cancel these out: ^{1*2*…*(365-n)*(365-n+1)*…*(365-1)*365}/_{1*2*…*(365-n)}

And we are left with ^{365!}/_{(}_{365-n)!} = (365 – n + 1) * (365 – n + 2) * … * (365 – 2) * (365 – 1) * **365**

And if we just change the order of the terms: ^{365!}/_{(}_{365-n)!} = (365 – 1) * (365 – 2) * … * (365 – n + 2) * (365 – n + 1) * **365**

Remember that P_{n} = 1 – ^{365-1}/_{365} * ^{365-2}/_{365} * ^{365-3}/_{365} … * ^{365-n+1}/_{365}

And we can see that the numerators of P_{n} are practically the same as ^{365!}/_{(}_{365-n)!} except for the bold 365 at the end.

Now if we look at the denominator of the product in P_{n}, it’s simply 365 multiplied by itself n-1 times, so 365^{n-1}. But remember we have an extra 365 in the numerator, so if we multiply the denominator by an extra 365 we can cancel it out. So we will use a denominator of 365^{n}

### Putting it All Together

The final step is to combine all the pieces we’ve put together:

P_{n} = 1 – ^{365!}/_{(}_{365-n)! * 365n}

By taking the factorial terms and dividing it by 365^{n} we have recreated the long string of products in the original P_{n} formula, and this is the general solution to the birthday problem!

So if we return to the example of 23 people, all we do if plug in 23

P_{23} = 1 – ^{365!}/_{(}_{365-23)! * 36523} = 1 – ^{365!}/_{342! * 36523} = 1 – 0.493 = 0.507

In a group of 70 people

P_{70} = 1 – ^{365!}/_{(}_{365-70)! * 36570} = 1 – ^{365!}/_{295! * 36570} = 1 – 0.00084 = 0.99916

That’s the solution to the birthday problem! All of the fractions can get a bit confusing, so it really helps to write it out.

If you prefer to watch a video version of this tutorial:

You can also check out more great math tutorials.