6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @bof I edited my question accordingly. $\endgroup$ – Roey Waitsman Jun 7 '16 at 10:00
  • $\begingroup$ a coclusion from prufer code is: the number of labaled trees that their degrees are: $d_1,............,d_n $ are as the number of serieses with n-2 length with the numbers 1,.........,n when the i-th number appears $d_i -1$ times This is the way i calculated that range, noting that minimum case- all the vertices with degree 1, maximum case- all the vertices with degree 3 $\endgroup$ – Roey Waitsman Jun 7 '16 at 10:28
  • $\begingroup$ @AustinMohr it's not correct considering the restrictions above. $\endgroup$ – Roey Waitsman Jun 8 '16 at 16:52
8
$\begingroup$

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

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

$$\frac{n!}{2(n-1)} [z^n] T(z)^2 = \frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$

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

$$z = \frac{2w}{2+w^2} \quad\text{and}\quad dz = \left( \frac{2}{2+w^2} - \frac{2w}{(2+w^2)^2} 2w \right) dw.$$

This yields for the integral

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

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

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

Now when $n=2$ this evaluates to

$$\frac{2}{2^3\times 1} \times {1\choose 0} 2^{n-1} \times 2 = 1$$

which is the correct value. Continuing with $n\ge 4$ we obtain

$$\frac{n!}{2^{n+1}(n-1)} \left({n-1\choose (n-2)/2} 2^{n-1-(n-2)/2} \times 2 - {n-1\choose (n-4)/2} 2^{n-1-(n-4)/2}\right) \\ = n\times(n-2)!\times \left({n-1\choose (n-2)/2} 2^{-1-(n-2)/2} - {n-1\choose (n-4)/2} 2^{-2-(n-4)/2}\right) \\ = \frac{(n-2)!}{2^{n/2}} \times n \times \left({n-1\choose (n-2)/2} - {n-1\choose (n-4)/2} \right) \\ = \frac{(n-2)!}{2^{n/2}} \times \left(n {n-1\choose (n-2)/2} - n \frac{(n-2)/2}{n} {n\choose (n-2)/2} \right) \\ = \frac{(n-2)!}{2^{n/2}} \times \left((n+2)/2 - (n-2)/2 \right) {n\choose (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} \\ = \sum_{q=0}^{\lfloor (n-2)/2\rfloor} {n\choose q} {n-q\choose n-2-2q} \frac{(n-2)!}{2^{q}}.$$

There are several possibilities to simplify this, 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.$$

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

$$\frac{n!}{2(n-1)} [z^n] T(z)^2 = \frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$

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

$$z = \frac{2w}{2+2w+w^2} \quad\text{and}\quad dz = \left( \frac{2}{2+2w+w^2} - \frac{2w \times (2w+2)}{(2+2w+w^2)^2} \right) dw.$$

This yields for the integral

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

We write

$$(2+2w+w^2)^{n-1} = (1+(w+1)^2)^{n-1} = \sum_{q=0}^{n-1} {n-1\choose q} (w+1)^{2q}$$

Extracting the residue we obtain the formula

$$\frac{n!}{2^{n+1}(n-1)} \sum_{q=0}^{n-1} {n-1\choose q} \left(2\times {2q\choose n-2} - {2q\choose n-4}\right).$$

This yields the sequence

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

which is OEIS A003692.

We introduce a binomial coefficient integral in an effort to get a better closed form. Put

$${n-q\choose n-2-2q} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1-2q}} (1+v)^{n-q}\; dv.$$

Observe that this vanishes when $\lfloor(n-2)/2\rfloor \lt q\le n$ so we may extend the upper limit of the sum to $n,$ obtaining

$$\frac{(n-2)!}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (1+v)^{n} \sum_{q=0}^n {n\choose q} \frac{v^{2q}}{2^q(1+v)^q} \; dv \\ = \frac{(n-2)!}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (1+v)^{n} \left(1+\frac{v^2}{2(1+v)}\right)^n \; dv \\ = \frac{(n-2)!}{2^n\times 2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (2+2v+v^2)^n\; dv.$$

Extracting the residue we get a very slight improvement which yields

$$\frac{(n-2)!}{2^n} \sum_{q=0}^{n} {n\choose q} {2q\choose n-2}.$$

$\endgroup$

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.