1. Introduction

Hurwitz number has been a well-known problem studied from different perspectives [1,2]. These perspectives include matrix models, Gro mov–Witten invariants, topological recursion, and classical and quantum integrable systems [1-3]. The Hurwitz number problem has connections to many areas of mathematics, as evidenced by the diverse approaches taken to study it [4-7]. The problem of simple Hurwitz numbers is solved [8]. Overall, Hurwitz numbers have various underlying geometric structures that connect them to diverse areas of mathematics [9,10]. One specific area of research considers how many transpositions in strictly monotone factorizations of a permutation in the symmetric group Sn. Trans positions are one of the simplest types of permutations. Strictly monotone factorizations decompose a permutation into adjacent transpositions while preserving the permuted order. The number of such factorizations gives the Hurwitz number in this case. Understanding monotonic factorizations reveals combinatorial aspects of Hurwitz numbers. More broadly, continuing research on Hurwitz numbers, such as exploring their connections to moduli spaces and integrable systems, can provide insight into complex geometrical objects like higher genus Riemann surfaces. Advancing knowledge of enumerative problems like the Hurwitz enumeration remains an active area of mathematical inquiry. This paper considers the number of transpositions of strictly monotone factorization of a permutation in symmetry group \( {S_{n}} \) .

2. Definitions and Preliminaries

Definition 1. A symmetry group is a subgroup of the group of isometries or rigid motions of a geometric object that maps the object onto itself.

Theorem 1. Every permutation σ can be decomposed into products of dis joint cyclic permutations

Let \( T⊂{S_{n}} \) is the set of transpositions, i.e. \( T \) contains 2-cycles s.t. \( (i,j) \) , \( 1≤i≤j≤n \) . \( T \) can generate \( {S_{n}} \) according to Theorem 1. Obviously, there are many ways to factorize a permutation \( σ \) .

Definition 2. For each permutation \( σ \) , there is a minimal value of r such that the factorization exists, and r is called word norm of σ and denoted \( |σ| \) .

Proposition 1. For every permutation \( σ \) , all factorizations have the same parity.

Proof. If \( σ \) is even, the sign of permutations is \( +1 \) ; if \( σ \) is odd, the sign of permutations is \( -1 \) . Therefore, the sign of a permutation \( σ \) is

\( sgn(σ)={(-1)^{m}} \ \ \ (1) \)

where \( m \) is the number of transpositions in the decomposition. Such decom positions are not unique. If we can prove that \( ∀σ \) is permutation, the sign of \( σ \) , \( sgn(σ) \) , will not change, Proposition 1 has been proved. Since for all \( τ∈T \) , \( {τ^{2}}=i \) , identity element, the parity of \( m \) will not change; the sign of a permutation \( σ \) will not change. Therefore, for every permutation \( σ \) , all factorizations have the same parity.

Theorem 2. \( |σ|=n-c(σ) \) , where \( n \) is the order of the symmetric group and \( c(σ) \) is the number of factors in the unique decomposition of \( σ \) .

Remark. \( c(σ) \) includes 1-cycles (fixed numbers)

Definition 3. The metric function

\( d :{S_{n}}×{S_{n}}→N\ \ \ (2) \)

is defined by \( d(ρ,σ) =|{ρ^{-1}}σ| \) ,

Then, we can define the radius set \( Br(ρ)=\lbrace ρ∈{S_{n}}|d(ρ,σ) \lt r\rbrace \) centered at permutation \( ρ \) .

Definition 4. A Cayley graph is a graph that represents the elements of a group as vertices, with edges connecting vertices corresponding to the action of generators of the group on the elements.

Remark. A group might have different Cayley graphs depend on different generating sets.

The function \( d \) is the distance on the Cayley garph \( {Γ_{n}}=Cay({S_{n}},T) \) , the Cayley graph generated by the transposition subset \( T \) . The vertex set of \( {Γ_{n}} \) is \( {S_{n}} \) , and two permutations \( ρ,σ∈{S_{n}} \) are connected by the edge if and only if \( ∃τ∈T \) such that \( σ=ρτ \) . Besides, \( {Γ_{n}} \) is an undirected graph because \( {τ^{2}}=i \) , the identity permutation \( ∀τ∈T \) since all the elements in \( T \) are transpositions.

3. Unique Monotone Factorization

In this section, we will present Hurwitz enumeration problem in terms of Cayley graph, propose unique monotone factorization theorem, and prove the theorem.

