Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm a software developer by trade and one of the things I did today was recursively generate some dummy data for a tree. I used two parameters in my recursive algorithm: number of levels and number of items per level. From doing things like this in the past I know it's a quick and easy way to produce a lot of dummy data but today I realized that I couldn't predict how much would be produced. I'm sure there must be an equation that exactly links the input variables with the number of items in the tree.

I've tried various equations involving powers and factorials etc but none give the correct result. Plotting the data for three levels in Excel and fitting a curve gave a equation of approximately y=3x^2.5 but it's a fairly poor fit.

So my question is: how would a mathematician go about finding the equation for this data?

Please note, I tagged this homework because I didn't know what else to tag it and that seemed the best fit. Perhaps there should be a "personal challenge" tag :-)


Sample Tree - 2 Levels, 2 Items

Root

 - 0
 - - 0.0
 - - 0.1
 - 1
 - - 1.0
 - - 1.1

Total: 7 Items

Sample Data

Levels  Items   Count
1   10  11
2   1   3
2   2   7
2   3   13
2   4   21
3   1   4
3   2   15
3   3   40
3   4   85
3   5   156
3   6   259
3   7   400
3   8   585
3   9   820
3   10  1111
5   1   6
5   2   63
5   3   364
5   4   1365
5   10  111111
share|improve this question
    
Perhaps the self-learning tag may be more appropriate than the homework tag. –  Firefeather Oct 11 '12 at 21:09

2 Answers 2

up vote 3 down vote accepted

I believe you are asking how many nodes are in a C-ary tree. Except you seem to be confused about whether to count counting the top level node as a node.

Let L be the number of levels including the root node, at level i=0, and let C be the number of children per node.

  • The zeroth level has 1 node
  • The first has 1*C = C nodes
  • The second has C*C = C^2 nodes
  • ...
  • The nth has C^(n) nodes
  • ...
  • the last, which is the (L-1)st (since we started at 0), has C^(L-1)

So in total there is $\sum_{i=0}^{L-1} C^i = {1 \over {1-C}} - {{C^L} \over {1-C}} = {{1 - C^L} \over {1 - C}} = {{C^L - 1} \over {C - 1}}$ by the formula for the infinite geometric series.

>>> L=2; C=2; (C**(L+1) - 1) / (C - 1)
7
>>> L=5; C=10; (C**(L+1) - 1) / (C - 1)
111111
>>> L=5; C=3; (C**(L+1) - 1) / (C - 1)
364
>>> L=3; C=3; (C**(L+1) - 1) / (C - 1)
40

Note that I say C**(L+1) because you are counting a one-level tree, the tree with just a root node, as L=0, which is wrong.

In general, fitting an equation to some arbitrary data is a very difficult subject with many possible solutions. In this case, there's a simple theory with integer outputs and no need to do regression, but even in a more complicated case you need some sort of theory to guide you, even if your theory starts by plotting the points and guessing.

share|improve this answer
    
Thanks for the explanation as well was the answer. Now I see it I can't believe I didn't spot it. –  wobblycogs Oct 11 '12 at 20:43

It looks to me like $$ count = \frac{items^{levels+1} - 1}{items-1}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.