cycleexpansion

Cycle expansion is a technique used in combinatorics and graph theory to analyze certain types of permutations and their properties. It is particularly relevant in the study of symmetric groups and their representations. The core idea of cycle expansion is to decompose a permutation into a product of disjoint cycles. Any permutation can be uniquely written as a product of cycles that do not share any elements.

For example, consider the permutation that maps 1 to 2, 2 to 3, and 3 to 1. This can be written in two-line notation as (1 2 3 / 2 3 1). Its disjoint cycle decomposition is (1 2 3). If we have a permutation that maps 1 to 2, 2 to 1, and 3 to 4, 4 to 3, this is represented as (1 2 3 4 / 2 1 4 3). Its disjoint cycle decomposition is (1 2)(3 4).

The length of a cycle is the number of elements it contains. The order of a permutation is the least common multiple of the lengths of its disjoint cycles. Cycle expansion is a fundamental tool for understanding the structure of permutations and for computing various combinatorial quantities related to them, such as the number of permutations with a given cycle structure. It is also used in algorithms for permutation generation and analysis.