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.
 A: 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.
A: 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)$$
A: If you are looking Binary search trees with $n$ nodes, I think $\dfrac{2n!}{(n+1)!*n!}$ is the answer (Catalan numbers). Considering you are looking for only Binary tree (not binary search tree) then answer will be $\dfrac{2n!}{(n+1)!}$
But if you are looking for trees (not specifically binary) with $n$ nodes then the answer is $\dfrac{n^n}{n^2}$ by Cayley's formula.
