6
$\begingroup$

The probem is I have 2 conflicting solutions.

Solution 1:

Since there is $n$ people who each choose any one of $n$ doors, the total number of ways $n$ people enter the hall is $n^n$. (correct?)

then I used, $P($one door not chosen$)=1-P($all doors chosen$)$

which (to me) implies a 1 to 1 matching of people to doors, which can only happen in $n!$ ways (equivalent to the number of arrangements of $n$ objects).

ie. $P($all doors chosen$)=\dfrac{n!}{n^n}$

and so the required probability is $1-\dfrac{n!}{n^n}$

Solution 2:

Consider all cases where at least $1$ door is not used:

If $n$ people enter through $1$ door there is $1^n=1$ arrangements

If $n$ people enter through $2$ doors there is $2^n$ arrangements

If $n$ people enter through $3$ doors there is $3^n$ arrangements

...

If $n-1$ people enter through $n-1$ doors there is $(n-1)^n$ arrangements

(Note: $n$ cannot enter through all $n$ doors or required condition is not met)

In this formulation the required probability is given by $\dfrac{1^n+2^n+3^n+...+(n-1)^n}{n^n}$

So which solution (if either) is correct?

2 Answers 2

3

There are, as you say, $n^n$ ways for $n$ people to enter the hall, and $n!$ of those ways that use all $n$ doors, so the number of ways that leave at least one door unused is $n^n-n!$. If all $n^n$ possibilities are equally likely, the probability of at least one door’s remaining unused is indeed $1-\dfrac{n!}{n^n}$.

The problem can also be worked by inclusion-exclusion, which is a correct version of what you were trying to do with your second solution. For each of the $n$ doors there are $(n-1)^n$ ways for the $n$ people to enter the hall without using that door, so to a first approximation there are $n(n-1)^n$ ways for at least one door to remain unused. However, any way that leaves two doors unused gets counted twice, so we have to subtract the extra count. There are $\binom{n}2$ pairs of doors, and there are $(n-2)^n$ ways for a given pair to be unused, so we have to subtract $\binom{n}2(n-2)^n$, getting $n(n-1)^n-\binom{n}2(n-2)^n$ as a second approximation. This requires further correction for the ways that leave three doors unused, and so on all the way to those that leave $n-1$ doors unused. The final total is

$\sum_{k=1}^{n-1}(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=1}^{n-1}(-1)^{n-1-k}\binom{n}kk^n\;.$

  • 0
    @Keegs: Yes, that’s always a nice feeling. You’re welcome!2012-10-11
3

The first solution is correct. Counting even the ways in which $n$ people enter through two doors is not as simple as your Solution $2$ indicates. The $2$ doors can be chosen in $\binom{n}{2}$ ways. Now let each person choose one of these two doors. This can be done in $2^n$ ways. But $2$ of these ways involve everybody choosing the same door. So we end up with $\binom{n}{2}\left(2^n-2 \right)$ ways. For $k$ doors, we get in the same way $\binom{n}{k}$ and $k^n$, but removing the cases where fewer than $k$ doors were actually chosen gets complicated.