Calculating Children in a Hierarchy

Question

I am creating "children" in script and would like to calculate the number of children before launching the script. I have "width" the number of child nodes and "depth" the depth of the nodes.

• 5 wide and 1 deep = 5
• 5 wide and 2 deep = 30 = (5+25)
• 5 wide and 3 deep = 155 = (5+25+125)

and so on. I "see" the pattern but cannot come up with the equation based on the values of width and depth.

Answer 1

Let's define : $$N(w,d)=w+w^2+w^3+...+w^d $$ We then do the following : $$ w\cdot N(w,d) = w^2 + w^3 + ... + w^{d+1} \\ w\cdot N(w,d) - N(w,d) = w^{d+1} -w \\ (w-1)N(w,d) = w^{d+1} -w \\ N(w,d) = \frac{w^{d+1} -w}{w-1} $$ So in your case where $w = 5$ you get that at depth $n$ you have $$ \frac{5^{n+1} - 5}{4} \text{ nodes} $$

Answer 2

For width $w$ and depth $d$ the number of children $N$ is

$$N = w + w^2 + w^3 + \dots + w^d$$

I am not aware of any simple closed formula for all $(w,d)$ pairs.