Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be reached in exactly $k$ steps? A step from a node is a jump to any adjacent vertex.
Thanks for any help.
Without backtracking
Every node except the root has degree $C+1$. If $k\leq h$, there are $$(C+1)C^{k-1}$$ reachable nodes. If $k>h$, then we have to worry about paths traversing the root. One formula is $$C^k + \sum_{j=1}^h (C-1) C^{k-j-1}.$$ The $C^k$ counts paths going down (away from the root.) Each term $(C-1) C^{k-j-1}$ counts paths going $j$ steps upward, then choosing from the other $(C-1)$ children of the $j$th ancestor, then taking the remaining $k-j-1$ steps down. This can be simplified as $$C^k +C^{k-1}-C^{k-h-1}.$$
With backtracking
If backtracking is allowed, then in $k$ steps we can reach any vertex at the end of a path of length $k$, or a path of length $k-2$, or by any path whose length is less than $k$ and the same parity as $k$.
So, if $k \leq h$ and $k = 2n+1$ is odd, we have $$\sum_{j=0}^n (C+1)C^{2j}$$ vertices. This can be rewritten as $$ (C+1)\frac{C^{2n+2}-1}{C^2-1} = \frac{C^{k+1}-1}{C-1}. $$
If $k = 2n$ is even (and still $k \leq h$), we have $$1 + \sum_{j=1}^n (C+1)C^{2j-1}$$ reachable vertices. This again simplifies to $$\frac{C^{k+1}-1}{C-1}.$$
If $k > h$, and $k$ and $h$ have the same parity, then we have $\frac{C^{h+1} - 1}{C-1}$ nodes reachable in $k$ steps at distance $h$ or less, and $\sum\limits_{l=1}^{\frac{k-h}{2}} (C^{h+2l} + C^{h + 2l - 1} - C^{2l-1})$ reachable at distance more than $h$. When added and simplified, this is $$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - 1}{C^2 -1}.$$
On the other hand, if $k > h$ and $k$ and $h$ have different parity, then we have $$\frac{C^{h} - 1}{C-1} + \sum_{l=0}^{\frac{k-h-1}{2}} \bigl(C^{h+2l+1} + C^{h + 2l} - C^{2l}\bigr),$$ which simplifies to $$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - C}{C^2 -1}.$$
Another approach when $k > h$
We can also just take the $\frac{C^{k+1}-1}{C-1}$ vertices which would be reachable if every node had degree $C+1$, and subtract those which would be found in the missing branch at the root.
If $k$ and $h$ have the same parity, this is $$\frac{C^{k+1}-1}{C-1} - \sum_{j=0}^{\frac{k-h-2}{2}} C^{2j+1},$$ which simplifies to the same expression as before, $$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - 1}{C^2 -1}.$$
If $k$ and $h$ have different parity, we have $$\frac{C^{k+1}-1}{C-1} - \sum_{j=0}^{\frac{k-h-1}{2}} C^{2j},$$ which simplifies to the same expression as before, $$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - C}{C^2 -1}.$$