# Solving birthday problem without complement

I'm trying to find the probability of at least 2 people in a room of 4 sharing the same birthday (without using complements).

I began by breaking the problem down into 4 cases:

Let E = the event that at least 2 people share the same birthday in a room of 4.

Our sample size: $365^4$

Case 1: 4 people share the same birthday: 365 ways

Case 2: 3 people share the same birthday, 1 distinct birthday: $365 \cdot 364 \cdot C(4,3)$

Case 3: 2 people share a birthday, another 2 people share some other birthday: $365 \cdot 364 \cdot \frac{C(4,2)}{2}$

Case 4: 2 people share same birthday, 2 distinct birthdays: $365 \cdot 364 \cdot 363 \cdot C(4,2) \cdot 2$

After adding up all the cases and dividing by the sample size to find probability the answer had an over-count. I checked my answer by doing $$P(E) = 1- \frac{365 \cdot 364 \cdot 363 \cdot 362}{365^4}$$

Where did I have an over-count? Thank you!

Here is an example that works with n = 3 people and at least 2 people share same birthday.

Case 1: 3 people share same birthday: 365

Case 2: 2 Same birthdays, 1 different: $365 \cdot 364 \cdot \binom{3}{2}$

$$P(E) = \frac{365 + (365 \cdot 364 \cdot \binom{3}{2})}{365^3} \equiv 1 - \frac{365 \cdot 364 \cdot 363}{365^3}$$

Those are both equivalent answers because in the complement we're subtracting away the event that all birthdays are distinct.

• Case three. The four people are named., say Alfred, Bobby, Carlos and Dan. Pick alfred's birthday. Pick who else shares alfred's birthday. Pick the birthday of the remaining two people. There are $365\cdot 364\cdot 3$ outcomes here, not $365\cdot 364\cdot 6$ – JMoravitz Dec 13 '16 at 5:09
• For Case 3, I think you're overcounting. You are counting the pairs of birthdays twice, just naming them in a different order.... – Calconym Dec 13 '16 at 5:10
• Why is there a $\cdot 2$ at the end of Case 4? – Erick Wong Dec 13 '16 at 5:28
• @user1813840 Imagine you are writing down every combination exactly once by filling out various templates like [XYZZ]. You are saying that you need to count both of the templates [XYZZ] and [YXZZ]. But any list of dates that fits the first template (say, [Easter, Christmas, New Year, New Year]) also fits the second. That's double counting! – Erick Wong Dec 13 '16 at 12:59
• @ErickWong Finally wrapped my head around it, thank you so much :) – user390456 Dec 13 '16 at 19:22

When trying out a new way, it is prudent to look to a familiar class of problem, like die tosses in Yahtzee, ( except that here it is a $365$ sided die tossed 4 times.)

We can then "straightjacket" it into a format as [ Choose faces to come up ] $\times$ [ Permute ]

There are four possibilities:

$4\;of\;a\;kind: [\binom{365}1] \times [\frac {4!}{4!}]$

$3-1\;of\;a\;kind: [\binom{365}1\binom{364}1] \times [\frac{4!}{3!1!}]$

$2-2\;of\;a\;kind: [ \binom{365}2] \times [\frac{4!}{2!2!}]$

$2-1-1\;of\;a\;kind: [\binom{365}1\binom{364}2 \times [\frac{4!}{2!1!1!}]$

Add up to get favorable ways, and divide by $365^4$ to get the final result.

Assuming 365 equally likely birthdays, here is a simulation of 10 million realizations of the number of unique birthdays $X$ out of 4. It might help you settle the over-count issue.

m = 10^7;  x = numeric(m)
for (i in 1:m) {
room = sample(1:365, 4, repl=T)
x[i] = length(unique(room))  }
table(x)/m
x
2         3         4
0.0000510 0.0163006 0.9836484


Notice that event $\{X = 1\}$ did not occur even once in 10 million 'rooms'. Not really surprising; it's probability is only 2.056465e-08. Probabilities for $X = 3$ and $4$ should be accurate to three places.

Addendum (after unexplained down-vote): OP's Case 4 has an incorrect factor of 2 as Commented by @ErickWong (which prompted, and agrees with, my simulation). This is also @trueblueanil's case 2-1-1, which again agrees with my simulated $P(X=3) \approx 0.016.$ (+1) [Moreover, sdding cases 3-1 and 2-2 gives less than .0001, as in the simulation for $P(X=2).$]