Number of binary trees with $N$ nodes

Question

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.

Answer 1

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)$$