# A generating function for walks on a rooted infinite regular tree

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.

• 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? Jun 6, 2011 at 20:21
• 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$. Jun 6, 2011 at 20:34
• 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. Jun 6, 2011 at 23:33
• Some formulas are given in Lemma 2.1 of "The expected eigenvalue distribution of a large regular graph" by Brendan McKay. Dec 14, 2021 at 0:49

Here is an explicit formula for $$w(l)$$: $$w(2l+1)=0 \ \ \ \ \ \ \text{and} \ \ \ \ \ \ w(2l)=\sum_{j=1}^{l}C_{j,l}d^{j}(d-1)^{l-j},$$ where $$C_{j,l}=\frac{j}{2l-j}\binom{2l-j}{l}$$ is the "generalized $$l$$-th Catalan number", which counts the number of sequences $$(0=d_{0},d_{1},\dots,d_{2l}=0)$$, where each $$d_{i}$$ is a non-zero integer and $$|d_{i+1}-d_{i}|=1$$ for each $$i=0,\dots,2l-1$$ and where exactly $$j$$ terms in $$d_{0},d_{1},\dots,d_{2l-1}$$ are $$0$$.

• $$w(2l+1)=0$$. It is well known that a closed walk of odd length contains an odd cycle, which does not exist in a tree as every tree is a bipartite graph. Now for the even case

• $$w(2l)=\sum_{j=1}^{l}C_{j,l}d^{j}(d-1)^{l-j}$$. Associate each closed walk $$(v_{0},v_{1},\dots,v_{2l})=v_{0}$$ of length $$2l$$ with the sequence $$(d_{0},d_{1},\dots,d_{2l})$$, where each $$d_{i}$$ is the distance of the vertex $$v_{i}$$ from the root $$v_{0}$$. It is easy to see that each such sequence satisfies the above conditions for some $$j=1,\dots, l$$. Conversely, it is easy to see that each such sequence defines (not uniquely) a closed walk from $$v_{0}$$ to $$v_{0}$$ of length $$2l$$. Now, we compute how many such closed walks are associated with each such sequence. Each such walk makes $$s$$ steps towards $$v_{0}$$ and $$s$$ steps away from $$v_{0}$$. Thus, there are $$s$$ indices such that $$d_{i+1}-d_{i}=1$$ and $$s$$ indices such that $$d_{i+1}-d_{i}=-1$$. For each step towards $$v_{0}$$, the next vertex is uniquely determined and for each step away from $$v_{0}$$ we have $$d$$ choices, if $$d_{i}=0$$, and $$d-1$$ choices for the remaining $$s-j$$ terms. Therefore, for each such sequence there are $$d^{j}(d-1)^{s-j}$$ corresponding walks as desired.

This proof is from Expander Graphs and their Applications.