Combinatorial Species

This is a continuation of my last note on polynomials as lists. Here, I'm going to talk about the concepts of generating functions and combinatorial species, which extend the ideas from those posts into a more coherent framework.

Combinatorics is concerned with counting instances of structures. "Structure" here is a very broad term. It can refer to anything from permutations, to multisets, to trees. The key thing to these structures is that their size can be talked about in a meaningful way: permutations may act on a given number of elements, multisets likewise, and trees can have a certain number of nodes. The driving idea of combinatorics is to take any one of these structures and determine "how many" there are of a given size. For example, there are $n! = n(n-1)(n-2)(n-3) \cdots 2 \cdot 1$ possible permutations of $n$ elements.

The obvious way to do this is to just enumerate these structures manually. For example, the first few general trees are enumerated in the hand-drawn figure below.

The number of trees for each size grows as $1, 1, 2, 5, 14, 42,...$, but finding this manually becomes intractable as the size of the trees becomes larger. If I were to give you a few minutes to find how many trees there are of size $20$, you definitely wouldn't be able to draw all 1,767,263,190 of them. You would, however, be able to use this closed-form expression to find the answer:

$\text{\# of trees of size n} = \frac{(2n-2)!}{n(n-1)!^2} = \frac{1}{n} { {2n-2} \choose {n - 1}}$

This will be proven later, but for now it's given. The idea here is that simple enumeration won't be enough to study combinatorial structures, so a more efficient approach is needed to gain any information about them. This approach was hinted at in the last post, Polynomials as Lists, where I introduced the idea of using sequences of numbers to create infinite polynomials, known as power series. This can be applied in enumerating combinatorial structures through a specialized kind of power series known as a generating function (GF). In that post I took the Fibonacci sequence, $[ 1, 1, 2, 3, 5, 8, 13, 21, \cdots ]$, and showed that its generating function $\mathcal{F}(z)$ is equal to

$\mathcal{F}(z) = z + z^2 + 2z^3 + 3z^4 + 5z^5 + \cdots = \frac{z}{1-z-z^2}$

This was done by taking advantage of the recurrence relation that Fibonacci numbers have, $f_n = f_{n-1} + f_{n-2}$, and using that on the lefthand side of the equality to find a functional equation that we solved to get the righthand side. A fundamental property of generating functions is that their singularities ultimately determine their coefficients. In the case of $\mathcal{F}(z)$, the GF has two singularities which give an explicit formula for Fibonacci numbers:

$f_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1}{-1 + \sqrt{5}} \right)^{n+1} - \left( \frac{1}{-1 + \sqrt{5}} \right)^{n+1} \right)$

If we were to apply this to the sequence of trees, we get the generating function for general tree structures.

$\mathcal{T}(x) = z + z^2 + 2z^3 + 5z^4 + 14z^5 + \cdots$

Unfortunately, we're unable to get much further in our understanding of this structure since it doesn't have an "easy" recurrence scheme like the Fibonacci numbers. In order to do anything with this GF, we need to know more about what generating functions are and what they represent.

Let's start from the beginning and work our way towards "discovering" generating functions from scratch. We can start with the binomial theorem, which relies on a fairly straightforward combinatoric argument to prove.

$(x + y)^n = \displaystyle\sum_{k=0}^n {{n} \choose {k}} x^k y^{n-k}$

It goes like this; the power on the lefthand side can be broken up into a product: $(x+y)^n = (x+y)(x+y)(x+y)\cdots (x+y)$. Taking a specific term from the expansion effectively means making $n$ choices between either $x$ or $y$ and multiplying those out in order. If you were to fix the number of choices of $x$ ahead of time to $k$, then there are $n - k$ choices of $y$ (since they must add up to $n$) and there are exactly $n \choose k$ different terms of this type.

If we don't group the terms together like in the equation above, then we can more clearly see the structure that $(x+y)^n$ represents.

$(x + y)^1 = x + y$ $(x + y)^2 = xx + xy + yx + yy$ $(x + y)^3 = xxx + xxy + xyx + yxx + xyy + yxy + yyx + yyy$ $(x + y)^4 = xxxx + xxxy + xxyx + xyxx + yxxx + xxyy + xyxy + xyyx + yxyx + yyxx + yxxy + yyyx + yyxy + yxyy + xyyy + yyyy$ $\cdots$

We get $2^n$ terms, each of which is a unique sequence of $x$ and $y$ with length $n$. We can then say that $(x+y)^n$ "generates" n-length sequences of $x$ and $y$. This is where I should make clear that $x$ and $y$ don't necessarily need to be interpreted as numbers. For instance, we can interpret these are actual letters as written. This may seem strange, since you cannot add or multiply letters in a literal sense. The level of abstraction we need comes from the notion of a combinatorial species.

A combinatorial species is roughly a set interpreted in the language of algebra. The "elements" are all written like $e_1 + e_2 + e_3 + \cdots$, where addition represents a disjoint union in the language of sets. Multiplication corresponds to the cartesian product of two sets, or all possible pairs of elements from the two.

