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 .