Minimal transitive factorizations of a permutation
of type (p, q)

Jang Soo Kim<fnref n="1" />

Seunghyun Seo<fnref n="2" />

Heesung Shin<fnref n="3" />

**Abstract.** We give a combinatorial proof of Goulden and Jackson’s formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type B.

**Résumé.** Nous donnons une preuve combinatoire de formule de Goulden et Jackson pour le nombre de factorisations transitives minimales d'une permutation lorsque la permutation a deux cycles. Nous utilisons le résultat récent de Goulden, Nica, et Oancea sur le nombre de chaînes maximales des partitions non-croisées annulaires de type B.

**Keywords:** minimal transitive factorizations, annular noncrossing partitions, bijective proof

# 1 Introduction

Given an integer partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_\ell)$ of $n$, denote by $\alpha_\lambda$ the permutation

$$ (1 \dots \lambda_1)(\lambda_1 + 1 \dots \lambda_1 + \lambda_2) \dots (n - \lambda_\ell + 1 \dots n) $$

of the set $\{1, 2, \dots, n\}$ in the cycle notation. Let $\mathcal{F}_\lambda$ be the set of all $(n + \ell - 2)$-tuples $(\eta_1, \dots, \eta_{n+\ell-2})$ of transpositions such that

$$ (1) \quad \eta_1 \cdots \eta_{n+\ell-2} = \alpha_\lambda \quad \text{and} $$

$$ (2) \quad \{\eta_1, \dots, \eta_{n+\ell-2}\} \text{ generates the symmetric group } S_n. $$

Such tuples are called minimal transitive factorizations of the permutation $\alpha_\lambda$ of type $\lambda$, which are related to the branched covers of the sphere suggested by Hurwitz [Hur91, Str96].

In 1997, using algebraic methods Goulden and Jackson [GJ97] proved that

$$ |\mathcal{F}_\lambda| = (n + \ell - 2)! n^{\ell-3} \prod_{i=1}^{\ell} \frac{\lambda_i^{\lambda_i}}{(\lambda_i - 1)!} \quad (1) $$

<footnote n="1">¹School of Mathematics, University of Minnesota, Minneapolis, MN, USA</footnote>

<footnote n="2">²Department of Math Education, Kangwon National University, Chuncheon, South Korea</footnote>

<footnote n="3">³Department of Mathematics, Inha University, Incheon, South Korea</footnote>

<footnote n="0">0) Emails: kimjs@math.umn.edu, shyunseo@kangwon.ac.kr, shin@inha.ac.kr</footnote>
Bousquet-Mélou and Schaeffer [BMS00] proved a more general formula than (1) and obtained (1) using the principle of inclusion and exclusion. Irving [Irv09] studied the enumeration of minimal transitive factorizations into cycles instead of transpositions.

If $\lambda = (n)$, the formula (1) yields

$$|\mathcal{F}_{(n)}| = n^{n-2}, \qquad (2)$$

and there are several combinatorial proofs of (2) [Bia02, GY02, Mos89].

If $\lambda = (p, q)$, the formula (1) yields

$$|\mathcal{F}_{(p,q)}| = \frac{pq}{p+q} \binom{p+q}{q} p^p q^q. \qquad (3)$$

A few special cases of (3) have bijective proofs: by Kim and Seo [KS03] for the case $(p, q) = (1, n-1)$, and by Rattan [Rat06] for the cases $(p, q) = (2, n-2)$ and $(p, q) = (3, n-3)$. There are no simple combinatorial proofs for other $(p, q)$.

Recently, Goulden et al. [GNO11] showed that the number of maximal chains in the poset $NC^{(B)}(p, q)$ of annular noncrossing partitions of type $B$ is

$$\binom{p+q}{q} p^p q^q + \sum_{c \ge 1} 2c \binom{p+q}{p-c} p^{p-c} q^{q+c}. \qquad (4)$$

Interestingly it turns out that half the sum in (4) is equal to the number in (3):

$$\sum_{c \ge 1} c \binom{p+q}{p-c} p^{p-c} q^{q+c} = \frac{pq}{p+q} \binom{p+q}{q} p^p q^q.$$

