Thanks to Tim Hosgood for helping me type these notes up.

Previous lecture here.

## Fibonacci and `tribonacci’ numbers

Recall: there’s a species with

G(X) = {ways to totally order X and chop it into blocks of length 1 or 2}

For example,

We saw that

where is the n-th Fibonacci number. Note that ; it’s not . We also saw that which implies that . This would follow from if were a species with . Before, we talked about as the species of “being a k-element set”, with

but this gives that . What we now want is , the species of “being a totally-ordered k-element set”, with

so that .

To totally order X and chop it into blocks of length 1 or 2, you just

- see if , and stop if so; otherwise
- chop X into two subsets: the first with 1 element, and the second totally ordered and chopped into blocks of length 1 or 2; or
- chop X into two subsets: the first with 2 elements, and the second totally ordered and chopped into blocks of length 1 or 2.

Note that gave us . Going one level further, with gave us and the Fibonacci numbers.

Going yet one more level, we get the **tribonacci numbers**, which are those that follow

i.e. 1, 1, 1, 3, 5, 9, 17, 31, …

Indeed, there’s a species with , and we can show (using the same ideas) that , and that

= |{ ways to chop {0, … , n-1} into blocks of length 1, 2, or 3}|.

## Trees

Let be the species with

B(X) = {binary rooted planar trees with leaves equipped with a bijection to X}

as in Lecture 3. Notice that

|B(n)|= n! |{binary rooted planar trees}|

since a B-structure on X is a total ordering along with a choice of binary rooted planar tree. For example, |B(5)| = 5! 5.

Here, , i.e. a tree with X-labelled leaves is either just a root, or given by chopping X into two subsets and putting a labelled tree structure on the leftover stuff. Using this, we see that gives

but since |B(0)| should be 0, not 1, we see that we want to take the root given by taking to be -. So write . For ,

and so

…

where we are using !! to denote the double factorial. More interesting is the fact that

= {number of trees with n leaves} = .

Next time, we’ll return to the Catalan numbers.