Solving non linear differential equations using combinatorics!

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.

 

 

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