In this paper we will give a combinatorial proof of (3) using the results in [GNO11]. The rest of this paper is organized as follows. In Section 2 we recall the poset $S_{nc}^B(p, q)$ of annular noncrossing permutations of type $B$ which is isomorphic to the poset $NC^{(B)}(p, q)$ of annular noncrossing partitions of type $B$, and show that the number of connected maximal chains in $S_{nc}^B(p, q)$ is equal to $\frac{2pq}{p+q} \binom{p+q}{q} p^p q^q$. In Section 3 we prove that there is a 2-1 map from the set of connected maximal chains in $S_{nc}^B(p, q)$ to $\mathcal{F}_{(p,q)}$, thus completing a combinatorial proof of (3).

We note that the present paper is part of [KSS12]. In the full version [KSS12] we give another combinatorial proof of (3) by introducing marked annular noncrossing permutations of type $A$.

## 2 Connected maximal chains

A signed permutation is a permutation $\sigma$ on $\{\pm 1, \dots, \pm n\}$ satisfying $\sigma(-i) = -\sigma(i)$ for all $i \in \{1, \dots, n\}$. We denote by $B_n$ the set of signed permutations on $\{\pm 1, \dots, \pm n\}$.

We will use the two notations

$$[a_1 a_2 \dots a_k] = (a_1 a_2 \dots a_k - a_1 - a_2 \dots - a_k), \\ ((a_1 a_2 \dots a_k)) = (a_1 a_2 \dots a_k) (-a_1 - a_2 \dots - a_k),$$
<figure><img src="image_1.png" /><figcaption>Fig. 1: The Hasse diagram for $S_{\text{nc}}^{B}(2, 1)$.</figcaption></figure>

and call $[a_1 \ a_2 \ \dots \ a_k]$ a zero cycle and $((a_1 \ a_2 \ \dots \ a_k))$ a paired nonzero cycle. We also call the cycles $\epsilon_i := [i] = (i - i)$ and $((i \ j))$ type B transpositions, or simply transpositions if there is no possibility of confusion.

For $\pi \in B_n$, the absolute length $\ell(\pi)$ is defined to be the smallest integer $k$ such that $\pi$ can be written as a product of $k$ type B transpositions. The absolute order on $B_n$ is defined by

$$ \pi \le \sigma \Leftrightarrow \ell(\sigma) = \ell(\pi) + \ell(\pi^{-1}\sigma). $$

From now, we fix positive integers $p$ and $q$. The poset $S_{\text{nc}}^{B}(p, q)$ of annular noncrossing permutations of type B is defined by

$$ S_{\text{nc}}^{B}(p, q) := [\epsilon, \gamma_{p,q}] = \{\sigma \in B_{p+q} : \epsilon \le \sigma \le \gamma_{p,q}\} \subseteq B_{p+q}, $$

where $\epsilon$ is the identity in $B_{p+q}$ and $\gamma_{p,q} = [1 \ \dots \ p][p+1 \ \dots \ p+q]$. Figure 1 shows the Hasse diagram for $S_{\text{nc}}^{B}(2, 1)$. Then $S_{\text{nc}}^{B}(p, q)$ is a graded poset with rank function

