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.
 A: 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.
A: 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).
A: 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.
