Proving the number of permutations $A,B\;$ with $n+1$ total cycles and $AB=(123\cdots n)$ is $C_n$

Please give a combinatorial proof of the following:

The number of pairs $(A, B)$ of permutations of the set $\{ 1, 2,\ldots,n \}$ such that they have a total of $n+1$ cycles and their composition $AB$ is the permutation $(123 \ldots n)$, is the $n$th catalan number.

Take a plane tree with $n+1$ vertices, take a bipartition and associate to each vertex the cyclic permutation that changes the adjacent edges cyclically.

The products of the cycles of each bipartition give the two permutations.

This is a restriction of a bijection by Cori for planar maps.

The desired product $(123\ldots n)$ increases $n-1$ elements and decreases only one. The number of elements it increases is at most the sum of the numbers of elements increased by each factor. Each $k$-cycle of a permutation increases at most $k-1$ elements. The sum of the lengths of all cycles in $A$ and $B$ together is $2n$. Since there are $n+1$ cycles in total, at most $2n-(n+1)=n-1$ elements can be increased. Since we want to increase $n-1$ elements, the $k$-cycles in $A$ and $B$ must each increase $k-1$ elements, that is, they must cyclically permute the elements in their orbit. Thus, each partition of $\{ 1, 2,\ldots,n \}$ yields at most one candidate for $B$, namely the permutation that cyclically permutes each block of the partition.

However, not all these candidates are suitable. In fact, precisely those permutations that cyclically permute each block of a noncrossing partition are suitable. To see this, consider first this representation of such a permutation $B$ (in red) together with the corresponding factor $A=(123\ldots n)B^{-1}$ (in green):

The fixed points are not shown. Note that all cycles run clockwise as they must. A noncrossing partition with $k$ blocks (corresponding to a permutation $B$ with $k$ cycles) partitions the circle into $n-k+1$ regions outside the blocks: There is one region to begin with, and each $k$-cycle splits one region up into $k$ pieces. As you can convince yourself from the illustration, the factor $A$, which has to move each element to the successor of its preimage under $B$, contains one cycle for each region outside the blocks of $B$. Thus the total number of cycles in $A$ and $B$ is $k+(n-k+1)=n+1$ as required. Note that $A$ also cyclically permutes each block of a noncrossing partition.

Now consider this representation of a permutation $B$ which cyclically permutes each block of a crossing partition (in red), again together with the corresponding factor $A=(123\ldots n)B^{-1}$ (in green):

Note that now the arrows of $A$ don't form counterclockwise cycles. To see that they can't, take any arrow $r$ of $B$ that crosses another arrow of $B$, say, $5\to0$, and find the arrow $s$ that crosses it closest to its origin, in this case $2\to8$. Viewed along $r$, $s$ must go left, since it is part of a clockwise cycle. (If it's part of a $2$-cycle, we can pick the arrow that goes left.) Now take the arrow $t$ of $A$ that gets composed with $s$, in this case $8\to3$. It crosses $r$ closer to the origin of $r$ than $s$ does, or it may end at the origin of $r$ (in this case $5$). Any clockwise cycle of $A$ containing $t$ would have to include an arrow $u$ of $A$ that either crosses $r$ yet closer to its origin, or begins at the origin of $r$. Then the arrow of $B$ that gets composed with $u$ would either cross $r$ yet closer to its origin, which is impossible by assumption, or end at the origin of $r$. The latter is also not possible because this arrow would be coming from the wrong side of $r$ to form a clockwise cycle with $r$.

In summary, the possible values of $B$ are precisely the permutations which cyclically permute each block of a noncrossing partition of $\{1,\dotsc,n\}$. It is well-known to those who know it that the noncrossing partitions of $\{1,\dotsc,n\}$ are counted by the Catalan numbers; a bijection with Dyck paths is exhibited here (section 3, page 5).

The Catalan number, $C_n$, is the number of rooted binary trees with $n+1$ leaves (and hence $n$ non-leaves.) Label the root $1$ and the other non-leaves with the values from $2$ to $n$. Let $\mathcal{T}$ be the set of such labeled binary trees. There are $C_n$ ways to pick the tree and $(n-1)!$ different labelings, so $|\mathcal{T}|=(n-1)!C_n$.

For permutation $A$, let $c(A)$ be the number of cycles in $A$. Let $\mathcal{P}$ be the set of ordered pairs of permutations $(A,B)$ on $\{1,2,...,n\}$ such that $c(A)+c(B)=n+1$ and $AB$ is an $n$-cycle. The number of elements in $\mathcal{P}$ is $(n-1)!$ times the number of such $(A,B)$ with $AB=(123...n)$.

We want to find a 1-1 correspondence between $\mathcal{T}$ and $\mathcal{P}$.

Given a binary tree T, break the tree into left-ward arrows, and convert each arrow into a cycle of $A$. Then break down the tree into right-ward arrows, and make $B$.

Each leaf of the tree is a "terminus" of exactly one of the arrows, so the cycles of $A$ and $B$ add up to the number of leaves, which is $n+1$.

For example, with $n=4$, if $3$ is the left child of $1$, $2$ the right child of $1$, and $4$ the left child of $2$, then we get $A=(13)(24)$, and $B=(12)(3)(4)$.

You can show that the product $AB$ is an $n$-cycle by recursion, noting that $1(AB)^r$ walks first one side of the tree, then the other.

A pair $(A,B)$ cannot result from two different labeled trees because the pair $(A,B)$ encodes the tree, given that the root is $1$. Essentially, we construct a directed graph $G$ on $n$ nodes with edges $(k,kA)$ colored $L$ and edges $(k,kB)$ colored $R$. Now, if $(A,B)$ resulted from a tree $T$, then $G$ is equivalent to $T-\{\text{leaves}\} $ by removing the edge $(k,kA)$ if the distance in $G$ from $1$ to $k$ is greater than or equal to the distance from $1$ to $kA$. Thus, we can see that different labeled trees yield different pairs $(A,B)$.

I am unsure on how to do this next part.

Finally, we need to show that this is onto. Given a pair $(A,B)\in \mathcal{P}$, we need to show how to get the corresponding labeled tree. It certainly can't hurt to started with the graph $G$ we defined above. Then we need to use the fact that $AB$ is an $n$-cycle to prove that we can remove the $n+1$ edges to get a binary tree rooted on $1$. To do so, each removed edge would have to be from a different cycle of $A$ or $B$, since a tree cannot have a cycle. We'd also have to remove both edges into $1$ and one edge into each of the other nodes $2,...,n$, otherwise the resulting directed graph is not a binary tree.

My guess is that you first remove the two edges into $1$, then determine which edge to remove going into node $1(AB)^{k+1}$ recursively based on the edges remaining at that stage. This then removes the requisite $n+1$ edges. How to define the recursive step is still not obvious.