Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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\;.$$

share|improve this answer
1  
Thanks. This question is from a printed book of old test papers and solutions. The first solution was mine, the second one was from the book. It's nice to know I was right. –  Keegs Oct 11 '12 at 5:44
    
@Keegs: Yes, that’s always a nice feeling. You’re welcome! –  Brian M. Scott Oct 11 '12 at 5:58

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.