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.

Everything you need is there. – Zubzub Jul 06 '16 at 14:19 — Zubzub, Jul 06 '16 at 14:19

score 0 · Answer 1 · answered Jul 06 '16 at 14:15

0

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.

answered Jul 06 '16 at 14:15

naslundx

9,720

Thanks for this, though I marked the other as an answer because I was able to use the final calculation immediately in my code. – Matthew McDermott Jul 06 '16 at 20:23

score 0 · Accepted Answer · answered Jul 06 '16 at 14:27

0

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} $$

answered Jul 06 '16 at 14:27

Zubzub

4,143
1
17
25

Thanks! This works perfectly. – Matthew McDermott Jul 06 '16 at 20:24

Calculating Children in a Hierarchy

2 Answers2