1
$\begingroup$

Could you help me to prove that there is a bijection between ordered trees with $n+1$ leaves and ballot lists with $n$ A's and $n$ B's?

A ballot list is a sequence of A's and B's such that all initial segments contain at least as many Aìs as B's.

  • 0
    yeah, maybe it's a mistake2011-09-20

2 Answers 2

4

Take a balanced ballot list, and connect an innermost $AB$ pair by an arc above the word joining $A$ and $B$. Now act as though that pair has been deleted, and iteratively repeat until all $A$'s and $B$'s have been joined by disjoint arcs (chords). Thinking of the arcs as having endpoints on a horizontal line, the complement of the arcs in the upper half-plane has $n+1$ regions. Put a vertex in the middle of each region, and connect two vertices by drawing edges across all of the chords. This gives a map from balanced ballot lists to trees with ordered leaves, which you can verify is a bijection.

Here is a picture.

...

  • 0
    @Alex: Ah, I didn't notice that discrepancy. I was thinking $n+1$ vertices and not leaves.2011-09-20
1

Here’s a solution for the other possible correct version of the problem.

A full binary tree with $n+1$ leaves has $2n$ edges. Each internal vertex $v$ has a left child and a right child; call the edge from $v$ to its left child its left edge and the edge from $v$ to its right child its right edge. Now do a preorder traversal of the tree.

That is, start at the root, and always go left if you can. If you can’t go left, back up one level. If you’ve just backed up along a left edge, go forward along the corresponding right edge and then revert to the ‘left if you can’ rule. If you’ve just backed up along a right edge, back up one more level and try again, unless this takes you to the root; in that case you’re done. There’s a nice little animation here. As an example, here’s a full binary tree with $4$ leaves; I’ve labelled the vertices $a$ through $g$.

                                  a *                                    / \                                 b *   * c                                  / \                               d *   * e                                    / \                                 f *   * g 

Preorder traversal of this tree starts at the root $a$ and visits the vertices in the following order: $abdbefegebaca$. The forward steps, in order, were $ab$, $bd$, $be$, $ef$, $eg$, and $ac$, going left, left, right, left, right, and right, so I write down the ballot list AABABB.

To see that you always get a ballot list, observe that you always take a left edge before taking the corresponding right edge. To see why every ballot list has a corresponding tree, think about how you could reconstruct the tree from the ballot list.

  • 0
    I did it, it's [here](http://math.stackexchange.com/questions/66221/bijection-between-ordered-trees-with-n1-vertices-and-binary-trees-with-n1-l)2011-09-20