4
$\begingroup$

Consider $T_d$ the $d$-regular infinite tree rooted at some vertex $v_0$. I'd like to count all the closed walks on the tree which start at the root and order them by their length. So I'm looking for the coefficient $w(l)$ which denotes the number of walks of length $l$ which start and finish at the root vertex.

I'm expecting to see the Catalan numbers pop in there, but I'm not entirely sure how to do this since I'm not only interested in a binary tree, but any regular tree. Is there an obvious recurrence relation that I'm missing? Any ideas or references?

1 Answers 1

2

Let $w_n$ be the number of random walks of length $n$ in a $d$-ary tree that start and end at the root, and let $s_n$ be the number of such walks that do not visit the root at any point during the middle. Then $w_n$ and $s_n$ satisfy the relations $ w_n \;=\; \sum_{i_1+\cdots+i_k = n}s_{i_1}\cdots s_{i_k}\qquad\text{and}\qquad s_n = w_{n-2}d. $ The first is from the fact that any walk of type $w$ is a concatenation of finitely many walks of type $s$. The second is from the fact that a walk of type $s$ of length $n$ can be viewed as a walk of length $n-2$ of type $w$ based at one of the $d$ child vertices of the root.

It is easy to check that $ w_{2n} \;=\; C_n d^n \qquad\text{and}\qquad s_{2n} \;=\; C_{n-1}d^n $ are solutions to these recurrence relations, where $C_n$ is the $n$th Catalan number.
In particular: $ w_2 \;=\; d,\quad w_4 = 2d^2,\quad w_6 = 5d^3,\quad w_8 = 14d^8,\quad \ldots $

Edit: The above formulas work for the infinite rooted $d$-ary tree, but it seems that you were asking about a rooted tree in which the root has $d$ children, and every other node has $d-1$ children.

In this case, the formulas above work for random walks in each of the $d$ basic subtrees, with $d-1$ in place of $d$. For random walks based at the root, it follows that $ s_{2n} \;=\; C_{n-1}(d-1)^{n-1}d $ and $ w_{2n} \;=\; \sum_{i_1 + \cdots + i_k = 2n} s_{i_1}\cdots s_{i_k} $ I'm not sure there's a simpler formula for $w_{2n}$ than this.

  • 0
    I'm sorry, I interpreted "$d$-regular infinite rooted tree" in your question as referring to an infinite rooted tree in which every node has $d$ children, but apparently you mean that every vertex has *total* degree exactly $d$. I will revise my answer.2011-06-06