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.
Excellent post, brings back great memories! I had the extraordinary privilege of meeting and interacting with some of the founders and early proponents of the theory – Andre Joyal (a truly fascinating character), Pierre Leroux (who unfortunately passed away in 2008), the Labelle brothers (one of whom also happens to be a brilliant chess player) and Francois Bergeron (a polymath in the best sense of the word). They definitely played a major role in my decision to go into mathematics research. I’m sure the rest of your quals went well after such an inspiring start 🙂
Oh wow! I’ve never met the people you mentioned myself – I learned about species from Mark Haiman last year.
The exam did go pretty well after that. The algebraic geometry section gave me some trouble, but overall it was a fun exam. 🙂
Hi,
While searching for a proof, I fell on the disimmetry theorem – which is another mind blowing argument – and here is my comment.
Take for example, a necklace o-o-o-o-o-o. It has a “canonical” middle edge and two canonical ends that could be depicted by: x-o-o—o-o-x. These particular specifications are critical for the proof. Meanwhile, the associated species is E2(X.X.X).
This species has no middles, no ends and no edges. The only thing that the above combinatorial species has is the permutation group of order two and degree six, generated by (1 2) (3 4) (5 6).
Similarly, once written the species relation R = X.C(T), the trees as we knew them are not anymore there…
Lovely article,
Best regards