A Staff car park at a school has 13 parking spaces in a row. There are 9 cars to be parked.
i. How many Different arrangements are there for parking the 9 cars and leaving 4 empty spaces?
I did 9! * 40, but the answer is wrong. The answer is 13P9 instead.
My reasoning is:
a) you need to arrange the 9 cars so 9!
b) and then I can slot in the empty spaces in between the cars. So it can be :
1.1 unit of 4 empty spaces
2.1 unit of 2 spaces and 1 unit of 2 spaces.
3.1 unit of 3 spaces and 1 unit of 1 space.
4.1 unit of 1 space and 1 unit of 3 spaces.
And each of these can be slot into 10 slots (in between the cars or at either end of line-up of cars).
So total 10 * 4 = 40.
So that is how I got 9! * 40. Why is my reasoning wrong?
Best Answer
The reason that the answer is $P(13, 9)$ is that we need to select nine of the $13$ spaces for the cars and arrange them in those nine selected spaces, which can be done in $$\binom{13}{9}9! = \frac{13!}{9!4!} \cdot 9! = \frac{13!}{4!} = \frac{13!}{(13 - 9)!} = P(13, 9)$$ ways.
Your method of first arranging the cars in $9!$ ways from left to right, then placing four empty parking spots among the cars can be made to work. Let $x_1$ be the number of parking spaces to the left of the first car. Let $x_i$, $2 \leq i \leq 9$, be the number of parking spaces between the $(i - 1)$st car and $i$th car. Let $x_{10}$ be the number of parking spaces to the right of the ninth car. Since there are a total of four empty parking spaces, $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} = 4 \tag{1}$$ which is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of $10 - 1 = 9$ addition signs in a row of four ones. For instance, $$1 + + + 1 1 + + + 1 + + +$$ corresponds to the solution $x_1 = 1$, $x_2 = x_3 = 0$, $x_4 = 2$, $x_5 = x_6 = 0$, $x_7 = 1$, $x_8 = x_9 = x_{10} = 0$. The number of such solutions is the number of ways we can place nine addition signs in a row of four ones, which is $$\binom{4 + 10 - 1}{10 - 1} = \binom{13}{9}$$ since we must choose which nine of the thirteen positions required for four ones and nine addition signs will be filled with addition signs. Since the cars can be arranged in $9!$ ways and the empty parking spaces can be selected in $\binom{13}{9}$ ways, the number of admissible parking arrangements is $$9!\binom{13}{9} = P(13, 9)$$