# Minimal Factorizations of Permutations into
Star Transpositions

J. Irving<fnref n="1" /> and A. Rattan<fnref n="2" />†

**Abstract.** We give a compact expression for the number of factorizations of any permutation into a minimal number of transpositions of the form $(1i)$. Our result generalizes earlier work of Pak (Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees, Discrete Math. 204:329–335, 1999) in which substantial restrictions were placed on the permutation being factored.

**Résumé.** Nous présentons une expression compacte pour le nombre de factorisations minimales d'une permutation arbitraire de transposition de la forme $(1i)$. Ce résultat généralise le travail passé de Pak (Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees, Discrete Math. 204:329–335, 1999) dans lequel des restrictions substantielles sont imposées sur la permutation étant factorisée.

**Keywords:** factorizations, permutations, star transpositions, symmetric group

## 1 Introduction

It is well known that the symmetric group $S_n$ is generated by various sets of transpositions, and it is natural to ask for the number of decompositions of a permutation into a minimal number of factors from such a set. For instance, a famous paper of Dénes [1] addresses this question when the generating set is taken to consist of all transpositions. Stanley [10] has also considered the problem for the set of Coxeter generators $\{(i i + 1) : 1 \le i < n\}$.

More recently, Pak [9] considered minimal decompositions of permutations relative to the generating set $S = \{(1i) : 2 \le i \le n\}$. The elements of $S$ are called star transpositions because the labelled graph on vertex set $[n] = \{1, \dots, n\}$ obtained from them by interpreting $(ab)$ as an edge between vertices $a$ and $b$ is star-shaped. Pak proves that any permutation $\pi \in S_n$ that fixes 1 and has $m$ cycles of length $k \ge 2$ admits exactly

$$ \frac{k^m (mk + m)!}{n!} \qquad (1) $$

decompositions into the minimal number $n + m - 1$ of star transpositions. He leaves open the problem of extending (1) to more general target permutations $\pi$, and it is the purpose of this paper to answer this question.

<footnote n="1">¹Department of Mathematics and Computing Science, St. Mary's University, Halifax, NS, B3H 3C3, Canada</footnote>

<footnote n="2">²Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA</footnote>

<footnote>†Supported by a NSERC Postdoctoral Fellowship.</footnote>
Our result is best expressed in terms of minimal transitive star factorizations, which we now define. A star factorization of $\pi \in \mathfrak{S}_n$ of length $r$ is an ordered list $f = (\tau_1, \dots, \tau_r)$ of star transpositions $\tau_i$ such that $\tau_1 \cdots \tau_r = \pi$. (i) We say $f$ is minimal if $\pi$ admits no star factorization of length less than $r$, and transitive if the group generated by its factors acts transitively on $[n]$.

Observe that a permutation $\pi = (1 \ b_2 \ \cdots \ b_{\ell_1})(a_1^2 \ \cdots \ a_{\ell_2}^2) \cdots (a_1^m \ \cdots \ a_{\ell_m}^m) \in \mathfrak{S}_n$ with $m$ cycles admits the transitive star factorization

$$ \pi = \underbrace{(1 \ b_{\ell_1})(1 \ b_{\ell_1-1}) \cdots (1 \ b_2)}_{=(1 \ b_2 \cdots b_{\ell_1})} \underbrace{(1 \ a_1^2)(1 \ a_{\ell_2}^2)(1 \ a_{\ell_2-1}^2) \cdots (1 \ a_1^2)}_{=(a_1^2 \cdots a_{\ell_2}^2)} \underbrace{(1 \ a_1^m)(1 \ a_{\ell_m}^m)(1 \ a_{\ell_m-1}^m) \cdots (1 \ a_1^m)}_{=(a_1^m \cdots a_{\ell_m}^m)} $$

of length $\ell_1 - 1 + \sum_{i=2}^{m} (\ell_i + 1) = n + m - 2$. Moreover, it is well known [4, Proposition 2.1] that any transitive star factorization of $\pi$ requires at least this many factors. (ii) Thus a transitive star factorization of $\pi$ of length exactly $n + m - 2$ is said to be minimal transitive. It is easy to see that Pak's factorizations are minimal transitive.

Our main result is the following:

