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{.}\)

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?

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

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{.}\)

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.

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.