Unlabelled trees and Catalan numbers

Question

Show that the number of unlabelled trees with $n$ vertices is at the most $(n-1)^{\text{th}}$ Catalan number.

I tried to find a surjection but it does not seem to be the right way.

Answer 1

We have that $C_{n-1}$ is the number of ordered trees with $n$ vertices.

Each ordered tree clearly induces an unordered tree, and every unordered tree is reachable as an ordered tree (in fact always in more than $1$ way when the graph has more than $2$ vertices).

Proof that the number of ordered trees is $C_{n-1}$:

Let $O_n$ be the quantity.

We can show it holds for the first values by hand.

We now find a recursion for the number of ordered trees.

The number of ordered trees in which the number of vertices that belong to the subtree of the leftmost son of the root is $k$ is $O_kO_{n-k}$.

This is because the ordered subtree that belongs to the leftmost son can be formed in $O_k$ ways and the ordered tree obtained by deleting the leftmost son and all of its decendents can be formed in $O_{n-k}$ ways.

Therefore we have $O_{n+1} = \sum\limits_{k=1}^{n} O_kO_{n-k}=\sum\limits_{k=0}^{n-1}O_kO_{n-k}$ which is the usual catalan recurrence for $C_{n}$.