**Theorem 1** Let $\pi \in \mathfrak{S}_n$ be any permutation with cycles of lengths $\ell_1, \dots, \ell_m$. Then there are precisely

$$ \frac{(n+m-2)!}{n!} \ell_1 \cdots \ell_m $$

minimal transitive star factorizations of $\pi$.

Pak's formula (1) is recovered from Theorem 1 by setting $\ell_1 = 1$ and $\ell_2 = \cdots = \ell_{m+1} = k$ and observing that a star factorization of a permutation with no fixed points other than (possibly) 1 must be transitive, since $\pi(a) \neq a$ means any star factorization of $\pi$ involves the factor $(1 \ a)$. It is straightforward to deduce from Theorem 1 the number of minimal (not necessarily transitive) star factorizations of a given permutation:

**Corollary 2** Let $\pi \in \mathfrak{S}_n$ be any permutation with cycles of lengths $\ell_1, \dots, \ell_m$ including exactly $k$ fixed points not equal to 1. Then there are

$$ \frac{(n+m-2(k+1))!}{(n-k)!} \ell_1 \cdots \ell_m $$

minimal star factorizations of $\pi$.

Given the special role played by the symbol 1 in star factorizations, the lack of bias towards this symbol in the enumerative formula of Theorem 1 is quite surprising. Indeed, this symmetry is a very compelling aspect of the theorem, and it is not yet understood. Further comments on this curious symmetry, and recent extensions of these results, will be made in Section 4.

Below we outline a graphical approach to Theorem 1 that employs the well-known connection between factorizations of permutations and embeddings of graphs on surfaces (i.e. maps). Star factorizations

<footnote>(i) We multiply permutations in the usual order, so $\rho\sigma(j) = \rho(\sigma(j))$.</footnote>

<footnote>(ii) In fact, this holds true when arbitrary transposition factors are allowed.</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: The planar map corresponding to (1234567) = (25)(36)(27)(35)(17)(34).</figcaption></figure>

are thus seen to correspond with certain labelled trees, which can themselves be encoded as decorated Dyck sequences and enumerated using the cycle lemma. An alternative proof, using methods deliberately similar to those of [9], can be found in the full version of this extended abstract [7].

## 2 A Graphical Correspondence

Transitive factorizations in the symmetric group are well known to be in correspondence with certain classes of labelled maps, and this connection provides one elegant path to Theorem 1. We shall use a version of the factorization-map correspondence introduced in [6]. An alternative formulation of the factorization-map correspondence, developed with great effect in [8], can be applied here with equal ease.

Let $f = (\tau_1, \dots, \tau_r)$ be a transitive factorization of $\pi \in \mathfrak{S}_n$, where the factors $\tau_i$ are arbitrary transpositions. (That is, the group generated by the $\tau_i$ acts transitively on $[n]$.) Then $f$ naturally induces a graph $G_f$ on $n$ labelled vertices and $r$ labelled edges, as follows: the vertex set of $G_f$ is $[n]$, and there is an edge with label $i$ between vertices $a$ and $b$ whenever $\tau_i = (ab)$. The transitivity of $f$ ensures $G_f$ is connected, so $G_f$ admits a 2-cell embedding in an orientable surface of minimal genus. A unique such map $M_f$ is determined by insisting that the edge labels encountered on clockwise traversals of small circles around the vertices are cyclically increasing. Faces of $M_f$ correspond with the cycles of $\pi$, and the Euler-Poincaré formula thus implies $M_f$ is planar precisely when $f$ is minimal transitive.

**Example 3** The factorization $(1234567) = (25)(36)(27)(35)(17)(34)$ is minimal transitive. Its corresponding planar map is shown in Figure 1. $\square$

The maps corresponding to minimal transitive star factorizations are particularly simple. Consider, for example, the factorization

$$ \tau_1 \quad \tau_2 \quad \tau_3 \quad \tau_4 \quad \tau_5 \quad \tau_6 \quad \tau_7 \quad \tau_8 \quad \tau_9 \quad \tau_{10} \quad \tau_{11} \quad \tau_{12} \quad \tau_{13} \quad \tau_{14} \\ (19)(1\ 11)(19)(1\ 2)(1\ 10)(1\ 5)(1\ 3)(1\ 3)(1\ 4)(1\ 7)(1\ 6)(1\ 6)(1\ 10)(1\ 8) \qquad (2) $$

