Enumerative Combinatorics: Activities and Exercises

1. Descending Binary Trees.

A decreasing binary tree is a rooted binary plane tree where the vertices are labeled by elements of \([n]\) so that every child has a label that is smaller than its parent. Draw all of the decreasing binary trees for \(n=1,2,3\text{.}\) Solution.

2. Descending Binary Trees and Permutations.

We give a recursive geometric layout of a decreasing binary tree that reveals this bijection. For a vertex \(j\text{,}\) let its depth \(d(j)\) be the distance of vertex \(j\) to the root \(n\text{.}\) Start by placing the root \(n\) at point \((0,0)\text{.}\) Suppose that the parent \(j\) of vertex \(i\) has been placed at \((x, -d)\) where \(d=d(j)\) is the depth of \(j\text{.}\) Place vertex \(i\) at \((x \pm (1/3)^d, -d-1)\text{.}\) Here is an example:

1. What is the permutation corresponding to the above descending binary tree on 8 vertices? Solution.

   \begin{equation*} 72618534 \end{equation*}

2. Go back to your trees in problem 1 and write down the corresponding permutations. Solution.

   See the solution to problem 1

3.

Given a permutation, can you determine the corresponding decreasing binary tree? Try to draw the descending binary trees for the permutations \(38412756\) and \(53147268\text{.}\) Solution.

4. Descending Binary Trees and the Eulerian Numbers.

1. Let \(B_R(n,k)\) be the number of descending binary trees on \(n\) vertices in which \(k-1\) vertices have a right child. Prove that \(B_R(n,k) = A(n,k)\text{.}\) You may assume the mapping in problem 2 is a bijection. Solution.

   We use the bijection described in problem 2. We start with a decreasing binary tree. Suppose that vertex \(k\) has a right child. We claim that there is a descent immediately after \(k\) in the corresponding permutation. Indeed, the label of a child is always smaller that the label of the parent. So all of the vertices to the right of vertex \(k\) have labels that are smaller than \(k\text{.}\) In other words, there is a descent immediately after element \(k\text{.}\)

2. Let \(B_L(n,k)\) be the number of descending binary trees on \(n\) vertices in which \(k-1\) vertices have a left child. Prove that \(B_L(n,k) = A(n,k)\text{.}\) You may assume that part (a) is true. Solution.

   A decreasing binary tree has \(k-1\) left children if and only if it has \((n-1)-(k-1)=n-k\) right children. Using this observation, the previous problem and the mirror symmetry of the Eulerian numbers, we get

   \begin{equation*} B_L(n,k) = B_R(n,n-k+1) = A(n,n-k+1) = A(n,k). \end{equation*}