I'm trying to solve a problem related to counting the number of trees.
Basically, I want to count trees as different only if they have different structure. So, for example, there are $5$ trees of size $4$, let them be: $A, B, C, D, E$:
(A) (B) (C) (D) (E)
* * * * *
| | |\ |\ /|\
* * * * * * * * *
| |\ | |
* * * * *
|
*
Notice that trees $C$ and $D$ are different because on $C$, the first child of the root has a child, whereas on $D$ the second child of the root does. Also, notice they are not necessarily binary trees.
Is there a formula to find the number of such trees for any given number of nodes?
Such trees are in fact called ordered trees (perhaps you were thinking of labeled trees?) and the number of such trees is given by $$\sum_{k=1}^{n-1}{\frac{1}{n} {n \choose k} {n \choose {k-1}}}.$$ For more information see this paper: http://www.cs.tau.ac.il/~nachumd/papers/Enumerations.pdf