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?

Advertisements

2 comments

  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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: