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?
 A: 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.
A: 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.
