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

Solution 1:

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