Cyclic Permutations

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:

permutations of 123: 123, 132, ...

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:

permutations joined at the ends

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

permutations joined at the ends, arranged in 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:

3 points, 2 directed loops

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:

1 undirected loop

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!/(2n). 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):

4 points, 3 loops

For 5 nails, 12 shapes:

5 points, 12 loops

And for 6 nails, 60 shapes:

6 points, 60 loops

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.

Copyright © 2013–2017 by Robert Dickau.

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


www.robertdickau.com/cyclicperms.html