2
$\begingroup$

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

$\endgroup$
  • $\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$ – Christiaan Hattingh Feb 26 '15 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 '15 at 18:21
  • 1
    $\begingroup$ Are you counting trees "up to isomorphism" or counting as if the nodes were labelled? $\endgroup$ – hardmath Feb 26 '15 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 '15 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$ – Christiaan Hattingh Feb 26 '15 at 18:34
1
$\begingroup$

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

$\endgroup$
  • $\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 '15 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 '15 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 '15 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.