Number of binary trees with $N$ nodes

I am trying to calculate the number of trees (non isomorphic) with $n$ nodes (total including leaves).

I think that there are n! such trees, but I don't know how to prove that.

I know that the number of trees with n internal nodes is a the $(n-1)$th catalan number, so I thought maybe there is a way to deduce from that the number of trees with $n$ total nodes.

another approach will be to look at each level and count the number of possible nodes in each level.

Solution 1:

Denote by $b_n$ the number of nonisomorphic binary trees with $n\geq1$ nodes. Apart from the root node each note has exactly one incoming edge and $0$ or $2$ outgoing edges.

Drawing the first few such trees we find $b_1=1$, $b_2=0$, $b_3=1$, $b_4=0$.

A binary tree with $n>1$ nodes can be set up as follows: Draw the root node; choose a $k\in[n-2]$, and attach to the two outgoing edges a left tree $T_l$ with $k$ nodes and a right tree $T_r$ with $n-k-1$ nodes. It is easily seen that all trees so constructed will have an odd number of nodes; whence $b_{2m}=0$ for all $m\geq1$.

Now we come to the counting. A first thought would be that $b_n$ is equal to $$\sum_{k=1}^{n-2}b_k b_{n-1-k}\ ;\tag{1}$$ but this would count the two isomorphic trees in the above figure as two different trees. Halving $(1)$ almost does the job. But the special case where $T_l=T_r$ is counted only once in $(1)$; therefore we have to add ${1\over2} b_{(n-1)/2}$ again. In all we obtain the following recursion formula: $$b_n=\cases{0&($n$ even)\cr{}&\cr {1\over2}\sum_{k=1}^{n-2}b_k b_{n-1-k}+{1\over2}b_{(n-1)/2}\quad&($n$ odd)\cr}\tag{2}$$ Using a generating function trick it should be possible to obtain from $(2)$ a closed formula in terms of factorials.

The Catalan numbers appear when the left-right symmetry is not quotiented out.

Solution 2:

There is a Recursive Algorithm to calculate this:

int count(int N) {

  if (N <=1) { 
    return(1); 
  } 
  else { 

    // Iterate through all the values that could be the root... 
    int sum = 0; 
    int left, right, root;

    for (root=1; root<=N; root++) { 
      left = count(root - 1); 
      right = count(N - root);

      // number of possible trees with this root == left*right 
      sum += left*right; 
    }

    return(sum); 
  } 
} 

Link
The definition of Catalan Numbers is: $$C_0 = 1 \text{ and } C_{n+1} = \sum_{i=0}^nC_iC_{n−i} \text{ for } n\ge0$$ which is what the above function simulates.
For example:$$C_3 = C_0 · C_2 + C_1 · C_1 + + C_2 · C_0$$ And the above function calculates:
$$sum=count(0).count(2) + count(1).count(1)+ count(2).count(0)$$