$$ \operatorname{rank}(\sigma) = (p+q) - (\# \text{ of paired nonzero cycles of } \sigma). \qquad (5) $$

Nica and Oancea [NO09] showed that $\sigma \in S_{\text{nc}}^{B}(p, q)$ if and only if $\sigma$ can be drawn without crossing arrows inside an annulus in which the outer circle has integers $1, 2, \dots, p, -1, -2, \dots, -p$ in clockwise order and the inner circle has integers $p+1, p+2, \dots, p+q, -p-1, -p-2, \dots, -p-q$ in counterclockwise order, see Figure 2. They also showed that $S_{\text{nc}}^{B}(p, q)$ is isomorphic to the poset $NC^{(B)}(p, q)$ of annular noncrossing partitions of type B.

A paired nonzero cycle $((a_1 \ a_2 \ \dots \ a_k))$ is called *connected* if the set $\{a_1, \dots, a_k\}$ intersects with both $\{\pm 1, \dots, \pm p\}$ and $\{\pm(p+1), \dots, \pm(p+q)\}$, and *disconnected* otherwise. A zero cycle is always considered to be disconnected. For $\sigma \in S_{\text{nc}}^{B}(p, q)$, the connectivity of $\sigma$ is the number of connected paired nonzero cycles of $\sigma$.
<figure><img src="image_2.png" /><figcaption>Fig. 2: $\pi = ((1\ 5\ 6))((2\ 3\ 4))$ and $\sigma = [1\ 5\ -7\ 2]((3\ 4))$ in $S_{nc}^B(4, 3)$</figcaption></figure>

We say that a maximal chain $C = \{\epsilon = \pi_0 < \pi_1 < \dots < \pi_{p+q} = \gamma_{p,q}\}$ of $S_{nc}^B(p, q)$ is *disconnected* if the connectivity of each $\pi_i$ is zero. Otherwise, $C$ is called *connected*. Denote by $CM(S_{nc}^B(p, q))$ the set of connected maximal chains of $S_{nc}^B(p, q)$.

For a maximal chain $C = \{\pi_0 < \pi_1 < \dots < \pi_n\}$ of the interval $[\pi_0, \pi_n]$, we define $\varphi(C) = (\tau_1, \tau_2, \dots, \tau_n)$, where $\tau_i = \pi_i^{-1}\pi_{i+1}$. Note that each $\tau_i$ is a type B transposition and $\pi_i = \tau_1\tau_2\cdots\tau_i$ for all $i = 1, 2, \dots, n$.

**Lemma 1** If $C$ is a connected maximal chain of $S_{nc}^B(p, q)$, then $\varphi(C)$ has no transpositions of the form $\epsilon_i = [i]$ and has at least one connected transposition. If $C$ is a disconnected maximal chain of $S_{nc}^B(p, q)$, then $\varphi(C)$ has only disconnected transpositions.

**Proof:** By (5), $\sigma$ covers $\pi$ in $S_{nc}^B(p, q)$ if and only if one of the following conditions holds, see [NO09, Proposition 2.2]:

(a) $\pi^{-1}\sigma = \epsilon_i$ and the cycle containing $i$ in $\pi$ is nonzero, i.e., $\pi$ has $((i \cdots))$ and $\sigma$ has $[i \cdots]$.

(b) $\pi^{-1}\sigma = ((i\ j))$ and no two of $i, -i, j, -j$ belong to the same cycle in $\pi$ with $|i| \neq |j|$, i.e., $\pi$ has $((i \cdots))((j \cdots))$ and $\sigma$ has $((i \cdots j \cdots))$.

(c) $\pi^{-1}\sigma = ((i\ j))$ and the cycle containing $i$ in $\pi$ is nonzero and the cycle containing $j$ in $\pi$ is zero with $|i| \neq |j|$, i.e., $\pi$ has $((i \cdots))[j \cdots]$ and $\sigma$ has $[i \cdots j \cdots]$.

(d) $\pi^{-1}\sigma = ((i\ j))$ and $i$ and $-j$ belong to the same nonzero cycle in $\pi$ with $|i| \neq |j|$, i.e., $\pi$ has $((i \cdots -j \cdots))$ and $\sigma$ has $[i \cdots] [-j \cdots]$.

If $\sigma$ covers $\pi$ in $S_{nc}^B(p, q)$, we have $zc(\sigma) \ge zc(\pi)$, where $zc(\sigma)$ is the number of zero cycles in $\sigma$. More precisely we have

$$zc(\sigma) - zc(\pi) = \begin{cases} 0 & \text{if type (b) or (c),} \\ 1 & \text{if type (a),} \\ 2 & \text{if type (d).} \end{cases}$$
Since $\gamma_{p,q}$ has two zero cycles, each $\pi \in S_{nc}^B(p, q)$ has at most two zero cycles. Moreover, if $\pi$ has two zero cycles, then one of them belongs to $\{\pm 1, \dots, \pm p\}$ and the other belongs to $\{\pm(p+1), \dots, \pm(p+q)\}$. Consider a maximal chain $C$ in $S_{nc}^B(p, q)$.

* If $C$ has a permutation $\pi$ with $zc(\pi) = 1$, there are two cover relations of type (a) and no cover relations of type (d) in $C$. For each cover relation $\pi < \sigma$ of type (a), (b), or (c), $\sigma$ is obtained by merging cycles in $\pi$. Since $\gamma_{p,q}$ has only disconnected cycles, all permutations in $C$ are disconnected, which implies that $C$ is disconnected.

* Otherwise, there is a cover relation $\pi < \sigma$ of type (d) in $C$. Then $\sigma$ has two zero cycles $[i \cdots]$ and $[-j \cdots]$, one of which is contained in $\{\pm 1, \dots, \pm p\}$ and the other is contained in $\{\pm(p+1), \dots, \pm(p+q)\}$. Thus $\pi$ has a connected nonzero cycle $((i \cdots -j \cdots))$, and $C$ is connected. Since $C$ has no cover relations of type (a), $\varphi(C)$ has no transposition of the form $\epsilon_i$.

Therefore, if $C$ is a disconnected maximal chain of $S_{nc}^B(p, q)$, then $\varphi(C)$ has two transpositions of the form $\epsilon_i$. So all transpositions of $\varphi(C)$ are disconnected. Also, if $C$ is a connected maximal chain of $S_{nc}^B(p, q)$, then $\varphi(C)$ has no transposition of the form $\epsilon_i$ and has at least one connected transposition. $\square$

The following proposition is a refinement of (4).

**Proposition 2** The number of disconnected maximal chains of $S_{nc}^B(p, q)$ is equal to

$$ \binom{p+q}{q} p^p q^q \qquad (6) $$

and the number of connected maximal chains of $S_{nc}^B(p, q)$ is equal to

$$ \sum_{c \ge 1} 2c \binom{p+q}{p-c} p^{p-c} q^{q+c}. \qquad (7) $$

We now prove the following identity that appears in the introduction. The proof is due to Krattenthaler [Kra].

**Lemma 3** We have

$$ \sum_{c \ge 1} c \binom{p+q}{p-c} p^{p-c} q^{q+c} = \frac{pq}{p+q} \binom{p+q}{q} p^p q^q. \qquad (8) $$

**Proof:** Since $c = p \cdot \frac{q+c}{p+q} - q \cdot \frac{p-c}{p+q}$, we have

$$ \begin{aligned} \sum_{c=0}^{p} c \binom{p+q}{p-c} p^{p-c} q^{q+c} &= \sum_{c=0}^{p} \left( p \cdot \frac{q+c}{p+q} - q \cdot \frac{p-c}{p+q} \right) \binom{p+q}{p-c} p^{p-c} q^{q+c} \\ &= \sum_{c=0}^{p} \left( \binom{p+q-1}{p-c} p^{p-c+1} q^{q+c} - \binom{p+q-1}{p-c-1} p^{p-c} q^{q+c+1} \right) \\ &= \binom{p+q-1}{p} p^{p+1} q^q = \frac{pq}{p+q} \binom{p+q}{p} p^p q^q. \end{aligned} $$
<figure><img src="image_3.png" /><figcaption>Fig. 3: Connected maximal chains in $S_{nc}^B(2, 1)$.</figcaption></figure>

<figure><img src="image_4.png" /></figure>

By Proposition 2 and Lemma 3, we get the following.

**Corollary 4** The number of connected maximal chains of $S_{nc}^B(p, q)$ is equal to

$$ \frac{2pq}{p+q} \begin{pmatrix} p+q \\ q \end{pmatrix} p^q q^q. \qquad (9) $$

For example, Figure 3 illustrates $16 = \binom{4}{3} \binom{2}{1}^2$ connected maximal chains of $S_{nc}^B(2, 1)$.

By Corollary 4, in order to prove (3) combinatorially it is sufficient to find a 2-1 map from $CM(S_{nc}^B(p, q))$ to $F_{(p,q)}$. We will find such a map in the next section.

*Remark 1.* One can check that the factorizations $\varphi(C)$ coming from connected maximal chains $C$ in $S_{nc}^B(p, q)$ are precisely the minimal factorizations of $\gamma_{p,q}$ in the Weyl group $D_{p+q}$. Thus Corollary 4 can be restated as follows: the number of minimal factorizations of $\gamma_{p,q}$ in $D_{p+q}$ is equal to $\frac{2pq}{p+q} \binom{p+q}{q} p^q q^q$. Goupil [Gou95, Theorem 3.1] also proved this result by finding a recurrence relation.

*Remark 2.* Since the proof of Lemma 3 is a simple manipulation, it is easy and straightforward to construct a combinatorial proof for the identity in Lemma 3. Together with the result in Section 3 we get a combinatorial proof of (9). It would be interesting to find a direct bijective proof of (9) without using Lemma 3.

## 3 A 2-1 map from $CM(S_{nc}^B(p, q))$ to $F_{(p,q)}$

Recall that a minimal transitive factorization of $\alpha_{p,q} = (1 \dots p)(p + 1 \dots p + q)$ is a sequence $(\eta_1, \dots, \eta_{p+q})$ of transpositions in $S_{p+q}$ such that

$$ (1) \quad \eta_1 \cdots \eta_{p+q} = \alpha_{p,q} \quad \text{and} $$
(2) $\{\eta_1, \dots, \eta_{p+q}\}$ generates $S_{p+q}$,

and $\mathcal{F}_{(p,q)}$ is the set of minimal transitive factorizations of $\alpha_{p,q}$.
In this section we will prove the following theorem.

**Theorem 5** There is a 2-1 map from the set of connected maximal chains in $S_{nc}^B(p, q)$ to the set $\mathcal{F}_{(p,q)}$ of minimal transitive factorizations of $\alpha_{p,q}$.

In order to prove Theorem 5 we need some definitions.

**Definition 6** (Two maps $(\cdot)^+$ and $|\cdot|$) We introduce the following two maps.

(1) The map $(\cdot)^+$: $B_n \to B_n$ is defined by

$$ \sigma^+(i) = \begin{cases} |\sigma(i)| & \text{if } i > 0, \\ -|\sigma(i)| & \text{if } i < 0. \end{cases} $$

(2) The map $|\cdot|: B_n \to S_n$ is defined by $|\sigma|(i) = |\sigma(i)|$ for all $i \in \{1, \dots, n\}$.

**Definition 7** A $(p+q)$-tuple $(\tau_1, \dots, \tau_{p+q})$ of transpositions in $B_{p+q}$ is called a minimal transitive factorization of type $B$ of $\gamma_{p,q} = [1 \dots p][p+1 \dots p+q]$ if it satisfies

(1) $\tau_1 \dots \tau_{p+q} = \gamma_{p,q}$,

(2) $\{|\tau_1|, \dots, |\tau_{p+q}|\}$ generates $S_{p+q}$.

Denote by $\mathcal{F}_{(p,q)}^{(B)}$ the set of minimal transitive factorizations of type $B$ of $\gamma_{p,q}$.

**Definition 8** A $(p+q)$-tuple $(\sigma_1, \dots, \sigma_{p+q})$ of transpositions in $B_{p+q}$ is called a positive minimal transitive factorization of type $B$ of $\beta_{p,q} = ((1 \dots p)((p+1 \dots p+q))$ if it satisfies

(1) $\sigma_1 \dots \sigma_{p+q} = \beta_{p,q}$,

(2) $\{|\sigma_1|, \dots, |\sigma_{p+q}|\}$ generates $S_{p+q}$,

(3) $\sigma_i = \sigma_i^+$ for all $i = 1, \dots, p+q$.

Denote by $\mathcal{F}_{(p,q)}^{+}$ the set of positive minimal transitive factorizations of type $B$ of $\beta_{p,q}$.

For the rest of this section we will prove the following:

1. The map $\varphi: \mathcal{CM}(S_{nc}^B(p, q)) \to \mathcal{F}_{(p,q)}^{(B)}$ is a bijection. (Lemma 9)

2. There is a 2-1 map $(\cdot)^+ : \mathcal{F}_{(p,q)}^{(B)} \to \mathcal{F}_{(p,q)}^{+}$. (Lemma 11)

3. There is a bijection $|\cdot|: \mathcal{F}_{(p,q)}^{+} \to \mathcal{F}_{(p,q)}$. (Lemma 10)

By the above three statements the composition $|\varphi^+| := |\cdot| \circ (\cdot)^+ \circ \varphi$ is a 2-1 map from $\mathcal{CM}(S_{nc}^B(p, q))$ to $\mathcal{F}_{(p,q)}$, which completes the proof of Theorem 5. Since the proofs of the first and the third statements are simpler, we will present these first.
**Lemma 9** The map $\varphi: CM(S_{nc}^B(p, q)) \to \mathcal{F}_{(p,q)}^{(B)}$ is a bijection.

**Proof:** Given a connected maximal chain $C = \{\epsilon = \pi_0 < \pi_1 < \dots < \pi_{p+q} = \gamma_{p,q}\}$ in $S_{nc}^B(p, q)$, the elements in the sequence $\varphi(C) = (\tau_1, \dots, \tau_{p+q})$ are transpositions with $\tau_1 \cdots \tau_{p+q} = \gamma_{p+q}$. By Lemma 1, at least one of $\tau_i$'s is connected. Thus $\{|\tau_1|, \dots, |\tau_{p+q}|\}$ generates $S_{p+q}$, and $\varphi(C) \in \mathcal{F}_{(p,q)}^{(B)}$. Conversely, if $\tau = (\tau_1, \dots, \tau_{p+q}) \in \mathcal{F}_{(p,q)}^{(B)}$, then $\varphi^{-1}(\tau) = \{\epsilon = \pi_0 < \pi_1 < \dots < \pi_{p+q} = \gamma_{p,q}\}$, where $\pi_i = \tau_1 \cdots \tau_i$, is a connected maximal chain in $S_{nc}^B(p, q)$ because $\{|\tau_1|, \dots, |\tau_{p+q}|\}$ generates $S_{p+q}$. $\square$

**Lemma 10** There is a bijection $|\cdot|: \mathcal{F}_{(p,q)}^{+} \to \mathcal{F}_{(p,q)}$.

**Proof:** Let $(\sigma_1, \dots, \sigma_{p+q}) \in \mathcal{F}_{(p,q)}^+$. Each $\sigma_i$ can be written as $\sigma_i = ((j \ k))$ for some positive integers $j$ and $k$. In this case we let $\eta_i = |\sigma_i| = (j \ k) \in S_{p+q}$. Then the map $|\cdot|: \mathcal{F}_{(p,q)}^+ \to \mathcal{F}_{(p,q)}$ sending $(\sigma_1, \dots, \sigma_{p+q})$ to $(\eta_1, \dots, \eta_{p+q})$ is a bijection. $\square$

Recall $\epsilon_i = [i] = (i - i)$. We write $\overline{((i \ j))} := ((i - j))$. It is easy to see that for $i, j \in \{\pm 1, \dots, \pm(p+q)\}$, we have

$$[i \ j] = \epsilon_i((i \ j)) = ((i \ j))\epsilon_j = \overline{((i \ j))}\epsilon_i = \epsilon_j\overline{((i \ j))}. \qquad (10)$$

**Lemma 11** There is a 2-1 map $(\cdot)^+ : \mathcal{F}_{(p,q)}^{(B)} \to \mathcal{F}_{(p,q)}^+$.

Here we only describe the map $(\cdot)^+$: For $(\tau_1, \tau_2, \dots, \tau_{p+q}) \in \mathcal{F}_{(p,q)}^{(B)}$, we define $(\tau_1, \tau_2, \dots, \tau_{p+q})^+ = (\tau_1^+, \tau_2^+, \dots, \tau_{p+q}^+)$. Since $\tau_1^+ \dots \tau_{p+q}^+ = \gamma_{p,q}^+ = \beta_{p,q}$, we have $(\tau_1, \tau_2, \dots, \tau_{p+q})^+ \in \mathcal{F}_{(p,q)}^+$. Let us fix $\sigma = (\sigma_1, \sigma_2, \dots, \sigma_{p+q}) \in \mathcal{F}_{(p,q)}^+$. If $\tau = (\tau_1, \dots, \tau_{p+q}) \in \mathcal{F}_{(p,q)}^{(B)}$ satisfies $\tau^+ = \sigma$, then $\tau' = (\tau'_1 \dots \tau'_{p+q}) \in \mathcal{F}_{(p,q)}^{(B)}$ defined by

$$\tau'_{i} = \begin{cases} \tau_i & \text{if } \tau_i \text{ is disconnected} \\ \bar{\tau}_i & \text{if } \tau_i \text{ is connected,} \end{cases} \qquad (11)$$

also satisfies $(\tau')^+ = \sigma$. Thus the map $(\cdot)^+ \text{ is two-to-one.}$ For the detailed proof, see [KSS12].

For example, let $\sigma = ((1 \ 2)), ((2 \ 5)), ((2 \ 3)), ((4 \ 5)), ((3 \ 4)) \in \mathcal{F}_{(3,2)}^+$ be the following factorization

$$\beta_{3,2} = ((1 \ 2 \ 3))((4 \ 5)) = ((1 \ 2))((2 \ 5))((2 \ 3))((4 \ 5))((3 \ 4)).$$

Since $\gamma_{3,2} = \epsilon_4 \epsilon_1 \beta_{3,2}$, we can obtain a factorization of $\gamma_{3,2}$ from $\sigma$ as follows:

$$\begin{align*} \gamma_{3,2} &= [1 \ 2 \ 3][4 \ 5] = \epsilon_4 \epsilon_1 ((1 \ 2)) ((2 \ 5)) ((2 \ 3)) ((4 \ 5)) ((3 \ 4)) \\ &= \epsilon_4 \epsilon_2 \overline{((1 \ 2))} ((2 \ 5)) ((2 \ 3)) ((4 \ 5)) ((3 \ 4)) \\ &= \epsilon_4 \epsilon_3 ((1 \ 2)) \overline{((2 \ 5))} ((2 \ 3)) ((4 \ 5)) ((3 \ 4)) \\ &= \epsilon_4 \epsilon_4 ((1 \ 2)) \overline{((2 \ 5))} ((2 \ 3)) \overline{((4 \ 5))} ((3 \ 4)) \\ &= ((1 \ 2)) \overline{((2 \ 5))} ((2 \ 3)) \overline{((4 \ 5))} ((3 \ 4)). \end{align*}$$
Thus $\tau = ((1\ 2), \overline{(2\ 5)}, ((2\ 3)), \overline{(4\ 5)}, \overline{(3\ 4)}) \in \mathcal{F}_{(3,2)}^{(B)}$ satisfies $\tau^+ = \sigma$. The factorization
$\tau' = ((1\ 2), ((2\ 5)), ((2\ 3)), \overline{(4\ 5)}, ((3\ 4))$ obtained by toggling the connected transpositions of $\tau$
also satisfies $(\tau')^+ = \sigma$.

## Acknowledgment

We thank Christian Krattenthaler for the proof of Lemma 3 and the anonymous referees for their valuable comments and suggestions to improve this article. For the second author, this research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2011-0008683). For the third author, this work was supported by INHA UNIVERSITY Research Grant (INHA-44756).

## References

[Bia02] P. Biane. Parking functions of types A and B. *Electron. J. Combin.*, 9(1):Note 7, 5 pp. (electronic), 2002.

[BMS00] Mireille Bousquet-Mélou and Gilles Schaeffer. Enumeration of planar constellations. *Advances in Applied Mathematics*, 24:337–368, 2000.

[GJ97] I. P. Goulden and D. M. Jackson. Transitive factorisations into transpositions and holomorphic mappings on the sphere. *Proc. Amer. Math. Soc.*, 125(1):51–60, 1997.

[GNO11] I. Goulden, Alexandru Nica, and Ion Oancea. Enumerative properties of $NC^{(B)}(p, q)$. *Annals of Combinatorics*, 15:277–303, 2011. 10.1007/s00026-011-0095-4.

[Gou95] Alain Goupil. Reflection decompositions in the classical Weyl groups. *Discrete Math.*, 137(1-3):195–209, 1995.

[GY02] Ian Goulden and Alexander Yong. Tree-like properties of cycle factorizations. *J. Combin. Theory Ser. A*, 98(1):106–117, 2002.

[Hur91] A. Hurwitz. Ueber Riemann'sche Flächen mit gegebenen Verzweigungspunkten. *Math. Ann.*, 39(1):1–60, 1891.

[Irv09] John Irving. Minimal transitive factorizations of permutations into cycles. *Canad. J. Math.*, 61(5):1092–1117, 2009.

[Kra] Christian Krattenthaler. Personal communication.

[KS03] Dongsu Kim and Seunghyun Seo. Transitive cycle factorizations and prime parking functions. *J. Combin. Theory Ser. A*, 104(1):125–135, 2003.

[KSS12] Jang Soo Kim, Seunghyun Seo, and Heesung Shin. Annular noncrossing permutations and minimal transitive factorizations. *ArXiv e-prints*, January 2012. arXiv:1201.5703.
[Mos89] Paul Moszkowski. A solution to a problem of Dénes: a bijection between trees and factorizations of cyclic permutations. *European J. Combin.*, 10(1):13–16, 1989.

[NO09] Alexandru Nica and Ion Oancea. Posets of annular non-crossing partitions of types *B* and *D*. *Discrete Math.*, 309(6):1443–1466, 2009.

[Rat06] Amarpreet Rattan. Permutation factorizations and prime parking functions. *Ann. Comb.*, 10(2):237–254, 2006.

[Str96] Volker Strehl. Minimal transitive products of transpositions—the reconstruction of a proof of A. Hurwitz. *Sém. Lothar. Combin.*, 37:Art. S37c, 12 pp. (electronic), 1996.