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

1.7k Views Asked by At

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?

2

There are 2 best solutions below

0
On

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.

0
On

The four employee cars can either leave the chief's place free and park falsely in $D_4=9$ ways, or they use the chief's place, and then the chief coming later would also be in a false place. This can happen in $D_5=44$ ways. It follows that there are $53$ ways for the four cars to park falsely.