Number of rooted subtrees with m edges of a p-regular tree

Question

I have the following question: Assume I have an infinite $p$-regular tree, that is a tree where every node has degree $p$ (so also the root should have degree $p$). Then how many subtrees containing the root are there with exactly $m$ edges? This is equivalent to asking how many subtrees on $m$ edges containing the root are there in a $p$-regular tree up to generation $m$, which means the leaves (i.e. nodes with distance $m$ from the root) do not have degree $p$ but have degree 1

This has bugged me for quite a time, since I was not able to figure out the correct recursion yet. Do the cases $m<p$ and $m>p$ make a difference? What I tried so far was counting trees, which seemed very tedious and interpreting size $m$ trees as paths of length $2m$ in the directed graph, however the coincidence matrix grows really fast as the number of vertices gets huge quite fast.

Any help would be much appreciated!

Edit: I am counting trees on labelled nodes

Answer 1

Edit: My original post assumed $p$-arity rather than $p$-regularity. If the $p$ child trees of the root, rather than being (infinite) trees similar to the $p$-regular parent, are of $(p-1)$-arity, then the recursion given needs to be adapted accordingly.

Note however this previous Question and Answer, which appears to give a closed form solution.

---

The recursion required here is a bit messy but seems to be fairly straightforward.

Let $T_p(m)$ denote the number of rooted (labelled) subtrees of the rooted infinite $p$-arity tree which have $m$ edges and share the same root $v_0$.

Note that the Question asks about an infinite $p$-regular tree, which has arity $p$ for root $v_0$ but all other nodes, having degree $p$, have arity $p-1$. We let $\widetilde{T}_p(m)$ denote this slightly different count and express it in terms of $T_p(m)$.

Essential idea of recursion: Since the root $v_0$ must appear in each subtree, we can choose the number $k$ of the $p$ edges from $v_0$ that will appear in the subtree, and then count possible subtrees extending from those edges.

This gives a recursion on $m$ involving the set $\mathscr{W}(m-k,k)$ of weak compositions of $m-k$ with $k$ summands.

For the basis case, define $T_p(0) = 1$. Then for $m \gt 0$:

$$ T_p(m) = \sum_{k = 1}^{\min(m,p)} \binom{p}{k} \sum_{\vec{w}\in \mathscr{W}(m-k,k)} T_p(w_1)\cdot T_p(w_2) \cdot \ldots \cdot T_p(w_k) $$

Here the inner summation is indexed by weak compositions $\vec{w} = (w_1,w_2,\ldots,w_k)$ of $m-k$ with $k$ summands:

$$ w_1 + w_2 + \ldots + w_k = m-k $$

where the summands are nonnegative integers.

Finally we express the desired $\widetilde{T}_p(m)$ in terms of $T_{p-1}(m)$:

$$ \widetilde{T}_p(m) = \sum_{k = 1}^{\min(m,p)} \binom{p}{k} \sum_{\vec{w}\in \mathscr{W}(m-k,k)} T_{p-1}(w_1)\cdot T_{p-1}(w_2) \cdot \ldots \cdot T_{p-1}(w_k) $$

Added:

Do the cases $m\lt p$ and $m\gt p$ make a difference?

They do in the immediate sense that when $m\gt p$ we are restricted at the root vertex $v_0$ from using up all the edges there (there simply aren't enough to exhaust the $m$ edges of our sought-after subtrees). This shows up in the recursion as the upper limit of the outer summation being given by $\min(m,p)$ rather than depending only on $m$.