# 5 cars in a roundabout traffic

Five cars are driving in a roundabout traffic at the same moment. Each comes from an other direction, and drives less than one full round. Also each car leave the roundabout traffic in an other direction than the other. The cars are forbidden to pass cars in the roundabout traffic. They can leave the roundabout whenever they want, but they drive less than one full round, and in the end all cars are driving in differnt directions.

Question:

How many possible combinations are there for the cars to leave the roundabout ? Give a proof.

The question simply (simply? yes; see the end for comments on one issue that's been raised) asks

how many permutations of five things there are with no fixed points; that is, nothing ending up in the same place as it began.

There is a famous answer to this

for an arbitrary number of things; with $$n$$, the answer is $$n!\left(\frac1{0!}-\frac1{1!}+\frac1{2!}-\cdots\pm\frac1{n!}\right)$$, which is approximately $$n!/e$$. For $$n=5$$ this becomes $$120\left(\frac1{1}-\frac1{1}+\frac12-\frac16+\frac1{24}-\frac1{120}\right)=120-120+60-20+5-1=44$$.

It can be proved

using the so-called inclusion-exclusion principle. For $$S$$ any subset of the things being permuted, let $$A_S$$ be all the permutations for which everything in $$S$$ is a fixed point; then $$|A_S|=(n-|S|)!$$. We want to know how many things are in no $$A_S$$ other than $$A_{\emptyset}$$. Begin by taking $$A_\emptyset$$ itself; then remove all the $$A_S$$ with $$|S|=1$$; now we have removed the permutations with fixed points but gone too far by removing ones with two fixed points twice, so add back the $$A_S$$ with $$|S|=2$$; now, alas, any permutation with three fixed points has been removed three times and added three times, so take those out by removing all the $$A_S$$ with $$|S|=3$$; continuing in this way we get $$|A_\emptyset|-\sum_{|S|=1}|A_S|+\sum_{|S|=2}|A_S|-\cdots$$. Term $$k$$ of this is $$(-1)^k$$ times the sum of $$\binom{n}{k}$$ things each equal to $$(n-k)!$$. Adding the whole thing up we get exactly the series I described.

If

the reasoning leading to $$|A_\emptyset|-\sum_{|S|=1}|A_S|+\sum_{|S|=2}|A_S|-\cdots$$ seems a little handwavy, there is a more rigorous way to express it in terms of the binomial expansion of $$(1-1)^n$$, which you will readily find by putting "inclusion-exclusion principle" into your favourite search engine.

Now, what about that restriction on passing?

It doesn't make any difference. Pick any derangement. Imagine that all the cars enter the roundabout together, go around in the same direction, and leave when they reach their "target" exit. Nothing in this requires that their paths cross. If exiting the roundabout is quick enough, the car behind needn't even slow down :-).

• You may have to show the formula actually works, since the cars each drive less than once around and presumably the roundabout has only one lane so cars cannot pass each other. – RShields Jun 21 at 21:22
• If the cars are forbidden to pass one another then the answer will be different and smaller. @Matti, would you like to clarify? – Gareth McCaughan Jun 21 at 21:23
• The answer may not be smaller. It seems like cars can exit at any time and can "pass" exited cars. Perhaps there's a way to show that cars can't block each other, therefore any rot13(qrenatrzrag) can occur. – RShields Jun 21 at 21:28
• Sorry ! I forgot to mention it. The cars are forbidden to pass other cars in the roundabout traffic. – Matti Jun 21 at 21:28
• Actually, unless I'm confused it's not a problem. I've added some comments on the issue to my answer. – Gareth McCaughan Jun 22 at 1:20