Solving birthday problem without complement

Question

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.

Answer 1

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).$]

Answer 2

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.