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.

  • $\begingroup$ How do you define "combinatorial proof"? $\endgroup$ – Phira Oct 8 '11 at 16:36
  • $\begingroup$ Counting in two different ways or giving a bijection between two sets one of which is counted by the LHS and the other is counted by the RHS. $\endgroup$ – Eowyn Oct 8 '11 at 16:44
  • $\begingroup$ And what is the second set? $\endgroup$ – Phira Oct 8 '11 at 16:49
  • $\begingroup$ The second set maybe the set of all rooted trees with n + 1 vertices. The number of such trees with n + 1 vertices is the nth Catalan number. $\endgroup$ – babu123 Oct 8 '11 at 16:53
  • 1
    $\begingroup$ @Pierre: I appreciate the kind words! As for what you said, understand that I say that the permutation $(123\cdots n)$ in cycle notation stands for the n-cycle $1\to2,2\to3,\dots,n\to1$ (you are correct that in one-line notation it would be denoted $(23\cdots n 1)$, and that $(123\cdots n)$ understood in one-line notation is the identity). In cycle notation you just write a permutation as disjoint cycles side-by-side, so if the permutation is itself just a single cycle (as here), the notations look exactly the same. $\endgroup$ – anon Oct 12 '11 at 20:12

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.

  • $\begingroup$ That's very nice! How do you show that the product is a single cycle, and that you get all such products this way? $\endgroup$ – joriki Oct 12 '11 at 16:54
  • 1
    $\begingroup$ @joriki The product of the two permutation is just a tour around the tree where you take every second edge which is just as well as every edge turns up two times, so it is a n-cycle. In the other direction the cycles of the permutations tell you where to put your edges and you cannot get a cycle in your graph because then the product would obviously not be an n-cycle and it is a tree because it clearly has the correct number of edges. $\endgroup$ – Phira Oct 12 '11 at 16:58

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

               noncrossing partition

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

               crossing partition

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

  • $\begingroup$ I love the phrase "It is well-known to those who know it." :) $\endgroup$ – Mike Spivey Oct 12 '11 at 23:12
  • 1
    $\begingroup$ @Mike: I do to :-) In fact I learned it here on math.SE and made exactly the same comment as you when I saw it: math.stackexchange.com/questions/33855/… :-) $\endgroup$ – joriki Oct 12 '11 at 23:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.