1
$\begingroup$

Why isn't adding the ways to achieve every mutually exclusive outcome giving me the denominator in the birthday problem for four people?

$$\binom{4}{2} \cdot 365 \cdot 364 +\binom{4}{3} \cdot 365 \cdot 364+365 \cdot 364 \cdot 363 \cdot 362+365-365^4 \neq 0$$ :

Exactly Two share a Birthday + Exactly Three share a Birthday + None Share a Birthday + All Share a Birthday - Denominator of Birthday problem for 4 People Should Equal Zero.

I expect this to work because the sum of binomial coefficients in pascal's should equal the $2^{row}.$

$\endgroup$
1
  • 3
    $\begingroup$ You seem to be omitting cases, like $XXYY$. Also, the first case is off: Exactly two sharing a birthday would need you to choose three dates, not two. $\endgroup$
    – lulu
    Commented Feb 15 at 19:36

1 Answer 1

Reset to default
1
$\begingroup$

The corrected calculation is as follows:

$\underbrace{\binom{4}{2}\cdot 365\cdot 364\cdot 363}_{\text{aabc}} + \underbrace{\binom{4}{2}\cdot\binom{365}{2}}_{\text{aabb}}+\underbrace{4\cdot 365\cdot 364}_{\text{aaab}}+\underbrace{365\cdot 364\cdot 363\cdot 362}_{\text{abcd}}+\underbrace{365}_{\text{aaaa}} = 365^4$

$\endgroup$
5
  • $\begingroup$ I'm writing the calculation for five people. $365+365*364*363*362*361+{5 \choose 4}*365*364+{5 \choose 2}*{365 \choose 2}+{5 \choose 3} *365*364*363+ {5 \choose 2}*365*364*363*362+ {5 \choose 2}* {365 \choose 2}*363$ $\endgroup$
    – user1289955
    Commented Feb 16 at 1:12
  • $\begingroup$ aaaaa (5), abcde (1), aaaab (4), aabbb (3), aaabc (3), aabcd (2), aabbc (2) What else am I missing? $\endgroup$
    – user1289955
    Commented Feb 16 at 1:15
  • $\begingroup$ For aabbb it will be $\binom{5}{2}\times 365\times 364$. That case was off by a factor of two. We can tell apart the triple from the pair. In the four person version we couldn't tell one pair apart from the other pair and so had to compensate. $\endgroup$
    – JMoravitz
    Commented Feb 16 at 2:30
  • $\begingroup$ Whenever you have something symmetric such as aaabbb You can't distinguish so in this case you have the product of two binomial coefficients ${persons \choose 2} \cdot {365 \choose 2} ?$ I wonder whether there's a general formula for these; I mean there's a general formula to do inclusion exclusion. $\endgroup$
    – user1289955
    Commented Feb 16 at 4:06
  • $\begingroup$ user1289955: If you have $d_i$ days each with $i$ sharing that birthday (with $i$ going from $0$ to $365$) then $\sum_i d_i =365$ and $\sum_i id_i=n$ is the number of people then you can use $\dfrac{\left(\sum_i d_i\right)!}{\prod_i\left(d_i!\right)} \dfrac{\left(\sum_i id_i\right)!}{\prod_i(\left(i!\right)^{d_i})}$. Sum this over all the partitions of $n$ into up to $365$ parts and you will get $365^n$. $\endgroup$
    – Henry
    Commented Feb 17 at 23:33

You must log in to answer this question.