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.