Question:

------------

Given N nodes, with one node is fixed as root. How many tree, p, could be built?

Condition:

------------

a) The trees can be balanced/unbalanced, as long as All nodes MUST in the tree.

b) Every node (except the root) connected to different set of child node(s) in its child tree is considered unique. However if two or more leaf node(s) connected to the same parent, position is not important.

Meaning, for N=3, with N1 is root

N1->N2->N3 and N1->N3->N2 is considered different tree.

But, the below is considered same tree.

N1 N1

| | | |

v v v v

N2 N3 N3 N2

c) To simplify, consider there exist only 1 root node, the rest of nodes are non-root.

Eg:

----

For N=3, p = 3

For N=4, p= 16

For N=5, p=125

I have manually calculated N={3,4,5}. However,

1) Is there a maths formula to solve this problem?