# Finding an equation to fit data points

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


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.

• Thanks for the explanation as well was the answer. Now I see it I can't believe I didn't spot it. Commented Oct 11, 2012 at 20:43

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