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
.