What are the total number of possible ordered trees with N nodes?

Question

For example for N=3, we can find easily by listing them all, but when asked for any arbitrary N value I am facing problem.

Answer 1

If you are looking at binary trees then, as mcdowella said, Choose(2n,n)/(n+1) (Catalan number) is the answer.

If you are looking at arbitrary trees then it is probably n. n^(n-2) = n^(n-1), but I am not totally sure. Prufer's algo tells us that there are n^(n-2) labeled trees and any of the nodes can be made a root, thus we get the number n^(n-1).

Answer 2

This is covered in Knuth Vol 1 (The Art of Computer Programming: Fundamental Algorithms) section 2.3.4.4 About half a page of maths gives you Choose(2n, n) / (n + 1) and searching for the sequence in Knuth finds http://oeis.org/A000108

Answer 3

You could go about it like this using dynamic programming :
Let's fix element i as the root of the tree. Now we need to know how many different trees we can form with the first (i-1) elements and the rest (n-i-1) elements.
So we follow the same procedure for these two subarrays (i-1) and (n-i-1) to obtain the following recurrence:

Formula:

LaTeX:

Trees[n]&space;=&space;\sum_{i&space;=&space;2}^{i&space;=&space;n-1}&space;Trees[i-1]*Trees[n-i-1]

Answer 4

Binary Trees (2n,n)/(n+1) (Catalan number) as the answer If labeled trees than n^(n-2) trees .