Wondering how to calculate the number of items that can fit into a tree.
For example, say at each level of a tree you can have 10 children (aka 10 different "types"). Say you're only considering trees that are 10 levels deep. The question is, the generic way of solving this so I can do it for any tree with n number of children at each level, and m levels deep.
For example, a real data tree might look like this:
top
0 1 2 3 4 5 6 7 8
1 3 4 5 6 2 3 3 4 5 6 5 8
Where the numbers are from 0-9 to account for the 10 children per level. I would like to know how many nodes can possibly fit into the tree, what the equation is for this. Basically, the maximum number of nodes in a specific model of a tree, specifying the number of children per node, and the number of levels in the tree.
The number of nodes at level $m$ is certainly $n^m$ (assuming root is considered level 0). Therefore, the maximum number of nodes for a $m$-deep tree is $$ f(m,n) = \sum_{k=0}^m n^k = \frac{n^{m+1}-1}{n-1} $$ using a geometric series.
Example Testing this out on a binary tree (at most 2 children per node), you get $f(m,2) = 2^{m+1}-1$, as expected.