How does a circular permutation differ from a linear permutation?

Answer 1

For some information, see this link What is circular permutation

It goes to another wiki answers article that I just got done writing, and it is both a description of circular permutations and an explanation of how to compute them.

I am going to make the assumption that you already know what permutations are in general, otherwise you wouldn't be asking for the differences between the two.

Permutations are just ordered arrangements of a set or of a subset of elements.

Take the set {a,b,c}

We can order the elements to form new ordered sets

{a,b,c}

{a,c,b}

{b,a,c}

{b,c,a}

{c,a,b}

{c,b,a}

For a total of six unique orders, or permutations.

Notice that these have a starting point and an ending point... the elements are written in an order, yes, but from left to right in a line.

Suppose that there is no start or end, and the right-end wraps around back to the left-beginning in a closed loop, or circle.

{a,b,c} is the same as {b,c,a} and {c,a,b}. Element 'a' is followed by 'b', which is followed by 'c'... and 'c', if we are in a circle, is followed by 'a'. This order or pattern is true and the same for each of these three permutations. This makes them ONE circular permutation.

In fact, there are only two unique circular permutations for the set {a,b,c}. And those are:

{a,b,c}

{a,c,b}

That is the difference.

Here is a real world example...

Suppose five people are to sit in a row at the movie theatre. Each seat is unique, there are two ends and each seat has a specific position therein, with no regard to who sits where. This is a linear permutation. There are 5! = 120 unique permutations.

Suppose five people are to sit at a round dinner table. The main course is nearest to one seat (a reference point). These five people can sit at the dinner table in 5! = 120 unique permutations. Why? Because each seat is unique. The seats themselves are as unique as the people who are sitting. There is a reference point (the main course) and all seats have a relation to it. It is not unlike numbering the seats themselves.

Suppose five people are to sit at a round empty table. Here, any one seat is as good as the next. There is no reference, each seat is non-unique. It doesnt matter where the first person sits. It is his sitting that creates the reference point, and everyone else may sit relative to him. There are 4! = 24 unique seating permutations for these five people.