3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – antarcticfox May 21 '14 at 7:00
  • $\begingroup$ 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. $\endgroup$ – Manuel Lafond May 21 '14 at 17:08
  • $\begingroup$ 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$. $\endgroup$ – antarcticfox May 21 '14 at 17:21
  • $\begingroup$ Ah, so the root of the subtrees we count must be the same root as the tree... $\endgroup$ – Manuel Lafond May 21 '14 at 17:25
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – antarcticfox Jul 5 '14 at 7:48
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Jul 6 '14 at 10:36
  • $\begingroup$ @ 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. $\endgroup$ – Barkas Aug 27 '15 at 16:00

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.