Consider the permutations of 3 elements: 123, 132, 213, 231, 312, 321. One way to visualize the 3! different permutations is to draw a dot for each element, and then draw an arrow joining adjacent elements:

Each of the diagrams can be turned into a loop by drawing another arrow that joins the last element in a permutation with the first one:

Next, take the dots and arrange them evenly around a circle:

If only the shape of a diagram matters—since a loop doesn’t have a particular beginning or end—each figure is either a counterclockwise arrow (123, 231, and 312) or a clockwise arrow (132, 213, and 321) around the points:

So far, these correspond to the Stirling numbers of the first kind
*s*(*n*, 1).

And if the direction of the arrows doesn’t matter, there’s only one shape:

This is what you’d get if you stretched a rubber band around
*n* nails spaced evenly around a circle.

For *n* points, the number of distinct loops is
*n*!/(2*n*). To begin, the number of permutations of
*n* elements is *n*!. When the first and last elements are
joined to make a loop, the overall count is divided by *n*
because each loop is represented by *n* different permutations,
one starting at each of the points: 123, 231, and 312 are equivalent
counterclockwise loops, and 132, 213, and 321 are equivalent clockwise
loops.

Moreover, because each loop has a clockwise representation and a counterclockwise representation, we can further divide the count by 2 when orientation no longer matters.

For greater values of *n*, then, more shapes are possible. For
example, there are 3 basic ways to twist a rubber band around 4 nails,
corresponding to 4!/(2·4):

For 5 nails, 12 shapes:

And for 6 nails, 60 shapes:

The same reasoning applies to counting necklaces or bracelets made up
of *n* distinct beads, where the points change places for each
permutation but the overall shape is always a circle.

This is sequence A001710 at the Online Encyclopedia of Integer Sequences.

See G. E. Andrews, Number Theory, Dover Publications: New York, 1994, pp. 38–40,
where the shapes are called *stellated p-gons*.

Designed and rendered using *Mathematica* 9.

© 2013–2024 by Robert Dickau.

[ home ] || [ 2013-03-23 ]

www.robertdickau.com/cyclicperms.html