Cycle Type
One concept I’d like to introduce is that of the “cycle type” of a permutation. This simply counts the number of cycles of various length in a permutation. For example — using the sample permutations from last time — has two cycles of length two, while has one cycle of length three and one “fixed point” — a cycle of length one. No cycle in a permutation in can be longer than , so we only need to count up to . We collect the information in a cycle type into a tuple of the form . The cycle type of is , and that of is .
It should be clear that the sum of the cycle lengths is . In a formula:
That is, the cycle type breaks up or “partitions” into chunks whose total size adds up to . In general, a partition of is a sequence of numbers in nonincreasing order, whose sum is . Thus the cycle type of gives us the partition , while the cycle type of gives us the partition .
One more example, from the beginning: the two-line notation
describing a permutation in has the cycle notation . Its cycle type is , which corresponds to the partition .
[…] to each symbol in the cycle notation. In particular, any two conjugate permutations have the same cycle type. In fact, the converse is also true: given any two permutations with the same cycle type, we can […]
Pingback by Conjugates « The Unapologetic Mathematician | September 10, 2010 |