# complete $k$-ary tree: average distance between all vertices

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.

-
I don't feel like thinking about this right now. But here's a sanity check: when $k$ is large, most leaves will be at level $r-1$ (i. e. the level furthest from the root) and most paths will require going all the way up to the root and all the way back down. So as $k$ approaches infinity with fixed $r$, your answer should approach $2r-2$. –  Michael Lugo Oct 8 '10 at 4:31
You could use the fact that the distance between two nodes in a tree is simply the sum of their respective distances from their lowest common ancestor. Counting pairs of nodes below a given least common ancestor should be simpler than counting distances between all possible pairs of nodes. –  Rahul Oct 8 '10 at 5:49

Here's another approach to trying to find the total distance: assume that we have some 'initial' node on level $m$, and we're trying to find the distance to the nodes at equal or lower levels. Start with the equal level: there are $(k-1)$ siblings, at distance 2; then $k(k-1)$ 'first cousins' (as each of our parent's $k-1$ siblings has $k$ children, at distance 4; $k^2(k-1)$ 'second cousins', at distance , ..., up to $k^{m-1}(k-1)$ 'root cousins' (i.e., children going through the root node). Now, consider e.g. our first cousins; each of those will bring $k$ children at distance 4+1=5, $k^2$ grandchildren at distance 4+2=6, ..., $k^{n-m}$ great-great-...grandchildren, each of which contributes $4+(n-m)$ distance. A bit of careful working through the algebra should be enough to sum these correctly (distribute out that factor of 4 first!), and that'll be enough to get the total distance from a given node on level $m$ to all nodes on deeper levels; then just sum that over all depths. The one little 'gotcha' is that you want to divide the distance-sum from a node on level $m$ to all nodes on the same level by 2, otherwise you'll double-count it, but that's easily accounted for. I can try and work out the algebra later this evening, but I think it'd make a pretty good exercise.

-
thanks, i will try to work it out –  gprime Oct 9 '10 at 20:12

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.

-
yeah, that is a mess. Thanks! –  gprime Oct 9 '10 at 20:12