What is circular permutation?

Answer 1

A circular permutation is a type of permutation which has no starting point and no ending point. It is a set of elements that has an order, but no reference point. It circles back around on itself and encloses.

For example, think of the number of ways of sitting 5 people around a circular table. If the chairs themselves are ordered then its a regular permutation problem, and is equivalent to sitting in a row at the movie theatre because the seats are as unique as the people who are to be sat. Any object, be it a main course or the hosts seat at a dinner party, or the ends of a row of seats, adds a reference point which makes it a linear permutation problem.

If, on the other hand, the chairs are NOT ordered, the table is round, and all the people are unique... its a circular permutation problem because no seat is unique. There is no reference point that is independent of the people sitting. The uniqueness in seating is a result of a persons placement in relation to other people. It is in fact the first person to sit which creates the reference point in which all other sitters sit relative to.

Another example. Flags on a flag pole can be arranged like a regular (linear) permutation problem, because it is linear in shape and thus has a top (a reference point). But suppose you have 10 Christmas ornaments to arrange on a reef. If there is a reference point, such as a top to the reef whereby we hang the reef, then it is still a regular permutation problem. The hook is the reference point and all ornaments are placed relative to it.

But if the reef has no top or reference, and you can hang the reef any which way you want... then its a circular permutation problem. Once the reef is made it has a fixed ornament order (a circular permutation) but may still be hung differently - depending on how you orientate the reef on the door and where you place the top, it may appear to be a different reef each time. This is because the top reference makes for a different linear permutation for a given circular permutation. Simply put, only so many reefs can be made with 10 Christmas ornaments. If rotating the reef is the only difference between two reefs, then they have the same circular permutation and are in fact the same reef design.

That is the basic idea of a circular permutation.

Suppose there are n objects and we wish to pick kof them to arrange in a circular permutation. The number of circular permutations are...

(k-1)! * nCk =nPk / k

And is sometimes denoted nP'k with a little prime tack mark above the P.

For circular permutations, all elements have to be unique and so without replacement. Unfortunately, I do not know how to solve a circular permutation with replacement problem... nor can I find such references online.

Anyway, the basis of the formula is to take a regular permutation and adjust it for the fact that there is no reference point... any arbitrary starting point is just as good as another and does not increase the multiplicity of the pattern. The pattern on whole is what matters, not where it starts. Regular linear permutations count the same circular pattern k times, once for each of the k unique starting places in that pattern.

An explanation of the math. The nCkfunction computes the number of ways to choosing, without order, k objects from n unique objects. Of those kunique objects, there are (k-1)! circular permutations. We multiply, as per the fundamental counting principle, to account for all possible orders of all possible combinations of picks. Likewise, nPk is the number of ways of permuting kobjects picked from n unique objects. As explained in the previous paragraph, k objects have the potential for k reference points, and so each circular permutation is counted k times when nPk is computed. Both expressions are algebraically equivalent.

If you allow k=n then you are finding the circular permutations of all n-elements of an n-element set, no elements left out. Both expressions simplify into (n-1)!.

Then, I suppose, if you need to get why k elements can be arranged in (k-1)! circular permutations in the first place... what relationship between this and the linear permutations of k elements being k! is there? Bare in mind that when the first person of k people sits at a round table, he is creating the reference point. He is arbitrary, but he also turns the circular permutation into a linear permutation. There are k-1 other people to be sat in k-1 other chairs. Voilà, (k-1)! is the number of permutations that exist under these circumstances.

Up until now I have talked about what is called Fixed Circular permutations. A reef may not have a top, but it does have a front. This makes it fixed.

Now suppose we took something like a bracelet with coloured beads. It is a circular permutation. But you can take that bracelet off of your wrist and turn it around, placing it back on your wrist backwards and so the permutation is now in reverse order. If you are able to do this in your problem, you have what is called Free Circular permutations. Every one unique bracelet, or fixed circular permutation, counts as two: one clockwise and one counter-clockwise. You only need half as many bracelets as there are fixed circular permutations. All you have to do is take the number of fixed circular permutations and divide by two:

nP'k / 2