Prove that number of non-isomorphic ordered tree with 'n' vertices is nth catalan number. 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}
$$
 A: 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.$
