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

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

• I assume with a tree you mean a connected graph with no cycles? Every tree has at least two end-vertices, which are vertices of degree 1...so the only p-regular tree must be 1-regular, that is, $K_2$? Am I missing something? – Christiaan Hattingh Feb 26 '15 at 18:17
• Oh yes sorry, I had the infinite $p$-regular tree in mind. In case you want to picture a finite tree, then it would be the p-regular tree up to generation $m$ where the leaves have of course degree 1. Thanks for the clarification, I'll modify my question – Barkas Feb 26 '15 at 18:21
• Are you counting trees "up to isomorphism" or counting as if the nodes were labelled? – hardmath Feb 26 '15 at 18:28
• Labelled nodes, which is why I also demand the root to be part of any such tree. – Barkas Feb 26 '15 at 18:30
• Can't you just use Cayley's formula together with m=n-1? I guess you have to bring the regularity into this as well...so not so straightforward, but there may be merit in trying this. – Christiaan Hattingh Feb 26 '15 at 18:34

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)$$

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$.
• Michael, in comparing this Question, I realized that I'd confused the $p$-regularity condition with $p$-arity of the infinite tree. The difference is that $p$-regular requires all nodes below the root to have $p-1$ children, not $p$ children as I assumed in outlining my recursion. The recursion is easily adapted to this, but I wanted to bring it to your attention. – hardmath Mar 5 '15 at 14:28