permutations to find number of ways to park cars in circle

Question

In how many ways can $4$ cars park in $6$ places in circular order?

I've used a formula to find the answer: $$\frac{P(6,4)}{4}$$ Is it true? If so, why?

Answer 1

Assuming that a rotation, but not reflection, results in the "same" configuration, you should be dividing by 6, not 4, as there are 6 different rotations (including the null rotation).

Answer 2

By convention, when objects are arranged in a circle, two permutations that can be obtained from each other by rotation are considered to be equivalent, so only the relative order of the objects matters.

Suppose the cars are blue, gray, red, and tan.

Method 1: Park the blue car. We use it as our reference point. Relative to the blue car, there are five ways to park the gray car in one of the remaining positions, four ways to park the red car in one of the remaining positions, and three ways to park the tan car in one of the remaining positions. Hence, there are $$5 \cdot 4 \cdot 3 = 60$$ distinguishable ways to park the four cars in a circle with six positions.

Method 2: As you observed, there are $P(6, 4)$ ways to place four distinct cars in six positions. However, for a given configuration such as the one shown below, there are six rotations that preserve the relative order of the cars.

Since these six rotations are considered to be equivalent, there are $$\frac{1}{6} \cdot P(6, 4) = \frac{1}{6} \cdot \frac{6!}{(6 - 4)!} = \frac{1}{6} \cdot \frac{6!}{2!} = \frac{1}{6} \cdot 6 \cdot 5 \cdot 4 \cdot 3 = 5 \cdot 4 \cdot 3 = 60$$ distinguishable ways to park the four cars in a circle with six positions.

Answer 3

This problem is the same as colouring a $6$ bead necklace in $5$ colours: $\{1,2,3,4,5\}$ so that there is one bead of each colour $1$ to $4$ (the $4$ distinct cars) and two beads of colour $5$ (the two identical empty spaces).

The cycle index polynomial for a $6$ bead necklace is

$$f_G(z_1,z_2,z_3)=\tfrac{1}{6}(z_1^6+z_2^3+z_3^2+3z_6^1)\, .\tag{1}$$

Then Pólya's pattern index for the $5$ colours represented by indeterminates $x_1$ to $x_5$ is found by replacing $z_k^r$ by $(x_1^k+\cdots +x_5^k)^r$ in $(1)$, viz

$$F_G(x_1,\ldots,x_5)=\tfrac{1}{6}((x_1+\cdots + x_5)^6+(x_1^2+\cdots + x_5^2)^3+(x_1^3+\cdots + x_5^3)^2+3(x_1^6+\cdots + x_5^6)^1)\, .$$

We want the coefficient of $x_1^1x_2^1x_3^1x_4^1x_5^2$ in $F_G$.

Clearly this is only yielded by the $(x_1+\cdots + x_5)^6$ term, hence

$$[x_1^1x_2^1x_3^1x_4^1x_5^2]F_G=\frac{1}{6}\cdot\frac{6!}{1!^52!}=60\, .\tag{Answer}$$

What's more, it is possible to see that any colouring of an $n$ bead necklace with at least $1$ colour used on only $1$ bead will simply be

$$\frac{\#(\text{linear colourings})}{n}\tag{2}$$

because a contribution of $x_k^1$ can only come from the first term of the necklace pattern index: $(x_1+\cdots +x_k+\cdots)^n$.

In this case $(2)$ becomes:

$$\frac{6!/(1!^52!)}{6}=60$$

as before.

Answer 4

It's multinomial permutation on a circle with $\{1,1,1,1,2 \}$

MultinomialPermutationsOnACircle[nTuple_] := 
 Module[{n = Total@nTuple, Delta = GCD @@ nTuple}, 
  1/n*Sum[EulerPhi[d]*Multinomial @@@ {#/d & /@ nTuple}, {d, 
     Divisors[Delta]}]]

MultinomialPermutationsOnACircle[{1, 1, 1, 1, 2}]

{60}