Probability – Group of r People with at Least Three Sharing the Same Birthday

birthdaycombinatoricspermutationsprobability

What is the probability that in a randomly chosen group of $r$ people at least three people have the same birthday?

  1. $\displaystyle 1- \frac{365\cdot364 \cdots(365-r+1)}{365^r}$
  2. $\displaystyle \frac{365\cdot364
    \cdots(365-r+1)}{365^r} +{r\choose 2}\cdot \frac{365\cdot364\cdot363 \cdots
    (364-(r-2) +1)}{364^{r-2}}$
  3. $\displaystyle 1- \frac{365\cdot364
    \cdots(365-r+1)}{365^r} +{r\choose 2}\cdot \frac{365\cdot364\cdot363 \cdots (364-(r-2) +1)}{364^{r-2}}$
  4. $\displaystyle\frac{365\cdot364 \cdots(365-r+1)}{365^r}
    $

My attempt :

(May be typo in option $(3)$ of question !)

$$P(\text{at least 3 persons have same birthday})$$

$$= 1 – \{P\text{(no one has same birthday) + P(any 2 have same birthday)\}}$$

So, option $(3)$ is true.

Can you explain it, please?

It asked here before, but I'm not satisfied by explanation.

Best Answer

Given $2k$ items, there are $(2k-1)!!$ ways to arrange them into pairs: the first item can be paired with $2k-1$ possibilities; the first unpaired item can be matched with $2k-3$ items; the new first unpaired item can be paired with $2k-5$ items; etc.

The number of functions from $n$ people to $365$ dates with $n-2k$ singles and $k$ pairs is $$ \begin{array}{cc} &\displaystyle\underbrace{ \overbrace{\binom{365}{n-k}}^{\substack{\text{ways to choose}\\\text{$n-k$ dates}\\\text{for birthdays}}} \overbrace{\binom{n-k}{k}}^{\substack{\text{ways to choose}\\\text{$k$ dates}\\\text{for pairs}}} }&\displaystyle\underbrace{ \overbrace{\ \ \binom{n}{2k}\ \ }^{\substack{\text{ways to choose}\\\text{$2k$ people}\\\text{for pairs}}} \overbrace{(n-2k)!\vphantom{\binom{n}{k}}}^{\substack{\text{ways to arrange}\\\text{$n-2k$ singles}}} \overbrace{(2k-1)!!\vphantom{\binom{n}{k}}}^{\substack{\text{ways to pair}\\\text{$2k$ people}}} \overbrace{\ \ \ \ \ k!\ \ \ \ \ \vphantom{\binom{n}{k}}}^{\substack{\text{ways to arrange}\\\text{$k$ pairs}}} }\\ \displaystyle= &\displaystyle\frac{365!}{(365-n+k)!\,(n-2k)!\,k!} &\displaystyle\frac{n!}{2^k} \end{array} $$ Thus, the probability of getting at least one triple is $$ 1-\frac{365!\,n!}{365^n}\sum_{k=0}^{365}\frac1{(365-n+k)!\,(n-2k)!\,k!\,2^k} $$ where we take $\frac1{n!}=0$ for $n\lt0$.

Here is a plot from $n=0$ to $n=730$. For $n\lt3$, the probability of getting a triple is $0$, and for $n\gt730$, the probability is $1$.

enter image description here

Related Question