Mfcttrf

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(frac10!-frac11!+frac12!-cdotspmfrac1n!right)$, which is approximately $n!/e$. For $n=5$ this becomes $120left(frac11-frac11+frac12-frac16+frac124-frac1120right)=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_=1|A_S|+sum_|A_S|-cdots$. Term $k$ of this is $(-1)^k$ times the sum of $binomnk$ 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_=1|A_S|+sum_|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 :-).

The answer should be

44, the number of derangements, or permutations with no fixed points, on five elements.

because

no car needs to pass any other if they all arrive at the same time; you can treat the cars' movements as discrete, moving one exit each step, and each car will indeed reach its destination in at most 4 steps without blocking any other cars.