Combinatorics, Lecture 4 (8 Oct 2019)

Using Generating Functions

We defined two binary operations on species $\mathsf{S} \to \mathsf{Set}$ :

Addition. $(G+H)(X)=G(X)+H(X)$ ;

Multiplication. $(GH)(X) = \{(Y,g,h) \mid Y \subseteq X, g \in G(Y), h \in H (X \setminus Y)\}$ .

These obey $|G+H| = |G|+|H|$ and $|GH|=|G||H|$ . In total, we’ll talk about five binary operations on species, the least useful of which is the Cartesian product: $(G \times H)(X) = G(X) \times H(X)$ . Since

$|G|(X) = \sum_{n \geq 0} \frac{|G(n)|}{n!} x^n$

and

$|H|(X) = \sum_{n \geq 0} \frac{|H(n)|}{n!} x^n$

we see that

$|G \times H|(X) = \sum_{n \geq 0} \frac{|G(n) \times H(n)|}{n!}x^n = \sum_{n \geq 0} \frac{|G(n)| |H(n)|}{n!}x^n$

which is some poorly-understood operation on power series.

Recall that $A_k$ is the species “being a k-element set”: $A_k(X) = 1$ if |X|=k, and $A_k(X) = 0$ otherwise.

Let $TO \colon \mathsf{S} \to \mathsf{F}$ (TO for total order) be given by TO(X) is the set of total orders (aka “linear orders”, “orders”, “reflexive, transitive, antisymmetric, trichotonous relations”) on X.

For example

TO(3) = {[0 < 1 < 2], [0 < 2 < 1], [1 < 0 < 2], [1 < 2 < 0], [2 < 0 < 1], [2 < 1 < 0]}

so |TO(3)| = 6.

Note $TO \cong A_0 + A_1 TO$ . What this says is “you can construct a total order on X by either: do nothing if X is empty, or select a single point of X and then totally order the rest of the set”.

To put a TO structure on X you can pick one element of X to be the least element, and then put a TO structure on $X \setminus {x}$ . This doesn’t work for the empty set though, but if X is empty, then you’re already done. So $TO \cong A_0 + A_1 \cdot TO = 1 + X \cdot TO$ . This is sort of like a recursive algorithm for totally ordering a set. Let’s use this to count total orderings now:

$|TO| = |A_0+A_1\cdot TO|$
$= |A_0| + |A_1||TO|$
$= 1 + X|TO|$

and so, rearranging, we get that

$|TO| = \frac{1}{1-x}$
$= \sum_{n\geq0} x^n$
$= \sum_{n\geq0} \frac{n!}{n!} x^n$

and so |TO(n)|=n!.

Notice that we used both subtraction and division, which are not really things that we can do with finite sets. The result, however, is obvious, since to totally order an n-element set we choose one element to be the least (n choices), then one to be the next least (n-1 choices), etc., so n(n-1)(n-2)…1=n! choices in total.

Fibonacci numbers

Let’s start with a sequence of numbers, turn it into a generating function, and then find a species with that generating function! All mathematicians are in love with the Fibonacci numbers, which are defined recursively by $F_0 = F_1 = 1$ , and $F_{i+2} = F_{i} + F_{i+1}$ .

Let’s invent a power series coming from this sequence:

$f(x) = \sum_{n\geq0} F_n x^n$

(note that there’s no n! here).
Now let’s turn the recursive definition into some fact about f.

so we see that $f(x)-x-1 = xf(x)-x+x^2f(x)$ , which we can rearrange to two different things: $f(x)=1+xf(x)+x^2f(x)$ , which gives us a recursive definition for a species with f(x) as its generating function; and $f(x)=\frac{1}{1-x-x^2}$ , which is the generating function.

Let’s actually see this function f(x) as the generating function of some species. Starting with the second recursive definition from above, let’s expand it, but we’re going to write it in a funny way:

$f(x)= \frac{1}{1-x-x^2}$
$= 1 + (x+x^2) + (x+x^2)^2 + (x+x^2)^3 +\ldots$
$= 1 + x+x^2 + x^2+2x^3+x^4 + x^3+3x^4+3x^5+x^6\ldots$
$= x^0 + x^1 + (x^2+x^1x^1) + (x^1x^2+x^2x^1+x^1x^1x^1) + \ldots$

Because we wrote it this funny way, we can see that each term is like a list of all the ways one could write a number as the sum of a sequence of 1’s and 2’s. So it describes a partition of an n-element totally ordered set into ordered blocks of size either 1 or 2.

Exercises:
1) Show that $\frac{1}{1-x-x^2} = \frac{A}{x+\phi} + \frac{B}{x-\phi^{-1}}$ for some $A$ and $B$ , where $\phi = \frac{\sqrt{5}+1}{2}$ is the golden ratio.
2) Expand $\frac{1}{x+\phi}$ and $\frac{1}{x-\phi^{-1}}$ using geometric series formulas to get a closed form for $F_n$ .
3) Show that $\lim_{n\to\infty} |F_n - \frac{\phi^{n+1}}{\sqrt{5}}|=0$ . In fact, $F_n$ is always the closest integer to $\frac{\phi^{n+1}}{\sqrt{5}}$ .