There are 7 distinct objects and 10 distinct spots numbered 1-10. Two of spots 7, 8, and 9 must be open. How many ways are there to arrange these objects?
I was helping a friend with this problem and was struggling to understand why our solutions differ numerically. Here are our approaches.
Solution 1:
There are ${3 \choose 2}$ = 3 ways to select the blocked spots, leaving 8 spots open.
There are ${8 \choose 7}$ = 8 ways to select available spots. Multiply by 7! for the total = 24 * 7! = 120,960
Solution 2:
Consider the total number of possibilities – all 3 filled – only 2 filled.
Total: ${10 \choose 7}*7!$ = $\frac{10!}{3!}$
Choose the 7 spots and order the objects.
3 filled: $7 * 6* 5 * {7 \choose 4} * 4! = 7 * 6 * 5 * \frac{7!}{3!}$
Fill the 3 spots (7 choices for spot 1, 6 for 2, 5 for 3), leaving 7 spots available. Choose 4 from these 7 and order the remaining objects.
Only 2 filled: ${3 \choose 2}*7*6*{7 \choose 5}*5! = 3 * 7 * 6 * \frac{7!}{2!}$
Choose the 2 spots to fill, and then fill them with the objects (7 choices for spot 1, 6 for 2). Finally, choose the 5 remaining spots from the 7 available and order the objects. There are only 7 available since we assume the third spot must be open.
Result: $\frac{10!}{3!} – (7 * 6 * 5 * \frac{7!}{3!}) – (3 * 7 * 6 * \frac{7!}{2!})$ = 110,880
I believe Solution 1 is right, but I'm not sure what specifically is wrong with Solution 2. Shouldn't they produce the same number? If not, is Solution 1 wrong?
Best Answer
Here is another way to do it -
First, we choose spots such that exactly two spots out of number $7, 8$ and $9$ are free and one of them has an object. That can be done in
$\displaystyle {3 \cdot {7 \choose 6}} = 21$ ways.
Then we choose spots such that all three spots $7, 8, 9$ are free. There is only one way to do that.
Now we permute objects in $7$ spots.
So total number of arrangements $\displaystyle = 7! \cdot 22 = 110880$
As your first solution triple counts arrangements where $7, 8, 9$ are empty, it can be fixed by subtracting $2 \cdot 7!$.