Combinatorial species

Now that we have the machinery of species, the plane trees problem cracks right open. We will use the following species in our computation:

  • The species $R$ of rooted plane trees, that is, plane trees with one vertex singled out as the root. Notice that there are $n$ times as many rooted plane trees as plane trees on $n$ vertices, so $$\widetilde{R}(x)=\sum_{n\ge 0} \frac{np_n}{n!}x^n=\sum_{n\ge 0} \frac{p_n}{(n-1)!}x^n.$$
  • The species $T$ of ordered rooted trees, that is, a rooted tree such that the children of each node starting from the root have a specified linear ordering.
  • The species $X$ defined by $X([n])=\begin{cases}1 & n=1 \\ \emptyset & n\neq 1\end{cases}$. Notice that $$\widetilde{X}(x)=x.$$
  • The species $C$ of cyclic orderings of $[n]$. Notice that $$\widetilde{C}(x)=\sum_{n\ge 0}\frac{1}{n}x^n=-\ln(1-x).$$
  • The species $L$ of linear orderings of $[n]$. Notice that $$\widetilde{L}(x)=\frac{1}{1-x}.$$

Now, notice that by partitioning a rooted plane tree into its root and its collection of branches with a cyclic ordering on the branches, we have $R=X\cdot (C\odot T)$, as each of the branches can be thought of as a rooted tree along with a linear ordering the children of each node. An example with $1$ as the root, and its branches circled, is shown below.

treespecies

Taking exponential generating functions, we have $$\begin{equation}\widetilde{R}(x)=x\cdot (-\ln(1-\widetilde{T}(x))),\label{eq:one}\end{equation}$$ so we wish to find $\widetilde{T}(x)$. By a similar species argument, $T=X\cdot (L\odot T)$, and so $$\widetilde{T}(x)=\frac{x}{1-\widetilde{T}(x)}.$$ Solving, we find $$\widetilde{T}(x)=\frac{1-\sqrt{1-4x}}{2},$$ and combining this with equation $\eqref{eq:one}$ we find $$\widetilde{R}(x)=-x\ln\left(\frac{1+\sqrt{1-4x}}{2}\right).$$

We’re almost there: now we just have to extract the coefficients. We have $$\left(\frac{\widetilde{R}(x)}{x}\right)’=\sum_{n\ge 0} \frac{p_{n+2}}{n!} x^n,$$ and by our formula for $\widetilde{R}(x)$,
$$\begin{eqnarray*}
\left(\frac{\widetilde{R}(x)}{x}\right)’ &=& \frac{2}{1+\sqrt{1-4x}}\cdot\frac{1}{\sqrt{1-4x}} \\
&=& \frac{2}{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{4x}\right) \\
&=& \frac{1}{2x}(-1+(1-4x)^{-1/2}) \\
&=& \frac{1}{2x}\left(\sum_{k=1}^\infty (-1)^k\binom{-1/2}{k}4^k x^k\right) \\
&=& \sum_{k=0}^\infty (-1)^{k+1} 2^{2k+1} \binom{-1/2}{k} x^k \\
&=& \sum_{k=0}^\infty 2^{2k+1} \frac{(1/2)(3/2)\cdots ((2k+1)/2)}{(k+1)!} x^k \\
&=& \sum_{k=0}^\infty 2^k\frac{(2k+1)!!}{k+1} \frac{x^k}{k!} \\
\end{eqnarray*}$$ (Here $(2k+1)!!$ means $1\cdot 3 \cdot 5 \cdot\cdots\cdot (2k+1)$.)

And so, comparing coefficients, we conclude that $$p_{n+2}=2^n\frac{(2n+1)!!}{(n+1)}$$ for all $n\ge 0$. Indeed, this checks out with our previous computations of $p_2=1$, $p_3=3$, $p_4=20$, and $p_5=210$.

So species have saved the day… but now that we know the formula for $p_n$, can we find a direct combinatorial proof? I haven’t found one yet, so feel free to comment with ideas!

3 thoughts on “Combinatorial species

  1. 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. 🙂

  2. 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

Leave a Reply

Your email address will not be published. Required fields are marked *