Just last month, I took my Ph.D. qualifying exam at Berkeley. It was a grueling three-hour oral exam, but from it came a gemstone that simply must be shared!
The very first question I was asked was from my advisor, Mark Haiman: “Enumerate [count] the labeled plane trees on $n$ vertices.”
More precisely, let $n$ be a positive integer, and define a labeled plane tree to be a tree with vertices labeled $1,2,\ldots,n$, along with a cyclic ordering of the branches attached to each vertex. (The name “plane tree” refers to the fact that the orderings of the branches determine an embedding of the tree into Euclidean space up to homotopy equivalence.) For instance, say we had the following trees drawn in the plane:
They are isomorphic as graphs but not as plane trees, because the branches around the vertex $1$ have different clockwise cyclic orderings.
So how do we count these trees?
Let’s get our hands dirty and start counting them by brute force. Letting $p_n$ denote the number of distinct plane trees up to isomorphism, it isn’t hard to find that $p_0=0$, $p_1=1$, $p_2=1$, $p_3=3$, $p_4=20$, and with a bit more work, $p_5=210$. Hmm. No obvious pattern jumps out immediately, and the computation gets difficult very quickly as $n$ increases.
Perhaps we can find a generating function for $p_n$ instead. And here is where species play a role.