[Math] 5 cars, 4 parking places. Derangements and permutations with fixed points

combinatoricsderangementspermutationsprobability

I found an exercise in combinatorics:

In the parking of a building, there a re five parking spots, with their owner cars assigned
to them. One day only four cars arrived. In how many ways can they park so that not one cars
parks on their corresponding spot?

So I think the following way: consider the missing car. It may arrive and park on its own parking spot, there are $5\cdot D_4$ ways of doing that, where $D_n$ is the number of derangements of $n$-element set, or it may arrive and find that his place is already taken. Then it takes someone other's place, thus making a complete derangement of 5 element set. So the total number is $5\cdot D_4+D_5$. Am I thinking correctly?

The real problem I have with this is that I found it in some early pop-quiz some teacher gave during the introduction to probability class. Isn't there an easier way?

Best Answer

Lets split into cases depending on which parking spot is open after the four cars have parked. Number the cars $1-5$ and suppose car $5$ is the one that didn't show up.

Case $1$: Parking spot $5$ is left empty.

In this case there are $D_4=9$ ways for the four cars to park in the other four spots.

Case $2$: Parking spot $1$ is left empty.

Here, if car $1$ parks in spot $5$, then the other three cars fill in with $D_3=2$ ways. If car $1$ parks in any of the other three spots, you can check that there are $3$ ways cars $2-4$ can fill in, making $9$ total. For this case, there are $2+9=11$ ways for the cars to park.

Since parking spots $2-4$ are the same as parking spot $1$ by symmetry, we get $11$ ways for each of those cases too. Altogether we find $9+4\cdot11=\boxed{53}$ ways for the cars to park.

Related Question