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

  • $\begingroup$ 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? $\endgroup$ Feb 26, 2015 at 18:17
  • 1
    $\begingroup$ 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 $\endgroup$
    – Barkas
    Feb 26, 2015 at 18:21
  • 1
    $\begingroup$ Are you counting trees "up to isomorphism" or counting as if the nodes were labelled? $\endgroup$
    – hardmath
    Feb 26, 2015 at 18:28
  • 1
    $\begingroup$ Labelled nodes, which is why I also demand the root to be part of any such tree. $\endgroup$
    – Barkas
    Feb 26, 2015 at 18:30
  • $\begingroup$ 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. $\endgroup$ Feb 26, 2015 at 18:34

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


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

  • $\begingroup$ Okay, Thank you very much!! It seems kind of hard though to get asymptotics for that expression or am I missing something? $\endgroup$
    – Barkas
    Mar 3, 2015 at 1:17
  • $\begingroup$ It reminds me of counting contingency tables, about which there are asymptotics for roughly equal row sums, but which indeed grow very rapidly. I'll have to give it a bit of thought as to whether I think there's a real analogy to pursue. $\endgroup$
    – hardmath
    Mar 3, 2015 at 1:40
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Mar 5, 2015 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .