Difference Between Circular And Linear Permutations

Permutations are the different orders in which a group of objects can be arranged.

The single difference between circular and linear permutations is that circular permutations are the different orders in which a group of objects can be arranged in a circle, whereas linear permutations are the different orders in which a group of objects can be arranged in a straight line.

The formula for circular permutations is obviously not the same as that for linear permutations. For a group of 'n' different objects to be arranged in circular order, the formula is
`P = (n - 1)!`
whereas for the same group of 'n' different objects arranged in linear order, the formula is
`P = n!`
In order to understand the above difference in more detail, read on.

The main difference between a straight line and a circle is that a straight line has a fixed starting point and a fixed ending point, whereas a circle has no fixed starting or ending point. Any point on a circle can be chosen as a starting point and the circle can be drawn from that point.

Thus when you arrange, say, 'n' objects in a straight line, they start with one fixed position and end on a fixed position. On the other hand, when these 'n' objects are arranged in a circle, we can not assign any position to be the starting or ending one. This gives rise to a peculiar property of circular permutations:

When these 'n' objects are arranged in a given order in a circle, and then each object is moved to the position to its right (or left), you get a seemingly different order, but from the mathematical point of view, both orders are same.

For example, the following example shows a group of five differently colored balls arranged in two (seemingly) different circular forms.
Circular Permutations
In the first figure above, the topmost ball is yellow colored while in the second figure, the topmost ball is red. Both the permutations look different, but they are same because in each of the two figures, each ball has the same colored ball to its left and right. For example, consider the yellow colored ball: In both the figures 1 and 2, the ball to its left is red and that to its right is blue. Thus, both the orders above are considered the same.

Now we arrange the same five balls in a straight line.
Linear permutations
The above two orders are considered different because the ball at the starting and ending position are different.

Thus, because a circle does not have a definite starting point, but a straight line does, circular permutations can not be calculated in the same way as linear permutations.

Calculation of Circular Permutations

Circular permutations are calculated by simply fixing one position as the starting and ending position (because the starting and ending points on a circle are always the same). We place any one of the 'n' objects in this fixed position. The remaining (n - 1) objects are now arranged in the remaining (n - 1) positions.
Circular permutations: Fixing one position
 Since we have already fixed one position in the circle, the remaining positions can be considered to be in a straight line, starting from the left of the fixed position and ending on the right of the fixed position (or vice versa).

Thus, in order to calculate the different orders in which the remaining (n - 1) objects can be arranged in the remaining (n - 1) positions, we just need to apply the formula for linear permutations.
`P = (n - 1)!`
The above formula gives the permutations of the (n - 1) objects in the circle's (n - 1) positions. But how does it give us the number of permutations of 'n' objects in the circle?

Now comes in use the concept which we discussed with the first diagram above: In circular permutations, moving all objects by a fixed number of places to their right or left does not change the order. Thus, if we move the fixed position above to any position in the circle (and simultaneously move all the other positions in the circle as well), we will end up with the same order! This is illustrated in the figure below.

Circular permutations: Moving the fixed position gives rise to the same order.

Thus, we can say that the total number of different orders in which 'n' objects can be arranged in a circle are given by
`P = (n - 1)!`

Conclusion

Thus we see that circular permutations are quite different from linear permutations, both in the concept and formulas.

No comments:

Post a Comment

Search This Blog