of

$$ \pi = (1\ 8\ 2)(3)(4\ 5\ 10\ 7)(6)(9\ 11) \in \mathfrak{S}_{11}. \qquad (3) $$

The planar map associated with this factorization is drawn in Figure 2.

Since such a map must be planar with edge labels increasing clockwise around the central vertex 1, no edge $\{1, a\}$ can appear more than twice. When two copies of $\{1, a\}$ are present they enclose a face of the map. It is this face that is associated with the cycle of the target permutation containing symbol $a$, and a vertex $b$ of degree one lies within it precisely when $b$ belongs to this same cycle.
<figure><img src="image_2.png" /><figcaption>Fig. 2: The planar map corresponding to a star factorization, and its reduced form.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 3: From maps to trees.</figcaption></figure>

The canonical labelling of edges around the central vertex makes all but one of the edge labels superfluous. Moreover, the labels of all vertices of degree 1 may be deduced from the target permutation and the labels of the other vertices. Thus all maps corresponding to minimal transitive star factorizations may be reduced in the manner demonstrated on the right of Figure 2.

From this reduced form, create a tree as follows. Begin by placing a vertex with label 1 in the outer face, so that every labelled vertex is naturally associated with one face of the map. Then draw an edge between each labelled vertex and all (non-central) vertices that are incident with its associated face. See Figure 3 for an example.

Let $\pi \in \mathfrak{S}_n$ be any permutation, and suppose it has cycles $\sigma_1, \dots, \sigma_m$, listed in increasing order of least element, with corresponding orbits $O_1, \dots, O_m$ (that is, $O_i$ is the set of symbols moved by $\sigma_i$). Let us write $\mathcal{F}_{\pi}$ for the set of all minimal transitive star factorizations of $\pi$, and $\mathcal{T}_{\pi}$ for the set of all bicoloured plane trees on $m$ labelled white vertices and $n-m$ black vertices in which

1. the root is white with label 1,
2. the non-root white vertices are labelled {$a_2, \dots, a_m$}, where $a_j \in \mathcal{O}_j$,

3. the white vertex with label $a_j$ has $|\mathcal{O}_j| - 1$ black children, for $j = 1, \dots, m$.

Given a factorization $f \in \mathcal{F}_\pi$, the correspondences described above allow us to first transform $f$ into a planar map $M_f$, and then transform $M_f$ into a plane tree $T_f$. Moreover, the full transformation $f \mapsto T_f$ is clearly bijective between $\mathcal{F}_\pi$ and $\mathcal{T}_\pi$, whence $|\mathcal{F}_\pi| = |\mathcal{T}_\pi|$

## 3 Counting Star Factorizations

We now prove Theorem 1 by enumerating the trees of $\mathcal{T}_\pi$, for fixed $\pi \in \mathfrak{S}_n$. The key is to observe that each such tree can be encoded using a Dyck-type sequences.

Assume the notation of the previous section, and for convenience set $\ell_j = |\mathcal{O}_j|$ for $2 \le j \le n$, and $r := n+m-2$. Consider the set of sequences $(d_0, d_1, \dots, d_r)$ whose entries $d_i$ are either 1 or $-\ell_j^{(k_j)}$ for some $j \in \{2, \dots, m\}$ and some $k_j \in \mathcal{O}_j$. Here the exponent $(k_j)$ is considered to be a formal decoration. Of these sequences, let $\mathcal{D}_\pi$ be the subset satisfying the following properties:

* a term of the form $-\ell_j^{(k_j)}$ appears exactly once, for $2 \le j \le m$, and

* all partial sums (ignoring decorations) are positive.

Given a tree $T \in \mathcal{T}_\pi$, create a sequence $d_T \in \mathcal{D}_\pi$ as follows: Traverse the boundary of $T$, beginning at its root and proceeding clockwise, writing 1 whenever a vertex is encountered for the first time, and $-i^{(k)}$ when a white vertex with label $k \ge 2$ and $i-1$ black children is encountered for the last time. For instance, the tree in Figure 3 yields the sequence

$$ (1, 1, 1, -2^{(9)}, 1, 1, 1, 1, -1^{(3)}, 1, 1, 1, -1^{(6)}, -4^{(10)}, 1). \quad (4) $$

