# Unordered increasing trees

In Lecture 7, I described a bijection between permutations on [n] and unordered increasing trees on [0,n], and I asked you to think about:

– why this is a bijection.

– why descents in the permutation correspond to leaves in the tree.

Anyone?

1. $\textbf{1) Why this is a bijection?}$

$U^{-1}$ : Take the biggest number in the second row (in {1,2,3} we take 3) and put on its right their children (in increasing order), taking first those branches with the greater digit.Then, continue with the left number until you use totally the second row.

Inasmuch we could find $U^{-1}$ (a way of going from $U(\pi)$ to the permutation $\pi$), $U(\pi)$ is a bijection.

Image 1:

$\textbf{2)why descents in the permutation correspond to leaves in the tree?}$

In the construction of $U^{-1}$ we find that the end-number of each branch will be follow for a smaller number on the next branch (see Image 1), so every leave of a branch (but not the final branch, because there’s not a next number of it) is, in fact, a descent.

2. Andrés, I could not see your image; but if I understand you correctly, you are describing a variant of “depth-first search”:
http://en.wikipedia.org/wiki/Depth-first_search
I agree that this is the inverse, but it’s not obvious *why* it is the inverse, no?