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(n1)(n2)(n3)21n! = n(n-1)(n-2)(n-3) \cdots 2 \cdot 1 possible permutations of nn 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,... 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 2020, 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:

# of trees of size n=(2n2)!n(n1)!2=1n(2n2n1) \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,] [ 1, 1, 2, 3, 5, 8, 13, 21, \cdots ] , and showed that its generating function F(z) \mathcal{F}(z) is equal to

F(z)=z+z2+2z3+3z4+5z5+=z1zz2 \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, fn=fn1+fn2 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 F(z) \mathcal{F}(z) , the GF has two singularities which give an explicit formula for Fibonacci numbers:

fn=15((11+5)n+1(11+5)n+1) 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.

T(x)=z+z2+2z3+5z4+14z5+ \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=k=0n(nk)xkynk (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)(x+y) (x+y)^n = (x+y)(x+y)(x+y)\cdots (x+y) . Taking a specific term from the expansion effectively means making nn choices between either xx or yy and multiplying those out in order. If you were to fix the number of choices of xx ahead of time to kk, then there are nkn - k choices of yy (since they must add up to nn) and there are exactly (nk) 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 (x+y)^n represents.

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

We get 2n2^n terms, each of which is a unique sequence of xx and yy with length nn. We can then say that (x+y)n (x+y)^n "generates" n-length sequences of xx and yy. This is where I should make clear that xx and yy 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 e1+e2+e3+ 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+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, S3S^3 represents the combinatorial species of all 3-letter words. Sf=af+bf+cf+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 SS (i.e. all possible words, no matter how long). This will be denoted as Seq(S) \text{Seq}(S), and it is:

Seq(S)=1=S2+S3+S4+=11S \text{Seq}(S) = 1 = S^2 + S^3 + S^4 + \cdots = \frac{1}{1-S}

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

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

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

PSet(x+y+z)=(1+x)(1+y)(1+z)=1+x+y+z+xy+yz+zx+xyz \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:

MSet(S)=αSSeq(α)=αS11α \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: accabcaccabc, cacbcacacbca, and cccabacccaba are three examples of such. Because ordering is arbitrary, we can set a fixed ordering, such as aabcccaabccc, 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 Seq(z)=1+z+zz+zzz+ \text{Seq}(z) = 1 + z + zz + zzz + \cdots . In this example, aabccc=a2bz3aabccc = 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

MSet(z)=PSet(z)×MSet(z2)\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 MSet(z2)\text{MSet}(z^2). This can be applied iteratively:

MSet(z)=PSet(z)×PSet(z2)×PSet(z4)×PSet(z8)×\text{MSet}(z) = \text{PSet}(z) \times \text{PSet}(z^2) \times \text{PSet}(z^4) \times \text{PSet}(z^8) \times \cdots

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

1+z+z2+z3+z4+=(1+z)(1+z2)(1+z4)(1+z8) 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+S = a + b + c + d + \cdots, its corresponding generating function is S(z)=26zS(z) = 26z (here zz is an arbitrary variable). Since there are 26 letters in the English alphabet, the species SS has 26 elements of size 1 . What about S2S^2? It's the species of two-letter words of which there are 26226^2 possible combinations, so its corresponding GF is S(z)=S(z)2=262z2S(z) = S(z)^2 = 26^2 z^2.

G(z)=a0+a1z+a2z2+a3z3+ \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 a0a_0 "empty" elements, a1a_1 elements of size 1, a2a_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:

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

If we just take a basic generating function like zz (one object of size 1), we get that Seq(z)=1+z+z2+ \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, Seq(z2)=1+z2+z4+z6+\text{Seq}(z^2) = 1 + z^2 + z^4 + z^6 + \cdots is the GF for even numbers. z+z2+z4+z8+z + z^2 + z^4 + z^8 + \cdots is the GF for powers of 22 (notice that the powerset of this GF is Seq(z) \text{Seq}(z) ).

We can build upon this a bit but won't stay for too long. One benefit to equating Seq(z) \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 44 are 1+1+1+1,1+1+2,1+3,3+1,... 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:

Comp(z)=Seq(Seq1(z))=11z1z=1z12z=1+z+2z2+4z3++2n1zn+ \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 nn there are, 2n12^{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+x2x + x^2 instead:

Comp1,2(z)=Seq(z+z2)=11zz2=1+z+2z2+3z3+5z4+ \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

Par(z)=MSet(Seq1(z))=k=111zk \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 Par(z) \text{Par}(z) approach:

Par(z)+14n3eπ2n/3zn+ \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.

T(z)=zSeq(T(z)) \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 T(z)=zSeq(T(z))\mathcal{T}(z)= z \cdot \text{Seq} (\mathcal{T}(z)) .

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

T(z)=z1T(z) \mathcal{T}(z) = \frac{z}{1-\mathcal{T}(z)} T(z)2T(z)+z=0 \mathcal{T}(z)^2 - \mathcal{T}(z) + z = 0 T(z)=114z2 \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:

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

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

(1/2k)=(1/2)(1/21)(1/22)(1/23)k!(1/2k)(12k1)(1/2k2) {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} =(1/2)(1/21)(1/22)(1/2k+1)k! = \frac{(1/2)(1/2 -1)(1/2 - 2)\cdots(1/2 - k + 1)}{k!} =(1)k11135(2k3)2kk! =(-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:

(135(2k3)=(2k2)!246(2k2))=(2k2)!2k1(k1)! (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/2k) {1/2 \choose k} in simpler terms and start to march backwards

(1/2k)=(1)k1(2k2)!22k1k!(k1)!=(1)k1212k1k(2k2k1) {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} 14z=2k=01k(2k2k1)zk \sqrt{1-4z} = -2 \displaystyle\sum_{k=0}^\infty \frac{1}{k} {2k-2 \choose k-1} z^k

Finally,

T(z)=114z2=k=11k(2k2k1)zk \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 1k(2k2k1) \frac{1}{k} {2k-2 \choose k-1} general trees with kk nodes.

Note by Levi Walker
2 months, 4 weeks ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Very good! Haven't seen any of your notes for a while...

Yajat Shamji - 2 months, 4 weeks ago

Log in to reply

Thank you!

Levi Walker - 2 months, 3 weeks ago

Log in to reply

Thank you for this. Your writing is very clear.

Justin Travers - 2 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...