genus zero permutation and noncrossing partition

Question

Question

Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), which is the largest possible value. Then there is a bijection from these permutations to the noncrossing partition.

I'm seeking for this bijection.

Motivation

This is a follow-up question of my SE post, the detailed motivation is in my answer. I'll briefly mention it here.

It is the bijective exercise (118) of the book Catalan Number by Richard P.Stanley, which gives one combinatorial interpretation of Catalan number

118. Permutations $u$ of [$n$] such that $u$ and $u(1,2,3, \cdots n)$ have a total of $n+1$ cycles, the largest possible (the permutations u are called permutations of genus 0)

and the solution in this book is

118. A coding of planar maps due to R. Cori, Ast'risque 27 (1975), e 169 pp., when restricted to plane trees, sets up a bijection with item 6. We can also set up a bijection with noncrossing partitions $\pi$ (item 159) by letting the cycles of $u$ be the blocks of $\pi$ with elements written in decreasing order. See S. Dulucq and R. Simion, J. Algebraic Comb. 8 (1998), 169–191.

Partial Solution

This bijection is made precise in the reference

The authors define the genus of $g$ as, \begin{equation} z( g) + z( g^{-1} \tau ) = n+ 1 - 2 \text{genus}_{\tau}( g) \end{equation} where $z(g)$ is the number of cycles of $g$. So we are looking for the bijection from set of genus 0 permutations to noncrossing partitions.

A noncrossing partition is self-explanatory when drawn on circle Fig1.(b) from [2]

In this figure, it represents a permutation (1)(256)(34)(78), which should be the type of bijection Richard P.Stanley is refering to.

But I do not understand why these and only these permutations have genus 0.

Philippe Nadeau's Solution

Let me first prove Lemma 1 of reference [3]

Suppose $g$ is a permutation that has $k$ cycles, and $\theta$ is a transposition. Then $g \theta$ has $k + 1$ cycles if and only if elements exchanged by $\theta$ are in the same cycle of $g$.

Proof:

Without loss of generality, let $\theta$ exchange $1,2$. If $1$ and $2$ are in the same cycle, then it breaks into two cycles: \begin{equation} 1 \rightarrow g( 2 ) \rightarrow \cdots\rightarrow g^{-1}(1) \rightarrow 1 , \quad 2 \rightarrow g(1) \rightarrow \cdots\rightarrow g^{-1}(2) \rightarrow 2 \end{equation}

On the other hand, if they belong to different cycles, then $\theta$ will combine them \begin{equation} 1 \rightarrow g(2) \rightarrow \cdots \rightarrow 2 \rightarrow g( 1 ) \rightarrow \cdots \rightarrow 1 \end{equation} $\square$

Let the Cayley distance(minimal number of transpositions) of $g$ to be $d$, then $z(g) = n - d$. $\tau = (1,2,3,\cdots, n )$ has only 1 cycle. The composition $g \tau$ can at most have $d + 1$ cycles. So the maximal number of cycles $n - d + d+ 1 = n + 1$ can only be reached if the transpositions of $g$ break the cycles of $\tau$ each time applied to it. The resulting $g\tau$ will have noncrossing partition patterns. Counting $g$ is equivalent of counting $g$, so we have the desired bijection.

[1]: Serge Dulucq and Rodica Simion, MR 1648480 Combinatorial statistics on alternating permutations, J. Algebraic Combin. 8 (1998), no. 2, 169--191.

[2]: Rodica Simion, MR 1766277 Noncrossing partitions, Discrete Math. 217 (2000), no. 1-3, 367--409.

[3]: Philippe Biane, MR 1475837 Some properties of crossings and partitions, Discrete Math. 175 (1997), no. 1-3, 41--53.

Answer 1

This was in fact first noticed explicitly by Biane I think, cf. Theorem 1 in Some properties of crossings and partitions.

The idea is that $\sigma$ has genus zero iff you can start from the long cycle $(1\cdots n)$ , multiply it by a series of transpositions to get permutations $\sigma_1,\sigma_2,\ldots, \sigma_k=\sigma$ where $\sigma_i$ has one more cycle than $\sigma_{i-1}$.

This forces the multiplication by a transposition to cut one cycle of $\sigma_i$ in two each time. From there it is an easy exercise to characterize which permutations one can get and why they correspond indeed to noncrossing partitions.