A bijection between ordered trees and ballot lists 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.

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.

!...