## Using Generating Functions

We defined two binary operations on species :

**Addition**. ;

**Multiplication**. .

These obey and . In total, we’ll talk about five binary operations on species, the least useful of which is the **Cartesian product**: . Since

and

we see that

which is some poorly-understood operation on power series.

Recall that is the species “being a k-element set”: if |X|=k, and otherwise.

Let (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 . 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 . This doesn’t work for the empty set though, but if X is empty, then you’re already done. So . This is sort of like a recursive algorithm for totally ordering a set. Let’s use this to count total orderings now:

and so, rearranging, we get that

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 , and .

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

(note that there’s no n! here).

Now let’s turn the recursive definition into some fact about f.

so we see that , which we can rearrange to two different things: , which gives us a recursive definition for a species with f(x) as its generating function; and , 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:

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 for some and , where is the golden ratio.

2) Expand and using geometric series formulas to get a closed form for .

3) Show that . In fact, is always the closest integer to .

Next time, we’ll continue with our analysis of the Fibonacci numbers using species.

## One thought on “Combinatorics, Lecture 4 (8 Oct 2019)”