Prove that number of non-isomorphic ordered tree with 'n' vertices is nth catalan number.

Question

according to wikipedia $C$_n is the number of non-isomorphic ordered trees with n vertices. But I can't seem to be able to prove this result. How do we do that?

where $n$th catalan number is:
$$ C_n = \frac 1{n+1} \binom{2n}{n} $$

Answer 1

We have from basic principles for the species of ordered trees the species equation

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z} \mathfrak{S}_{\ge 1}(\mathcal{T}).$$

This yields the functional equation for the generating function $T(z)$

$$T(z) = z + z \frac{T(z)}{1-T(z)}$$

which is

$$T(z) (1-T(z)) = z (1-T(z)) + z T(z) = z.$$

We claim that

$$[z^n] T(z) = \left.\frac{1}{m+1} {2m\choose m}\right|_{m=n-1} = \frac{1}{n} {2n-2\choose n-1}.$$

The shift in index of the Catalan numbers represents the species $\mathcal{T}$ which has one ordered tree on two nodes and not two (root node with one child node).

We then have

$$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$

Put $w = T(z)$ so that $w (1-w) = z$ and $dz = (1-2w) \; dw$ to get

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1} (1-w)^{n+1}} w (1-2w) \; dw.$$

This yields

$$[w^{n-1}] \frac{1}{(1-w)^{n+1}} - 2 [w^{n-2}] \frac{1}{(1-w)^{n+1}} \\ = {n-1+n\choose n} - 2 {n-2+n\choose n} \\ = {2n-1\choose n} - 2 {2n-2\choose n} = \left(\frac{2n-1}{n}-2\frac{n-1}{n}\right) {2n-2\choose n-1} \\ = \frac{1}{n} {2n-2\choose n-1}.$$

Remark. If an alternate approach is desired we can use formal power series on

$$T(z) = \frac{1-\sqrt{1-4z}}{2}$$

where we have solved the functional equation taking the branch that has $T_0 = 0$ as in the given problem. Coefficient extraction then yields

$$-\frac{1}{2} (-1)^n 4^n {1/2\choose n} = - 2^{2n-1} \frac{(-1)^n}{n!} \prod_{q=0}^{n-1} (1/2-q) \\ = - 2^{n-1} \frac{(-1)^n}{n!} \prod_{q=0}^{n-1} (1-2q) = - 2^{n-1} \frac{(-1)^n}{n!} \prod_{q=1}^{n-1} (1-2q) \\ = 2^{n-1} \frac{1}{n!} \prod_{q=1}^{n-1} (2q-1) \\ = 2^{n-1} \frac{1}{n!} \frac{(2n-2)!}{(n-1)! 2^{n-1}} = \frac{1}{n} {2n-2\choose n-1}.$$

Returning to the complex variables approach and taking the branch of the logarithm with the branch cut on the negative real axis we obtain that $T(z)$ is analytic in a neighborhood of the origin (branch point $z=1/4$ and branch cut $[1/4,\infty)$) with series expansion $z+z^2+\cdots$ so that the image of $|z|=\epsilon$ is a closed near-circle (modulus of the first term dominates) that may be deformed to a circle $|w|=\gamma.$