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?


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.

  • 1
    $\begingroup$ Hi Jim, thanks for your answer, I'm trying to go through some of the details here. In your statement $s_n = w_{n-2}d$ what would prevent from the $w$ type walk to go visit the root? That wouldn't create an $s$ type walk right? $\endgroup$ Jun 6 '11 at 20:21
  • $\begingroup$ Also, your formulas claim that there are $C_2\,3^2 = 18$ closed walks of length 4 in the 3-regular infinite tree but it looks like there are 6 walks of type $s$ and $9$ that I can create out of combining two walks of type $s$ of length 2, that's a total of 15 walks, so there's a mismatch (your formula for $s$ walks also fails since it predicts $C_1\,3^2=9$ walks instead of 6). It seems to me these mistakes come from what I pointed above in my previous comment. I'll see if I can make it work by saying that $s_n = s_{n-2}d$. $\endgroup$ Jun 6 '11 at 20:34
  • $\begingroup$ 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. $\endgroup$
    – Jim Belk
    Jun 6 '11 at 23:33
  • $\begingroup$ Some formulas are given in Lemma 2.1 of "The expected eigenvalue distribution of a large regular graph" by Brendan McKay. $\endgroup$ Dec 14 '21 at 0:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.