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.
Best Answer
Your sum $\sum_{i=1}^{r}k^i = k^1 + k^2 + ...+ k^r$ should run from $0$ to $r-1$. This is a geometric series which can be summed in the usual way to $(k^r-1)/(k-1)$
I tried counting the average distance from a node on each level but it became a mess. A slicker way is to count how many times each edge gets used when you count all the paths. It will get used if one of the vertices is above it and the other is not. For example, an edge attached to the root has a tree of height r-1 above it, so will get used $(k^{(r-1)}-1)/(k-1) * ((k^r-1)-(k^{(r-1)}-1)/(k-1)$ times. An edge at the top of the tree will get used if and only if its leaf is one of the vertices so will get counted $(k^r-1)/(k-1)-1$ times. An edge at level $i$ will get used $(k^{(r-i-1)}-1)/(k-1) * ((k^r-1)-(k^{(r-i-1)}-1)/(k-1)$ times and there are $k^{(i+1)}$ of them where i goes from 0 to r-2. Then divide by the number of pairs of vertices. So you want $\sum_{i=0}^{r-2} k^{(i+1)}*(k^{(r-i-1)}-1)/(k-1) * ((k^r-1)-(k^{(r-i-1)}-1)/(k-1)$ divided by $((k^r-1)/(k-1)-1)*(k^r-1)/(k-1)/2$
It's a mess, but I'm sure Mathematica can do it.