In this post, we will consider the (nasty?) non linear differential equation:
and show that the power series:
is a solution using combinatorics! In particular, note that is the exponential generating function for the number of labelled trees on vertices by Cayley’s formula. Let us call this number , which is equal to 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:
We will show this recurrence directly using combinatorics:
We will count the number of labelled trees on vertices with a distinguished edge with a distinguished direction. This number is clearly since there are edges to choose from and directions.
But if we imagine deleting the edge, this is the same as taking two labelled trees of sizes with a distinguished vertex on each and a choice of elements from . The choice of elements is because once we have two trees with labels from and we need to map the union of these two sets into and once we pick a element subset of , we can map the first set into it, preserving order and similarly for the complement.
Then, on a tree of size , there are distinct vertices to choose from.
This correspondence is clearly bijective and so the number we are counting is also equal to:
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.