Let $X$ be a regular graph of degree $d$ and let $v_{0}$ be a vertex such that the subgraph induced by the vertices $\{ v' \in X : dis(v_{0}, v') \leq r/2 \}$ is acyclic. Furthermore let $\theta(r)$ be the number of closed walks starting at $v_{0}$ of length $r$ in $X$
I was reading an old paper (Lemma 2.1) where the following is proved:
$$\theta(r) = \begin{cases} 0 &\text{$r$ is odd} \\ \sum^{s}_{k=1} {{2s-k}\choose{s}} \frac{k}{2s-k} d^{k}(d-1)^{s-k} &{r=2s} \end{cases}$$
When $r$ is even, we write $r=2s$
Unfortunately, many of the counting details are omitted in the proof I'm reading and I was wondering if someone could either provide a detailed proof or a helpful reference or even an example or strategy to gain more insight into this.
The graph is connected, regular, undirected and acyclic.
These conditions imply that the grap is a tree.
You can characterize a tree by its property that for every two nodes, there's exactly one path connecting them.
It further follows that there are no shortcuts, and every edge to take either brings you closer or farther away from the root.
From this follows that there are no closed walks for odd distances.
Now let $r=2s$.
Given that every edge you take either increases or decreases the distance to $v_0$ by exactly 1, every closed path from $v_0$ has to take exactly $s$ steps increasing the distance, and $s$ steps decreasing the distance.
Furthermore, with the exception of when you are at $v_0$, there's always exactly one edge that decreases the distance to $v_0$, and all other $d-1$ increase it.
And this now gives you the recipe:
Partition the set of all closed walks into how many times they arrive back at $v_0$.
Let's say we pick one partition $M$ in the set that arrives $k$ times back at $v_0$. Let $P_i$ be the set of paths of length $i$.
Then every path in $M$ can be cut into $k$ segments by cutting whenever we arrive back at $v_0$. By cutting this way, we obtain a strong even partition $x_1,...,x_k$ of $2s$ in $k$ parts, which gives us the length of the cut walks.
Inversely, for every strong partition $x_1,...,x_k$ of $s$ in $k$ parts we can count how many closed walks of length $2x_1$, then length $2x_2$,..., then length $2x_k$ there are, so that each of these sub-paths returns only to $v_0$ at the last node.
The number of closed walks of length $2x_i$ that return only to $v_0$ at the last node is: $$ \frac{1}{x_i+1}\binom{2x_i}{x_i}d\cdot (d-1)^{x_i-1} $$
This product comes as follows:
Every Dyck-path from 0 to 2s tells us for each step, whether we increase or decrease the distance to $v_0$. Whenever we increase the distance, we have $d-1$ options (besides at the starting point where we have $d$ options), and whenever we decrease the distance, we have $1$ option.
The number of closed walks of length $2x_1$, then length $2x_2$,..., then length $2x_k$ , where $x_1,...,x_k$ is a strong partition of $s$ is then: $$ \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i}d\cdot (d-1)^{x_i-1} $$
For the set $M$ of the partition, we therefore have $$ |M| = \sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i}d\cdot (d-1)^{x_i-1} $$
And finally, for the set $S$ of all partitions, or equivalently, the set of all closed walks from $v_0$ of length $2s$, we have: $$ |S|= \sum_{k=1}^s \sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i}d\cdot (d-1)^{x_i-1} $$
Now all that's left to do is simplify: $$ \sum_{k=1}^s \sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} \frac{1} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i} d\cdot (d-1)^{x_i-1} \\= \sum_{k=1}^s \sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} d^k\cdot (d-1)^{s-k} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i} \\= \sum_{k=1}^s d^k\cdot (d-1)^{s-k} \sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i} $$ Here, $\sum_{x_1+...+x_k=s\\x_1,...,x_k\ge 1} \prod_{i=1}^k \frac{1}{x_i+1}\binom{2x_i}{x_i} $ counts the number of Dyck-paths of length $2s$ that hit 0 exactly $k+1$ times ($k$ internal touches).
Therefore this is equal to: $$ \sum_{k=1}^s d^k\cdot (d-1)^{s-k}\frac{k}{2s-k}\binom{2s-k}{s} $$