Problem. What is the number of strictly monotone walks from to \( i \) to a permutation \( π \) on the Cayley graph \( {Γ_{n}} \) ?

Given an \( r \) -step walks on \( {Γ_{n}} \) , we define its signature to be the corresponding sequence \( {j_{1}},...,{j_{r}} \) of edge labels. If its signature is a strictly increasing sequence, a walk is strictly monotone. Thus, an \( r \) -step strictly monotone walk from \( i \) to \( σ \) is the same thing as a strictly monotone factorization of σ into r transpositions, i.e. \( σ=({i_{1}},{j_{1}})...({i_{r}},{j_{r}}) \) such that \( {j_{1}} \lt ... \lt {j_{r}} \) .

Theorem 3 (Unique Monotone Factorization). Every permutation \( π∈{S_{n}} \) has a unique strictly monotone factorization, and the length of this factorization is equal to \( |π| \) . That is,

\( {\vec{\vec{W}}^{r}}(π)=\begin{cases} \begin{array}{c} 1, if r=|π| \\ 0, otherwise \end{array} \end{cases}\ \ \ (3) \)

We will use induction hypothesis to prove Theorem 3.

Proof. We first consider \( n=2 \) . \( {S_{2}}=\lbrace i,τ\rbrace \) with \( i \) = (1)(2) and \( τ \) = (12). The complete answer to the Hurwitz enumeration problem for \( n=2 \) is given by

\( {W^{r}}(i)=\begin{cases} \begin{array}{c} 1, if r is even \\ 0, if r is odd \end{array} \end{cases}\ \ \ (4) \)

and

\( {W^{r}}(τ)=\begin{cases} \begin{array}{c} 1, if r is odd \\ 0, if r is even \end{array} \end{cases}\ \ \ (5) \)

If we want the factorization to be strictly monotone, the answer will be

\( {\vec{\vec{W}}^{r}}(i)=\begin{cases} \begin{array}{c} 1, if r=0 \\ 0, otherwise \end{array} \end{cases}\ \ \ (6) \)

and

\( {\vec{\vec{W}}^{r}}(τ)=\begin{cases} \begin{array}{c} 1, if r=1 \\ 0, otherwise \end{array} \end{cases}\ \ \ (7) \)

Let \( n \gt 2 \) and let \( π \) in \( {S_{n}} \) be any permutation. There are 2 cases to consider.

Case 1. \( n \) is fixed point in permutation \( π \) , i.e. \( π(n)=n \) .

The induction hypothesis is \( π∈{S_{n-1}} \) has a unique strictly monotone factorization. Therefore, \( π∈{S_{n}} \) has a unique strictly monotone factorization since we suppose \( π∈{S_{n}} \) .

Case 2. \( n \) is not fixed point in permutation \( π \) , i.e. \( π(n)≠n \) .

Thus,

\( π={π^{ \prime }}(ad)\ \ \ (8) \)

where \( π \prime ∈{S_{n-1}} \) and \( a∈\lbrace 1,...,d-1\rbrace \) . The induction hypothesis is \( {π^{ \prime }} \) has a unique strictly monotone factorization of length equal to \( {|π \prime |_{n-1}} \) . Thus, for \( π∈{S_{n}} \) , the unique strictly monotone factorization of length equal to

\( {|{π^{ \prime }}(ad)|_{n}}={|{π^{ \prime }}|_{n-1}}+1={|π|_{n}}\ \ \ (9) \)

We finally get the result.

4. Conclusion

In conclusion, this paper makes an important contribution to the study of Hurwitz enumeration by using Cayley graph theory and induction to prove the unique monotone factorization theorem. This novel result characterizes the uniqueness of minimal-length monotone factorizations of permutations into transpositions. The core technical innovation is representing permutations as vertices in the Cayley graph, with transpositions as edges. Properties of connectivity and shortest paths in this graphical representation allowed an inductive proof of the theorem. Overall, this provides elegant new connections between the combinatorics of the Hurwitz problem, graph theory, and inductive arguments. Looking forward, the theoretical foundation established here could stimulate new research directions, like exploring links to moduli spaces and integrable systems. The inductive tools used in the proof may also find wider applications in analyzing other combinatorial enumeration problems. By uniting diverse fields including group theory, graphs, and induction, this paper exemplifies how bringing together perspectives from across mathematics can drive progress on deep open questions.