# Birthday Problem counting principles

Consider the Birthday Problem

In this problem we calculate the probability that, in a group of n people, at least two have the same birthday. Let E be the event that at least two people share a birthday. In order to calculate P(E), we first need a sample space. A possible sample space consists of n-tuples of the integers 1 . . . 365 (each of n people have a birthday on one of the 365 days of the year; leap years are not considered).

Calculate P(E) for n = 2 using counting principles, and confirm that it is the same as 1 − P(E^c).

attempt:

For n = 2, our sample space S contains 365^2 tuples {(x1, x2), xi ∈ N , 1 ≤ xi ≤ 365}, and can be divided into two disjoint subspaces: S = S1 ∪ S2

where S1 contains tuples where each of the 2 birthdays is distinct,

S2 contains tuples where all two birthdays are the same

|S1| = P(365, 2) = 365*364

|S2| = P(365, 1) = 365

|S| = 365^2= 365*364+365= |S1|+|S2|

P(E)= |S2| / |S| = |S|-|S1|/|S| =1-(|S1|/|S|)= 1-P(E)

is n=2 ok?

• Looks good ... but of course it is not true for $n=2$ that $P(E)=1-P(E)$: when you have $2$ people the chance of them having tyhe same birthday is of course much lower than $\frac{1}{2}$. (in fact, I don't think there is any $n$ for which $P(E) = 1-P(E) = \frac{1}{2}$) – Bram28 Dec 14 '17 at 18:33
• Did you mean "Calculate P(E) for n = 2 using counting principles, and confirm that it is the same as $1 − P(E^c)$"? – XRBtoTheMOON Dec 14 '17 at 18:39
• For the sample space, consider cases. Note that the partitions of $5$ are begin{align*} 5 & = 5\\ = 4 + 1\\ & = 3 + 2\\ & = 3 + 1 + 1\\ & = 2 + 2 + 1\\ & = 2 + 1 + 1 + 1\\ & = 1 + 1 + 1 + 1 + 1\end{align*} The probability that there is no match (ignoring the possibility that somebody is born on 29 February) is $$1 \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365}$$ The probability that there is a match is found by subtracting that number from $1$. – N. F. Taussig Dec 14 '17 at 22:30