Combinatorics, Representing Permutations

Representing Permutations

We can denote a specific permutation simply by enumerating the functional values. For example, If the permutation p = [3 4 2 1 7 5 6 8], then p(1)=3, p(2)=4, p(p(6))=7, etc. Unless otherwise stated, or implied by context, a permutation operates on the integers [1,n].

If p(1) = 3, does that move the item in position 1 to position 3, or does it move the item in position 3 to position 1? I've seen both interpretations in various text books; apparently there is no standard answer.

Sometimes it is more informative to list the cycles of a permutation. The above permutation has the cycles [1 3 2 4], [5 7 6], and [8]. As the permutation is applied repeatedly, these cycles run independently. The element 8 stays in position, while item 1 steps through positions 3 2 4, and back to 1 again.

Some applications require only the lengths of the constituent cycles of a permutation. We sometimes use the notation c_i to indicate a cycle of length i. Thus the permutation given above decomposes into c₄c₃c₁. If c₃ appears twice, we can write c₃², rather than c₃c₃. Finally, + is used to separate distinct permutations. The cycle decomposition of all the 4-element permutations is described by:

6c₄ + 8c₃c₁ + 6c₂c₁² + 3c₂² + c₁⁴

The period of a permutation is the minimum number of repeated invokations required to get back to start. To compute the period, determine the constituent cycles that comprise the permutation. The least common multiple of the lengths of these cycles is the period of the permutation. For example, if a permutation has cycles c₇c₆c₄²c₁, its period is lcm(7,6,4,4,1) = 84.