Solving non linear differential equations using combinatorics!

December 09, 2019

In this post, we will consider the (nasty?) non linear differential equation:

$t(h'(t))^2 - 2th'(t) + 2h(t) = 0$

and show that the power series:

$h(t) = \sum_{n\geq 0}\frac{n^{n-2}t^n}{n!}$

is a solution using combinatorics! In particular, note that $h(t)$ is the exponential generating function for the number of labelled trees on $n$ vertices by Cayley's formula. Let us call this number $T_n$, which is equal to $n^{n-2}$ by Cayley.

If we plug in the generating function into the differential equation, we find that in order to show that $h(t)$ is a solution to the differential equation, it is sufficient to show the following recurrence:

$2(n-1)T_n = \sum_{k=}^{n-1}k(n-k)T_kT_{n-k}{n \choose k}$

We will show this recurrence directly using combinatorics:

We will count the number of labelled trees on $n$ vertices with a distinguished edge with a distinguished direction. This number is clearly $2(n-1)T_n$ since there are $n-1$ edges to choose from and $2$ directions.

But if we imagine deleting the edge, this is the same as taking two labelled trees of sizes $k, n-k$ with a distinguished vertex on each and a choice of $k$ elements from $n$. The choice of $k$ elements is because once we have two trees with labels from $\{1,\dots, k\}$ and $\{1,\dots, n-k\}$ we need to map the union of these two sets into $\{1,\dots, n\}$ and once we pick a $k$ element subset of $\{1,\dots, n\}$, we can map the first set into it, preserving order and similarly for the complement.

Then, on a tree of size $k$, there are $k$ distinct vertices to choose from.

This correspondence is clearly bijective and so the number we are counting is also equal to:

$\sum_{k}k(n-k)T_kT_{n-k}{n\choose k}.$

as promised.

I do not know how to prove the recurrence directly! But there are many nice proofs of Cayley's theorem available. One I particularly like is here.