Combinatorics, Lecture 5 (10 October 2019)

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

Fibonacci and `tribonacci’ numbers

Recall: there’s a species G \colon \mathsf S \to \mathsf F with

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

For example,

We saw that

|G|(X) = \sum_{n\geq0} \frac{ |G(n)|}{n!} x^n = \sum_{n\geq0} F_n x^n

where F_n is the n-th Fibonacci number. Note that n!F_n=|G(n)|; it’s not F_n=|G(n)|. We also saw that |G|(X)= \frac{1}{1-x-x^2} which implies that |G|(X)= 1 + X|G|(X) + X^2|G|(X). This would follow from G \cong Q_0 + Q_1 G + Q_2 G if Q_k were a species with |Q_k| (X) = x^k. Before, we talked about A_k as the species of “being a k-element set”, with

but this gives that |A_k|(X)=x^k/k!. What we now want is Q_k, the species of “being a totally-ordered k-element set”, with

so that |Q_k|(X)= \sum_{n\geq0} \frac{|Q_k(n)|}{n!} n! = x^k.

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

  • see if X=\emptyset, 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 TO \cong A_0 + A_1 TO \cong Q_0 + Q_1 TO gave us |TO|(X) = \frac{1}{1-x}. Going one level further, with G \cong Q_0 + Q_1G + Q_2G gave us |G|(X)=\frac{1}{1-x-x^2} and the Fibonacci numbers.
Going yet one more level, we get the tribonacci numbers, which are those that follow

T_0 = T_1 = T_2= 1
T_{n+3} = T_n + T_{n+1} + T_{n+2}

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

Indeed, there’s a species H \cong Q_0 + Q_1H + Q_2H + Q_3H with |H|(X) = \frac{1}{1-x-x^2-x^3}, and we can show (using the same ideas) that |H|(X) = \sum_{n\geq0} T_n x^n, and that

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

Trees

Let B \colon \mathsf S \to \mathsf F 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, B\cong A_1+B\cdot B, 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 B^2-B+X=0 gives

B= \frac{-1\pm\sqrt{(-1)^2-4\cdot1\cdot x}}{2\cdot1}
= \frac{1\pm\sqrt{1-4x}}{2}

but since |B(0)| should be 0, not 1, we see that we want to take the root given by taking \pm to be -. So write |B|(X) = \sum_{n\geq0} \frac{|B(n)|}{n!} x^n. For n>0,

|B(n)|= \frac{\mathrm{d}^n}{\mathrm{d}x^n} \left(\frac{1-\sqrt{1-4x}}{2}\right) \Bigg|_{x=0}
= -\frac12\frac{\mathrm{d}^n}{\mathrm{d}x^n} \big(\sqrt{1-4x}\big) \Big|_{x=0}

and so

|B(1)| = -\frac12\cdot\frac12\cdot(-4)\cdot(1-4x)^{-\frac12} \Big|_{x=0}
= -\frac12\cdot\frac12\cdot(-4) = 1

|B(2)| = -\frac12\cdot\frac12\cdot\left(-\frac12\right)\cdot(-4)^2\cdot(1-4x)^{-\frac32} \Big|_{x=0}
= -\frac12\cdot\frac12\cdot\left(-\frac12\right)\cdot(-4)^2 = 2

|B(3)| = -\frac12\cdot\frac12\cdot\left(-\frac12\right)\cdot\left(-\frac32\right)\cdot(-4)^3 = 12

|B(n)| = \frac{(-4)^n}{2^{n+1}}\cdot(-1)^n\cdot(2n-3)
= \frac{2^{2n}}{2^{n+1}}(2n-3)!!
= 2^{n-1}(2n-3)!!

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

\frac{|B(n)|}{n!} = {number of trees with n leaves} = \frac{2^{n-1}(2n-3)!!}{n!}.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s