$\begingroup$

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.

$\endgroup$ 2

3 Answers

$\begingroup$

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.

$\endgroup$ 2 $\begingroup$

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

$\endgroup$ 1 $\begingroup$

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.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy