The set of all permutations on a finite set of n elements forms a group, with the composition of the permutations as the group operation. A permutation can be considered as a bijection (one-to-one correspondence) from the set to itself, and can be represented in the form of cycles. Parity of a permutation is defined based on whether it can be represented as a composition of an odd or even number of transpositions. A transposition is a cycle of length 2, with all other (n-2) elements fixed.
Several interesting combinatorial problems exist in the study of permutations. In particular, the authors of this paper present some interesting proofs for formulas related to factorization of permutations.
Though the content is purely mathematical, the presentation style keeps the material interesting even for those with a limited background. Relevant definitions and sufficient introductory information are provided and make the paper easy to follow.
A factorization of a permutation into two large cycles yields a pair of permutations whose composition equals the original permutation. Given an even permutation, these factors both need to be n-cycles, while for an odd permutation, the first factor needs to be an n-cycle and the second an (n-1)-cycle.
The cyclic type of a permutation is the sequence of the lengths of its cycles written in weakly decreasing order. An ELC factorization of a given cyclic type is an even factorization into two large cycles, whose composition has that cyclic type. Similarly, OLC factorization of a given cyclic type is an odd factorization into an n-cycle and an (n-1)-cycle, with their composition having that specific cyclic type.
With these definitions, the paper then shows combinatorial proofs for various theorems and formulas, organized into sections.
The central result, given in section 2, is that for any odd permutation, the number of OLC factorizations is fixed as a function of the number of elements n, and is shown as 2(n-2)!. The proof involves a directed graph representation, and makes use of a technique based on Lehman sequences. It is interesting here to see that, for any permutation, the number of Lehman sequences is equal to n!.
In section 3, a new combinatorial proof of a previously known result is given. The probability of two -n-cycles, taken at random, forming a k-cycle permutation under their composition (for certain k values) is considered here. Section 4 deals with connecting factorizations and section 5 provides a new proof for a formula on the number of ELC factorizations.
An interested reader should refer to the paper for the complete details.