# Thread: Permutation of Tree Construction

1. ## Permutation of Tree Construction

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?

2. Originally Posted by twfx
Question:
...
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?
Hello,

you have
For N=2, p = 1
For N=3, p = 3
For N=4, p= 16
For N=5, p=125

According to your result you probably get:

$p = N^{N-2}$

I'm only guessing. I didn't find a proof for this formula.