Combinatorics on minimal transitive factorizations of permutations

Abstract

In this thesis, we give a combinatorial proof for the enumeration of the set ${\mathcal F}_{λ}$ of the minimal transitive factorizations of permutations that have cycle type λ. These factorizations are related to the branched covers of the sphere, which was originally suggested by Hurwitz. In Chapter 2, we introduce some related combinatorial objects - circle chord diagrams, noncrossing partitions, labelled trees, and parking functions. In Chapter 3, we prove that $|{\mathcal F}_{(n)}|=n^{n-2}$, and present an algorithm which generates the elements of ${\mathcal F}_{(n)}$ from parking functions. In Chapter 4, we enumerate some labelled trees combinatorially and count the number of certain parking functions by relating them to labelled trees. In Chapter 5, we give a combinatorial proof of $|{\mathcal F}_{(1,n-1)}|=(n-1)^{n}$ and obtain a refined enumeration of ${\mathcal F}_{(1,n-1)}$ by interpreting them as prime parking functions. In Chapter 6, we construct combinatorial objects whose cardinality is $4(n-1)(n-2)^{n-1}$, and find a bijection from ${\mathcal F}_{(2,n-2)}$ to them.