Tags: #theorem

Statement

The number of increasing binary trees with $n$ vertices and $k$ left edges is $A(n,k)$ (the Eulerian numbers)

Proof

We define a bijection between permutations in $S_n$ and increasing binary trees on $n$ vertices.

Suppose we have some $w\in S_n$. We shall iteratively construct a tree $T(w)$ as follows:

• Find the smallest number in $w$. Make that the root $r$, and everything to the left of it will be $A$ and to the right will be $B$.
• Then, create a tree by connecting $T(A)$ as the left child of $r$ and $T(B)$ the right child of $r$

Example: $w=9,6,12,4,3,10,8,1,2,7,5,11$

You might notice that the reading order of the tree will be equal to $w$, which is how you construct the inverse to this operation.

To conclude the statement, we have to show the following: If $w\mapsto T(w)$, then the number of descents of $w$ is equal to the number of left edges of $T(w)$.
Sketch: If some vertex $i$ with parent $j$ has no left child, then in the permutation $j,i$ will be next to each other in that order, and this will create an ascent (since $i>j$). Thus, we have a correspondence between no left edges and ascents. In other words, if there is a left edge, then we have a descent.