Number of labeled trees with n vertices such that all vertices have degree 1 or 3

Question

How many labeled trees with $n$ vertices exist such that their degree is $1$ or $3$? I succeeded to get a range but not a particular answer.

EDIT

the range I found:

$$\frac{n-2}{2^n}\lt\text{ number of trees with }n\text{ vertices }\lt n-2$$

Answer 1

We present two answers, one using Pruefer codes and one using combinatorial classes. Recall that the Pruefer code for a tree on $n$ nodes is a list of $n-2$ elements taking its values from the $n$ nodes, for a total of $n^{n-2}$ trees. The degree of a node in the resulting tree is one more than the number of times it appears in the list. Therefore with degrees one and three a node either appears not at all or it appears twice. We see immediately that there are no such trees on an odd number of nodes because $n-2$ must be even.

Now for the closed formula we must choose the $(n-2)/2$ nodes that are present in the code and distribute these pairs into the $n-2$ slots. We obtain

$${n\choose (n-2)/2} {n-2\choose 2,2,\ldots,2} = {n\choose (n-2)/2} \frac{(n-2)!}{2^{(n-2)/2}}$$

for $n$ even and zero otherwise. This yields the sequence

$$1, 0, 4, 0, 90, 0, 5040, 0, 529200, \\ 0, 89812800, 0, 22475653200,\ldots$$

For the alternate proof introduce labeled combinatorial class of rooted trees with outdegree two. These have total degree three or one at all nodes except for the root, which has degree two. The class equation is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} + \mathcal{Z}\times\textsc{SET}_{=2}(\mathcal{T}).$$

We thus obtain the functional equation

$$T(z) = z\left(1+\frac{1}{2} T(z)^2\right).$$

Now observe that an element of the target class $\mathcal{V}$ of unrooted labeled trees with node degree one or three is obtained by connecting two elements of $\mathcal{T}$ by an edge between the two roots. In this way we obtain every element of $\mathcal{V}$ exactly $n-1$ times, so we are after the following coefficient

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

To compute the desired value we use a variant of Lagrange inversion. With $n\ge 2$ we have

$$(n-2)! \; \underset{z}{\mathrm{res}} \; \frac{1}{z^n} T(z) T'(z).$$

We have $$z = \frac{2T(z)}{2+T(z)^2}$$ so putting $T(z) = w$ we obtain

$$z = \frac{2w}{2+w^2} \quad\text{and}\quad dw = T'(z) \; dz.$$

This yields for the residue

$$(n-2)! \; \underset{w}{\mathrm{res}} \; \frac{(2+w^2)^n}{2^n \times w^{n-1}}.$$

This is clearly zero when $n-2$ is odd. When $n$ is even we obtain

$$\frac{1}{2^n} (n-2)! [w^{n-2}] (2+w^2)^n = \frac{1}{2^n} (n-2)! {n\choose (n-2)/2} 2^{n-(n-2)/2} \\ = \frac{(n-2)!}{2^{(n-2)/2}} {n\choose (n-2)/2}.$$

This is the claim.

Remark. Lagrange Inversion is more machinery than we need here, we can also use the quadratic formula to obtain

$$T(z) = \frac{1-\sqrt{1-2z^2}}{z} \quad\text{so that}\quad T(z)^2 = \frac{2-2z^2}{z^2} -2\frac{\sqrt{1-2z^2}}{z^2}.$$

We get for $n\ge 2$ even $$[z^n] \sqrt{1-2z^2} = {1/2\choose n/2} (-1)^{n/2} 2^{n/2} \\ = (-1)^{n/2} 2^{n/2} \times \frac{1}{2} \frac{1}{(n/2)!} \prod_{q=0}^{n/2-2} (-1/2-q) = - \frac{1}{(n/2)!} \prod_{q=0}^{(n-4)/2} (1+2q) \\ = - \frac{(n-3)!}{(n/2)!} \frac{1}{2^{(n-4)/2}} \frac{1}{((n-4)/2)!}.$$

We then get for $n\ge 4$

$$[z^n]\left(-\frac{2}{z^2}\right) \sqrt{1-2z^2} = -2 [z^{n+2}] \sqrt{1-2z^2} = 2 \frac{(n-1)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!}.$$

Collecting everything we finally have

$$2 \frac{n!}{2(n-1)} \frac{(n-1)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!} \\= n! \frac{(n-2)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!} \\ = \frac{(n-2)!}{2^{(n-2)/2}} {n\choose (n-2)/2}$$

again as claimed.

Addendum. We now show how to compute the number of unrooted labeled trees with node degree at most three i.e. including nodes of degree two. This means we have pairs and singletons present in the Pruefer code. Suppose we have $q$ pairs. We must choose these from the $n$ available nodes and fill the rest of the Pruefer code with singletons. This yields

$$\sum_{q=0}^{\lfloor (n-2)/2\rfloor} {n\choose q} {n-q\choose n-2-2q} {n-2\choose 2,2,\ldots, 1,1,\ldots 1} \\ = (n-2)! \sum_{q=0}^{\lfloor (n-2)/2\rfloor} {n\choose q} {n-q\choose n-2-2q} \frac{1}{2^{q}}.$$

There are several possibilities to find alternate representations of this sum, we will use combinatorial classes. The class equation here now becomes

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\times\textsc{SET}_{=1}(\mathcal{T}) + \mathcal{Z}\times\textsc{SET}_{=2}(\mathcal{T}).$$

We thus obtain the functional equation

$$T(z) = z\left(1+ T(z) + \frac{1}{2} T(z)^2\right).$$

The construction goes through as before and we seek

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

To compute the desired value we again use a variant of Lagrange inversion. With $n\ge 2$ we get the same residue

$$(n-2)! \; \underset{z}{\mathrm{res}} \; \frac{1}{z^n} T(z) T'(z).$$

We have $$z = \frac{2T(z)}{2+ 2T(z) + T(z)^2}$$ so putting $T(z) = w$ we obtain

$$z = \frac{2w}{2+2w+w^2} \quad\text{and}\quad dw = T'(z) \; dz.$$

This yields for the residue

$$(n-2)! \; \underset{w}{\mathrm{res}} \; \frac{(2+2w+w^2)^n}{2^n \times w^{n-1}} \\ = \frac{(n-2)!}{2^n} [w^{n-2}] (1+(1+w)^2)^n \\ = \frac{(n-2)!}{2^n} [w^{n-2}] \sum_{q=0}^n {n\choose q} (1+w)^{2q} = \frac{(n-2)!}{2^n} \sum_{q=0}^n {n\choose q} {2q\choose n-2}.$$

This yields the sequence

$$1, 3, 16, 120, 1170, 14070, 201600, 3356640, 63730800, \\ 1359666000, 32212857600, 839350512000, 23860289653200, \\ 734964075846000, \ldots $$

which is OEIS A003692.

To see that this is the same as what the Pruefer codes produced we write in the Pruefer code formula

$$(n-2)! [w^{n-2}] (1+w)^n \sum_{q\ge 0} {n\choose q} \frac{1}{2^q} \frac{w^{2q}}{(1+w)^q}.$$

Here we have extended to infinity because the coefficient extractor enforces the upper limit. Contiuing,

$$(n-2)! [w^{n-2}] (1+w)^n \left[1+\frac{w^2}{2(1+w)}\right]^n \\ = \frac{(n-2)!}{2^n} [w^{n-2}] (1+(1+w)^2)^n.$$

This is the same as what the residue gave.