Combinatorial Question May 11, 2009Posted by David Speyer in blegs, combinatorics, things I don't understand.
Here’s something I can prove, but I don’t understand.
Let be the number of trees whose leaves are labeled by , and whose internal vertices all have degree . So counts objects like the tree on the right.
Let . Let be the number of pairings of . So counts objects like the pairing on the left.
Proof: We have the recursive relations and . (Exercise!)
Of course, it is easy to solve these recursions and compute that . This is sequence A001147 in Sloane’s encyclopedia, the so-called double factorial sequence.
Now, let be the number of trivalent trees with vertices which can be embedded in a disc, with the leaves occurring in circular order on the boundary. And let be the number of pairings of which can be embedded in a disc, with the points occurring in circular order around the boundary. The figures below show that .
Proof: We have the recurrences and . (Exercise!)
So the question is: Why? Is there some bijection between trees and matchings under which the condition of having a planar embedding behaves nicely? Are there other examples where we can go between double-factorial objects, with a symmetric group symmetry and Catalan objects with a dihedral symmetry?