Max number of nodes in non-binary tree in summation form

Question

Can some body help me to find total number of nodes in this tree network see the picture tree network, here Level-1 one has 4 nodes, and the next level has 3 and so 2, 2 is the minimum number of children a parent can have and there are maximum 3 levels allowed. What is the mathematical way of writing this in a summation form. for example the number of nodes in this example is 41 but how such a number is calculated through formula. If the nodes in the levels are not known then what would be its general formula?

Answer 1

Your problem can be simply described with the following equation:

$N=\sum_{n=1}^{N}{\frac{N!}{(N-n)!}}= \sum_{n=1}^{4}{\frac{4!}{(4-n)!}}$

With N-1 being the maximum level of 3. i.e. N=4.

Answer 2

This post explains how to calculate an estimation of the total number of nodes in the tree, not the exact number.

If n is the number of levels in a similar tree, the number of nodes in the final level is n! (n factorial). The number of nodes in all the levels working backwards is as follows:

• Level - Total Nodes
• n - n! (same as saying n!/1!)
• n-1 - n!/2! (total nodes in level n divided by 2)
• n-2 - n!/3! (total nodes in level n divided by 2, then by 3)
• n-3 - n!/4! (total nodes in level n divided by 2, then by 3, then by 4)
• ...
• root node - n!/n! (equals 1)

If you add up the formulas for total nodes at each level and substitute n!/1! for n! since they are equal, you would get the following formula:

n!/1! + n!/2! + n!/3! + n!/4! + ... + n!/n!

take out the common factor n!

n!(1/1! + 1/2! + 1/3! + 1/4! + ... + 1/n!)

the stuff in the parentheses is similar to the following formula for the constant e:

e = 1 + 1/1! + 1/2! + 1/3! + 1/4! + ...

except it's missing the initial number 1, therefore the formula to approximate the total number of nodes in the entire tree is

n!(e-1) where n is the number of levels (depth) in the tree.

If you apply this formula to the tree in the original question, there are 4 levels so 4!(e-1) is about 41.2387, and the actual number of nodes is 41.