The mapping $T \mapsto d_T$ is readily seen to be bijective, and thus $|\mathcal{T}_\pi| = |\mathcal{D}_\pi|$. So we now turn to enumerating $\mathcal{D}_\pi$. Our main tool is the cycle lemma of Dvoretzky and Motzkin [2], one version of which states that any sequence with integral entries $\le 1$ and total sum $s \ge 0$ has exactly $s$ cyclic rotations with all partial sums positive.

Any sequence in $\mathcal{D}_\pi$ is of length $r+1$, consisting of $m-1$ terms of the form $-\ell_j^{(k_j)}$ along with $r+1-(m-1)=n$ entries equal to 1. If we do not insist that partial sums are positive, there are exactly

$$ \frac{(r+1)!}{n!} \cdot \ell_2 \cdots \ell_m $$

sequences of this type, where the factors $\ell_j$ account for all possible choices of the $k_j$. The sequences $(d_0, d_1, \dots, d_r) \in \mathcal{D}_\pi$ we wish to count are further characterized by having all partial sums positive. But since they have total sum (ignoring decorations)

$$ \sum_{i=0}^{r} d_i = n \cdot 1 - (\ell_2 + \cdots + \ell_m) = n - (n - \ell_1) = \ell_1, $$

and since a sequence of length $r+1 = n+m-1$ admits $n+m-1$ cyclic rotations, the cycle lemma implies that

$$ |\mathcal{D}_\pi| = \frac{(n+m-1)!}{n!} \ell_2 \cdots \ell_m \cdot \frac{\ell_1}{n+m-1}. $$

Theorem 1 now follows, since $|\mathcal{F}_\pi| = |\mathcal{T}_\pi| = |\mathcal{D}_\pi|$. $\square$
# 4 Further Questions

Notice that Theorem 1 asserts that the number of minimal transitive star factorizations of a permutation $\pi$ depends only on the conjugacy class of $\pi$ (that is, the length of its cycles). This is certainly not obvious from the formulation of the problem, since one would certainly expect that the length of the cycle of $\pi$ containing symbol 1 would play a special role.

Moreover, Goulden and Jackson [5] have recently extended Theorem 1 to compute the number of transitive star factorizations of any permutation into an *arbitrary* number of factors (that is, minimality is not assumed). Interestingly, they witness the same symmetry in their results: the number of transitive star factorizations of $\pi$ of length $r$ is dependent only on the conjugacy class of $\pi$. Moreover, they observe a very interesting connection between star factorizations and the *Double Hurwitz Problem*, a combinatorial problem concerning transitive factorizations that is of much interest to geometers studying intersection theory.

Finding a simple combinatorial explanation for this curious symmetry remains an interesting open problem. Further open questions regarding star factorizations and their role in the general interplay between factorizations and geometry are discussed in [5].

# References

[1] J. Dénes, *The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs*, Publ. Math. Institute Hung. **4** (1959), 63–70.

[2] A Dvoretzky and T. Motzkin, *A problem of arrangements*, Duke Math. J. **14** (1947), 305–313.

[3] I.P. Goulden and D.M. Jackson, *Combinatorial Enumeration*, Wiley Interscience, New York, 1983.

[4] I.P. Goulden and D.M. Jackson, *Transitive factorizations and holomorphic mappings of the sphere*, Proc. Amer. Math. Soc. **125** (1997), 51–60.

[5] I.P. Goulden and D.M. Jackson, *Transitive powers of Young-Jucys-Murphy elements are central*, ArXiv:0704.1100 (2007).

[6] J. Irving, *Minimal transitive factorizations of permutations into cycles*, Canad. J. Math. (to appear).

[7] J. Irving and A. Rattan, *Minimal factorizations of permutations into star transpositions*, Discrete Math. (to appear).

[8] M. Bousquet-Mélou and G. Schaeffer, *Enumeration of planar constellations*, Adv. in Appl. Math. **24** (2000), 337–368.

[9] I. Pak, *Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees*, Discrete Math. **204** (1999), 329–335.

[10] R.P. Stanley, *On the number of reduced decompositions of elements of coxeter groups*, Europ. J. Combin. **5** (1984), 359–372.