how to count for car arrangement when there are empty spaces? 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? 
 A: 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)$$
A: The 4-empty-spaces can be "slotted in" in several spots...but not ten of them. We can describe where the 4 spaces are by saying where the left-hand-edge of those 4 spaces is, i.e. at position 0, 1, 2, ..., 6, with the last of these meaning that the four spaces are in slots 6,7,8,9.  So there are only 6 possibilities for the 4-spaces. 
What about the 2 + 2 spaces? Well, we can describe where the left-edge of the first pair sits, and where the left edge of the second pair sits. THe left edge of the first pair can be at 0, 1, 2, ..., 8. The left edge of the second pair...well, that's harder. If the first pair is at position 0, it occupies spaces 1 and 2. If you put the other pair at position 2, then you actually have four spaces together, which you've already counted in group one. 
This approach gets worse and worse as you try to work through all the cases, but at the very least, you can see that "10 choices for each of the four cases" isn't the right answer. 
A: If we're going to clump empty spots up like this, there are actually many more categories of clumping -- and each of these ways varies in how many ways the clumps can be distributed.
You're off to a good start with the ones you have: there is the single large clump $(4)$, and three ways to get two clumps $(3,1)$,$(2,2)$,$(1,3)$.  Then there are three ways to get three clumps $(2,1,1)$,$(1,2,1)$,$(1,1,2)$, and one more way to get four clumps $(1,1,1,1)$.  There are in fact $\binom{n - 1}{c - 1}$ ways to partition $n$ identical items into $c$ non-empty clumps.
Having found all our clump layouts, we need to make sure we correctly count the number of ways we can distribute these clumps.  In this problem, there are ten slots to fit clumps into (one before all the cars, one after, and eight between cars); each slot can only hold one clump, and since we're handling order already we won't consider order in counting these, so we just need to choose $c$ locations out of the $10$ we have available: $\binom{10}{c}$.  That is: there are $45$, not $10$, ways to place two clumps.  This gives the relatively nasty-looking summation
$$\sum_{c=1}^{N-n}\binom{n+1}{c}\binom{N-n-1}{c-1}$$
as the number of ways to distribute $n$ identical cars among $N$ parking spaces.  This still doesn't look like $\binom{N}{n}$ though, and as the correct answer shows, it's supposed to!  ...While I have verified that it works, I have not yet been able to manage the algebraic manipulations to prove it.  I might have better luck later, and if so I'll come back and edit then.
