## 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

- 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

- 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.