Probability of at least two people choosing the same menu

448 Views Asked by At

A group of $n>4$ people gathers for a feast. Each person brings $n$ dishes of his/her own unique stew. Then, each person forms his/her own menu by choosing 4 distinct dishes (of different stews), randomly and independently of any of the other people. What is the probability that at least two people chose the exact same menu?

What I got so far is since the probability for a person to choose a specific menu is $p=\frac{1}{n \choose 4}$, if $X$ is the random variable of the number of people choosing "that" menu, then $\Pr(X\geq 2)=\sum_{k=2}^{n} {n \choose k}p^k(1-p)^{n-k}\\$, but even after simplyfing this expression it doesn't resemble any of the answers (it's a multiple choice).

So I could really use some guidance here.

1

There are 1 best solutions below

0
On BEST ANSWER

There are $N=\binom n4$ possible possibilities for a menu, and there are enough dishes of each type so that the persons are free to choose. So the problem can be restated, and let us better ask for the complementary probability:

$n$ persons choose in the same time, independently one of $N$ menus, that exist in overflow. Which is the probability for $n$ different choices?

The answer is $$ \frac1{N^n}\cdot (N-0)(N-1)\dots(N-(n-1)) = \left(1-\frac 1N\right) \left(1-\frac 2N\right) \dots \left(1-\frac {n-1}N\right) \ . $$ The complement is the answer to the OP $$ 1-\left(1-\frac 1N\right) \left(1-\frac 2N\right) \dots \left(1-\frac {n-1}N\right)\ ,\qquad N = \binom n4=\frac 1{24}n(n-1)(n-2)(n-3) \ . $$