Going back to letters, we can say that the English alphabet is the combinatorial species, $S = a+b+c+d+\cdots$. Multiplication can be thought of as just "adding" one letter on the end of another to form a word. Then, for example, $S^3$ represents the combinatorial species of all 3-letter words. $S \cdot f = af + bf + cf + \cdots$ is the combinatorial species of two-letter words ending in f. The possibilities are endless.

We can take this further to ask about the combinatorial species of all sequences of $S$ (i.e. all possible words, no matter how long). This will be denoted as $\text{Seq}(S)$, and it is:

$\text{Seq}(S) = 1 = S^2 + S^3 + S^4 + \cdots = \frac{1}{1-S}$

Here $1$ is included as the "empty" sequence of length $0$, since $S^0=1$. Other structures than sequences can be combinatorically specified. For example, given a set such as $S$, all of its possible subsets (the powerset) may be obtained by:

$\text{PSet}(S) = \displaystyle\prod_{\alpha \in S} (1 + \alpha)$

Where $\alpha$ is a stand-in for any member of the set $S$. To see why this is, take $S = x + y + z$. Then

$\text{PSet}(x + y + z) = (1+x)(1+y)(1+z) = 1 + x + y + z + xy + yz + zx + xyz$

Similarly, multisets may be generated by:

$\text{MSet}(S) = \displaystyle\prod_{\alpha \in S} \text{Seq}(\alpha) = \displaystyle\prod_{\alpha \in S} \frac{1}{1-\alpha}$

If it's not clear why this is, a multiset is a set that can have the same element more than once. Since multisets aren't ordered, then several sequences may represent the same multiset: $accabc$, $cacbca$, and $cccaba$ are three examples of such. Because ordering is arbitrary, we can set a fixed ordering, such as $aabccc$, that uniquely defines a multiset and is a member of this combinatorial class. This decomposes multisets into a product of sequences of a, b, and c, where a sequence of a single variable is the species $\text{Seq}(z) = 1 + z + zz + zzz + \cdots$. In this example, $aabccc = a^2 \cdot b \cdot z^3$.

Some algebraic identities turn into observations from combinatorics. For example, the fact that a multiset may have either an even or an odd number of components results in the identity

$\text{MSet}(z) = \text{PSet}(z) \times \text{MSet}(z^2)$

Where the odd-numbered elements get one element "moved" into a powerset, resulting in a multiset with even numbers of elements. The combinatorial species for the latter is $\text{MSet}(z^2)$. This can be applied iteratively:

$\text{MSet}(z) = \text{PSet}(z) \times \text{PSet}(z^2) \times \text{PSet}(z^4) \times \text{PSet}(z^8) \times \cdots$

When $z$ is a combinatorial species with only one element (more on that soon), this translates into this interesting identity:

$1 + z + z^2 + z^3 + z^4 + \cdots = (1+z)(1+z^2)(1+z^4)(1+z^8)\cdots$

This captures the fact that every number can also be uniquely written as a sum of powers of 2 (i.e in binary).

Combinatorial species are close in form to generating functions. The dfference is that generating functions "equivocate" different elements of the same size. While the species of the alphabet is $S = a + b + c + d + \cdots$, its corresponding generating function is $S(z) = 26z$ (here $z$ is an arbitrary variable). Since there are 26 letters in the English alphabet, the species $S$ has 26 elements of size 1 . What about $S^2$? It's the species of two-letter words of which there are $26^2$ possible combinations, so its corresponding GF is $S(z) = S(z)^2 = 26^2 z^2$.

$\mathcal{G}(z) = a_0 + a_1 z + a_2 z^2 + a_3 z^3 + \cdots$

In general a generating function like the one above represents a combinatorial species with $a_0$ "empty" elements, $a_1$ elements of size 1, $a_2$ of size 2, and so on. This means that enumerating structures of a given size translates to finding the coefficients of the generating function of that structure, and vice-versa. This essentially repackages information about a structure into a single object.

The constructions above can be easily translated into generating functions:

$\text{Seq}(\mathcal{G}(z)) = 1 + \mathcal{G}(z) + \mathcal{G}(z)^2 + \mathcal{G}(z)^3 + \cdots$ $\text{PSet}(\mathcal{G}(z)) = \displaystyle\prod_{k=1} (1 + z^k)^{a_k}$ $\text{MSet}(\mathcal{G}(z)) = \displaystyle\prod_{k=1} \text{Seq}(z^k)^{a_k}$

If we just take a basic generating function like $z$ (one object of size 1), we get that $\text{Seq}(z) =1 + z + z^2 + \cdots$. This is an interesting species because it can be interpreted as representing all natural numbers (there is exactly one element of each size). Likewise, $\text{Seq}(z^2) = 1 + z^2 + z^4 + z^6 + \cdots$ is the GF for even numbers. $z + z^2 + z^4 + z^8 + \cdots$ is the GF for powers of $2$ (notice that the powerset of this GF is $\text{Seq}(z)$).

