I am trying to calculate the average distance between all vertices of a complete $k$-ary tree. A complete $k$-ary tree is a tree such that all vertices have $k$ children except for the leafs of the tree.
Suppose the tree has $r$ levels, where level 0 is the root. So the height of the tree is $r-1$. First i have to know how many vertices there are in the tree. For this i would sum up the vertices on each level of the tree which would give me
$\sum_{i=1}^{r}k^i = k^1 + k^2 + ...+ k^r$
(is there an easier way of representing this?)
Now how many ways are there to choose paths in this tree that are of length $1, 2, 3, ..., r-1, ..., 2(r-1)$
$2(r-1)$ because we can start from on leaf and go all the way up to the root and all the way down again to a vertex that is on a different branch that the initial vertex.
I am not sure how to count all these. For length 1 i can easily count those (i think): $r-1 * \sum_{i=i}^{r}k^i$
But level two is a little trickier because you can go up two parents or go up one parent and down to the child on the same level as the initial vertex.
One i figure out the total distance between all vertices i have to divide it by the total number of vertices to get the average, correct?
Any help would be appreciated.