Combinatorial Species, significance and problems can be solved with it.

Question

Combinatorial Species, is a subject I recently came across when just out of curiosity's sake, looked out for possible interaction between category theory and combinatorics. After awhile I ended up here Learning Combinatorial Species., and later on to this book Combinatorial Species and tree-like structures. For someone comfortable in Category Theory, this may be a very beautiful thing to mull over indeed and creates a flexibility to the theory of generating functions as well, and the latter is of important significance.

Though, in any instance of book/notes I can come up with, didn't find out an "intuitive" application of combinatorial species. Combinatorics, is definitely not about counting anymore, but arguably someone declares that the most funny stuff in it has to do with counting problems (because those sort of problems have more intuition I guess).

So my question has to do with that; Could you give me please an instance of application of Combinatorial Species in Enumerative combinatorics? Any other example of application is welcome too of course!

Last comment: I ain't have problem with it becuse its definition or significance. I'm looking for an intuitive approach of the aforementioned notion (I mentioned the latter, because I want to avoid any possible duplication with other possibly related question on MSE, because I think checked them all and not such an answer/question has been showed up. If such a duplication does exist with an answer though, please feel free to mention it!)

Thank you!

Answer 1

One of the first results is to provide a proof of Cayley's formula for the number of trees on $\{1,\dots,n\}$. To do this, let $\mathcal{T}$ be the class of trees. Then $\frac{d}{ds}\mathcal{T}$ is the class of trees with one vertex removed. This is an unordered collection of smaller trees with a distinguished vertex (the one that was attached to the vertex we removed). Thus

$$ \frac{d}{ds} \mathcal{T} \leftrightarrow \mathcal{E}\left( \frac{sd}{ds}\mathcal{T} \right). $$

(Here $\mathcal{E}(X) = \{X\}$ so that $|\mathcal{E}(\{1,\dots,n\})| = 1$ for all $n$.)

In terms of Generating functions, this says

$$ T'(x) = \exp\left(x T'(X) \right). $$

If we make substitution $A(x) = xT'(x)$ then this says

$$ A(x) = x \exp A(x). $$

Now apply Lagrange-Bürmann inversion to get

$$ \begin{align*} \text{# of trees on $n$ vertices} &= \left[ \frac{x^n}{n!} \right] T(x) \\ &= \frac{1}{n} \left[ \frac{x^{n}}{n!} \right] A(x) \\ &= \frac{1}{n} \left[ \frac{u^{n - 1}}{(n - 1)!} \right] \exp(n u) \\ &= \frac{1}{n} n^{n - 1} \\ &= n^{n - 2}. \end{align*} $$

---

This is fairly basic. What is more impressive is that this technique can prove Lagrange-Bürmann inversion. Let us look at one statement of the theorem:

Let $K$ be a commutative ring containing the rationals. Let $F, G \in K[[u]]$ be formal series and suppose $G$ has a nonzero constant term (not necessarily invertible).

Then the formula $R(x) = xG(R(x))$ has a unique (nonzero) solution in $K[[x]]$.

The coefficients of $F(R(x))$ are given by $$ \left[ \frac{x^n}{n!} \right] F(R(x)) = \left[ \frac{u^{n-1}}{(n - 1)!} \right] F'(u)G(u)^n. $$

In particular, $$ \left[ \frac{x^n}{n!} \right] R(x) = \left[ \frac{u^{n-1}}{(n - 1)!} \right] G(u)^n. $$

To do this, you let $\mathcal{G}$ be the "generic" class $\mathcal{E}$ with weights $g_n$ on sets of size $n$. Then let $\mathcal{F}$ be the "generic" class with weights $f_n$.

Recall the decomposition we had for trees:

$$ \frac{sd}{ds} \mathcal{T} \leftrightarrow \mathcal{X} * \mathcal{E}\left( \frac{sd}{ds} \mathcal{T} \right) $$

where I've introduced a factor of $\mathcal{X}$ on both sides (the generating function for $\mathcal{X}$ is just $x$ by the way). This is the decomposition for rooted trees. Therefore

$$ \mathcal{R} \leftrightarrow \mathcal{X} * \mathcal{G}(\mathcal{R}) $$

defines a recurrence for weighted rooted trees. Consequentially, there must be a unique generating function $R(x)$ that satisfies this recurrence.

Next, $$ \mathcal{F}(\mathcal{R}) $$ is the species of $f_n$-weighted forests of $g_n$-weighted rooted trees. Letting, $N = \{1,\dots,n\}$. The coefficient formula says that

$$ \#\left(\frac{sd}{ds} \mathcal{F}(\mathcal{R}) \right)(N) = \# \left( \frac{sd}{ds}\mathcal{F} * \mathcal G^n \right)(N). $$

There are extra factors added to both sides to make it possible to set up a weighted bijection. Unfortunately it would take too much space to describe this bijection. Anyways, that bijection gives you a combinatorial proof of the Lagrange-Bürmann formula.