We can build upon this a bit but won't stay for too long. One benefit to equating $\text{Seq}(z)$ to the GF of natural numbers is that we can talk about compositions and partitions easily. A composition is a way of writing numbers as the sum of smaller numbers. Some of the compositions of $4$ are $1+1+1+1, 1+1+2, 1+3, 3+1, ...$. This can be thought of as a sequence (here, order matters) of natural numbers (excluding 0), or:

$\text{Comp}(z) = \text{Seq}(\text{Seq}_{\ge 1}(z)) = \frac{1}{1 - \frac{z}{1-z}} = \frac{1-z}{1-2z} = 1 + z + 2z^2 + 4z^3 + \cdots + 2^{n-1}z^n + \cdots$

So we immediately know how many compositions of $n$ there are, $2^{n-1}$. We can also limit what numbers are used in compositions, so to find the compositions with only 1 and 2 used, we can look at sequences of the smaller generating function $x + x^2$ instead:

$\text{Comp}_{1, 2}(z) = \text{Seq}(z + z^2) = \frac{1}{1 - z - z^2} = 1 + z + 2z^2 + 3z^3 + 5z^4 + \cdots$

Which is the same as the generating function of the Fibonacci sequence from the beginning of the note, just "shifted over".

A partition is a composition where order no longer matters. It's generating function is then

$\text{Par}(z) = \text{MSet}(\text{Seq}_{\ge 1}(z)) = \displaystyle\prod_{k=1} \frac{1}{1 - z^k}$

While the coefficients of its power series can be calculated recursively, there's no non-recursive formula like what we found with the Fibonacci numbers. We can, however, find that the coefficients of $\text{Par}(z)$ approach:

$\text{Par}(z) \approx \cdots + \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{2n/3}} z^n + \cdots$

We won't prove that now though. We can find interesting constructions and sequences by composing these functions, using restricted base classes, and so on, but can this be extended into recursion? Can a generating function reference itself as a base class? Let's go back to thinking about general trees.

$\mathcal{T}(z) = z \cdot \text{Seq} (\mathcal{T}(z))$

A tree structure will always have a "root" node. Since we're counting the sizes of trees by the number of nodes they have, a tree may be broken up into it's size 1 root node and a sequence of smaller subtrees attached to the root node (the order/topology of the tree matters here). These subtrees are standalone trees themselves, since they contain a root and branches (subtrees) from that root. This "breaking down" process can continue indefinitely, or a root can simply terminate. The combinatorial species of trees is defined in terms of itself, since any member of the species is a node connected to subtrees, so $\mathcal{T}(z)= z \cdot \text{Seq} (\mathcal{T}(z))$.

Solving for $\mathcal{T}(z)$ is pretty straightforward. We have

$\mathcal{T}(z) = \frac{z}{1-\mathcal{T}(z)}$ $\mathcal{T}(z)^2 - \mathcal{T}(z) + z = 0$ $\mathcal{T}(z) = \frac{1 - \sqrt{1-4z}}{2}$

Finding a closed-form formula for trees amounts to finding a series representation of this function. We may use the binomial theorem here on the term of interest:

$\sqrt{1-4z} = \displaystyle\sum_{k=0}^\infty {1/2 \choose k} (-4z)^k$

Finding ${1/2 \choose k}$ is the hard part. Here's what it looks like:

${1/2 \choose k} = \frac{(1/2)(1/2 -1)(1/2 - 2)(1/2 - 3)\cdots}{k! (1/2 - k)(1-2 - k -1)(1/2 -k -2)\cdots}$ $= \frac{(1/2)(1/2 -1)(1/2 - 2)\cdots(1/2 - k + 1)}{k!}$ $=(-1)^{k-1} \frac{1 \cdot 1 \cdot 3 \cdot 5 \cdots (2k-3)}{2^k k!}$

We can "fill in the gaps" on the last term:

$(1 \cdot 3 \cdot 5 \cdots (2k-3) = \frac{(2k-2)!}{2 \cdot 4 \cdot 6 \cdots (2k-2))} = \frac{(2k-2)!}{2^{k-1} (k-1)!}$

So now we can write ${1/2 \choose k}$ in simpler terms and start to march backwards

${1/2 \choose k} = (-1)^{k-1} \frac{(2k-2)!}{2^{2k-1} k! (k-1)!} = (-1)^{k-1} 2^{1-2k} \frac{1}{k} {2k-2 \choose k-1}$ $\sqrt{1-4z} = -2 \displaystyle\sum_{k=0}^\infty \frac{1}{k} {2k-2 \choose k-1} z^k$

Finally,

$\mathcal{T}(z) = \frac{1 - \sqrt{1-4z}}{2} = \displaystyle\sum_{k=1}^\infty \frac{1}{k} {2k-2 \choose k-1} z^k$

Which means that there are exactly $\frac{1}{k} {2k-2 \choose k-1}$ general trees with $k$ nodes.