# Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states:

[...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of size $u$ [...]

Unfortunately this is not "well-known" to me, not being an expert in combinatorics. I understand this in the following sense: Starting from the root how many different subtrees can one construct containing $u$ sites. Or am I already wrong here? Is it possible to obtain the result based on a recursion relation? I am happy to work with a hint instead of an direct answer/proof...

• In the meantime I was able to show it for an infinite $D-ary$ tree, i.e. every node has $D$ children, by using the generating function method. But in a $D-regular$ tree all nodes, except the root, have $D-1$ children... – antarcticfox May 21 '14 at 7:00
• I don't understand the definition of $D$-regular tree. It sounded trivial to me that if the tree is $D$-regular, then the root must have $D$ children. And, any other node must have $D - 1$ children to be of degree $D$, as it must have exactly one parent. Why do we need generating functions ? I also don't understand the rooted subtrees of size $u$. Maybe you can tell me what's wrong with this : Say you pick any non-root node $x$. Take the subtree rooted at $x$, and pick $u$ nodes in this subtree. You got a subtree of size $u$. So there's an infinity of them. – Manuel Lafond May 21 '14 at 17:08
• Starting from the root how many ways are there to choose a sub-tree with u vertices (including the root). The statement that the tree is infinite is only there to assure that we can do so for any $u$ we like. If we fix the root there is obviously only a finite number of possibilities for finite $u$. – antarcticfox May 21 '14 at 17:21
• Ah, so the root of the subtrees we count must be the same root as the tree... – Manuel Lafond May 21 '14 at 17:25

As the calculation of this number/formula has not been posted I will try to outline it here.

Start with the combinatorial class equation $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z}\times \sum_{q=0}^{D-1} {D-1\choose q}\textsc{SEQ}_{=q}(\mathcal{T}).$$

We can visualize this equation as there being $$D-1$$ slots at the lower side of every node, all subsets of size $$q$$ of which, including zero, can be chosen to grow the tree. Different sets of slots give different trees. This reflects the fact that every edge taken gives rise to a different subtree. E.g. when $$D=5$$ and we take child nodes $$0$$ and $$2$$ then this is not the same as taking child nodes $$3$$ and $$4$$ even though we get two children. This reflects the possibilities of embedding subtrees into the infinite master tree.

The species equation yields the functional equation (here we take $$D\ge 2$$) $$T(z) = z \times \sum_{q=0}^{D-1} {D-1\choose q} T(z)^q = z \times (T(z)+1)^{D-1}.$$

We are interested in the quantity (what follows is a form of Lagrange inversion) $$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz.$$

To compute this put $$w=T(z)$$ so that $$z = \frac{w}{(1+w)^{D-1}}$$ and $$dz = \left(\frac{1}{(1+w)^{D-1}} - \frac{(D-1)w}{(1+w)^D}\right) dw.$$

Substituting $$w$$ into the integral we obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{(D-1)\times (n+1)}}{w^{n+1}} \times w \times \left(\frac{1}{(1+w)^{D-1}} - \frac{(D-1)w}{(1+w)^D}\right) dw.$$

We treat the two parenthesised terms in turn.

For the first one we obtain $$\frac{(1+w)^{(D-1)\times n}}{w^n}$$ so that the residue is $${(D-1)\times n\choose n-1}.$$

For the second one we find $$- (D-1) \frac{(1+w)^{(D-1)\times (n+1)-D}}{w^{n-1}}$$ so that the residue is $$-(D-1){(D-1)\times (n+1)-D \choose n-2} = -(D-1){(D-1)\times n -1 \choose n-2} \\ = -(D-1) \frac{n-1}{(D-1)\times n} {(D-1)\times n \choose n-1}.$$

Joining the two contributions we finally obtain $$\left(1-\frac{n-1}{n}\right) {(D-1)\times n \choose n-1} = \frac{1}{n} {(D-1)\times n \choose n-1}.$$ This is $$\frac{1}{n} \frac{((D-1)\times n)!}{(n-1)! ((D-2)\times n +1)!} = \frac{((D-1)\times n)!}{n! ((D-2)\times n +1)!} \\ = \frac{1}{(D-2)\times n + 1} \frac{((D-1)\times n)!}{n! ((D-2)\times n)!} \\= \frac{1}{(D-2)\times n + 1} {(D-1)\times n\choose n},$$ which was to be shown.

There is an apparent discrepancy here ($$D-1$$ instead of $$D$$) but I would argue that I have the right formula because the value for $$n=2$$ is $$\frac{1}{2D-3} {2D-2\choose 2} = \frac{1}{2D-3} \frac{1}{2} (2D-2) (2D-3) = D-1$$ which corresponds to one node at the top and the possible placement of the second (child) node at one of $$D-1$$ slots for the children.

The OEIS has entries for these e.g. at OEIS A002293 and OEIS A002294.

Remark, Feb 23, 2020. We can streamline this proof by introducing a second combinatorial class $$\mathcal{U},$$ which represents the root with outdegree $$D.$$ We use this to compute the number of $$D$$-regular trees as opposed to $$D$$-ary trees. The former is rooted like the latter but it has total degree (indegree plus outdegree) $$D$$ including at the root. With $$D$$-ary trees every node has $$D$$ children, which may include leaves of weight zero, so that the root has total degree $$D$$ and its children have total degree $$D+1$$. The first answer from 2014 counts $$(D-1)$$-ary trees. This explains why we have a $$D-1$$ instead of a $$D$$ in the closed form and it implies that the OP was asking to count $$D$$-ary trees.

We thus have the two combinatorial classes

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{U} = \mathcal{Z} \times \sum_{q=0}^{D} {D\choose q} \textsc{SEQ}_{=q}(\mathcal{T})$$

where

$$\mathcal{T} = \mathcal{Z} \times \sum_{q=0}^{D-1} {D-1\choose q} \textsc{SEQ}_{=q}(\mathcal{T}).$$

They were written this way because the OP asks for embeddings in an infinite tree. The binomial represents the choice of children that are not leaves. A more compact form of these is

$$\mathcal{U} = \mathcal{Z} \times (\mathcal{E} + \mathcal{T})^D$$

and

$$\mathcal{T} = \mathcal{Z} \times (\mathcal{E} + \mathcal{T})^{D-1}.$$

This gives the functional equations

$$U(z) = z \times (1+T(z))^{D}$$

and as before

$$T(z) = z \times (1+T(z))^{D-1}$$

so that

$$U(z) = T(z) (1+T(z)) = T(z) + T(z)^2.$$

We are interested in

$$[z^n] U(z) = \frac{1}{n} [z^{n-1}] U'(z) = \frac{1}{n} [z^{n-1}] T'(z) (2T(z) + 1).$$

The RHS is by the Cauchy Coefficient Formula (we have $$n\ge 1$$ in what follows)

$$\frac{1}{n\times 2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} (2T(z)+1) \; T'(z)\; dz.$$

We also have

$$z = \frac{T(z)}{(1+T(z))^{D-1}}.$$

Putting $$T(z) = w$$ we find

$$\frac{1}{n\times 2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{(D-1)n}}{w^{n}} (2w+1) \; dw.$$

We get two pieces, the first being

$$\frac{2}{n\times 2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{(D-1)n}}{w^{n-1}} \; dw = \frac{2}{n} {(D-1)n\choose n-2}.$$

and the second

$$\frac{1}{n\times 2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{(D-1)n}}{w^{n}} \; dw = \frac{1}{n} {(D-1)n\choose n-1}.$$

This is

$$\frac{1}{n} {(D-1)n+1\choose n-1} + \frac{1}{n} {(D-1)n\choose n-2} \\ = \frac{1}{n} {(D-1)n+1\choose n-1} + \frac{1}{n} \frac{n-1}{(D-1)n+1} {(D-1)n+1\choose n-1} \\ = \frac{1}{n} \frac{n-1+(D-1)n+1}{(D-1)n+1} {(D-1)n+1\choose n-1}.$$

We thus have

$$\bbox[5px,border:2px solid #00A000]{ \frac{D}{(D-1)n+1} {(D-1)n+1\choose n-1}.}$$

As a sanity check when $$D=3$$ we get the generating function $$U(z) = z (1+T(z))^3$$, with $$T(z) = z (1+T(z))^2 = z + 2z T(z) + z T(z)^2$$ being Catalan numbers without the empty tree:

$$U(z) = z \times \left(1+\frac{1-2z-\sqrt{1-4z}}{2z}\right)^3 \\ = z \times \left(\frac{1-\sqrt{1-4z}}{2z}\right)^3.$$

This expands to

$$z+3\,{z}^{2}+9\,{z}^{3}+28\,{z}^{4}+90\,{z}^{5}+297\,{z}^{6} +1001\,{z}^{7}+3432\,{z}^{8}+11934\,{z}^{9}+\cdots$$

and indeed the term $$\frac{3}{2n+1} {2n+1\choose n-1}$$ yields

$$1, 3, 9, 28, 90, 297, 1001, 3432, 11934, \ldots$$

• Thank you very much. You say that for the $n=2$ your results reproduces is the intuitive result? In a $D-regular$ tree any node (including) the root has degree $D$ and hence your argumentation would lead to the conclusion that the number of ways for $n=2$ is $D$ because there are $D$ childs at the root. This suggests that the original formula is right. Another question I have is about the notation? Can you say a bit more about the species equation and how to get to the functional equation? I guess $T(z)$ is a generating function. – antarcticfox Jul 5 '14 at 7:48
• There is no problem replacing $D-1$ by $D$ if you believe this is the correct problem definition, which I might have misunderstood. (I do prefer leaving my post as is.) The calculation goes through the same way. As for the method I suggest you start reading at Wikipedia Symbolic Combinatorics and Wikipedia Lagrange Inversion. – Marko Riedel Jul 6 '14 at 10:36
• @ Marko Riedel: I think you have a different definition of the $D$ regular tree in mind than antarcticfox. In your solution you work with a $D-1$-ary tree, that is a tree where every vertex has $D-1$ children. However, a $D$-regular tree is a tree, where the root has $D$ children and every other vertex has $D-1$ children (so every vertex has degree $D$) But I think it's questionable if the author of the cited paper really meant $D$-regular or rather $D$-ary, which would be the statement you proved above. – Barkas Aug 27 '15 at 16:00