How many trees on $\{1,2,3,4,5,6,7\}$ have a vertex of degree 2?

Question

How many trees on $\{1,2,3,4,5,6,7\}$ have a vertex of degree 2 ?

Attempt -

It feels like an inclusion exclusion problem (using kailey's code) , let's define $|A_i| \Rightarrow $ vertex $i$ is of degree $1$.

$|Ai\, \cup A_j$| - vertices $i,j$ are of degree $1$ and so on.

So following my calculation we might get -

$7 \cdot 5\cdot 6^4 - \binom{7}{2}\binom{5}{2}\cdot2\cdot5^3+ \binom{7}{3}\binom{5}{3}\cdot3!\cdot4^2 - \binom{7}{4}\binom{5}{4}\cdot4!\cdot3 + \binom{7}{5}5!$

What do you think? thank you !

Answer 1

I think that your formula is correct. It gives $16380$. Below there is an alternative approach with the same final result.

For a labeled tree with $7$ vertices we have that $$\sum_{v \in \{1,2,3,4,5,6,7\}} \deg v = 2(7-1)=12.$$ So if a tree has NOT vertices of degree $2$ and it has $m$ leaves of degree $1$ then $$12\geq l+3(7-l)$$ which means that $l$ can be $5$ or $6$ (there is at least one vertex which is not a leaf). Hence the degree sequence is $$1,1,1,1,1,3,4\quad\text{or}\quad 1,1,1,1,1,1,6.$$ By Cayley's formula there are $7^{7−2}$ labeled trees with $7$ vertices and the number of trees with vertices $1,2,3,4,5,6,7$ of degrees $d_1, d_2,\dots, d_7$ is $$\binom{7-2}{d_1-1,d_2-1,\dots, d_7-1}.$$ Hence the number of trees with vertices $1,2,3,4,5,6,7$ have at least a vertex of degree $2$ is $$7^{5}-7\cdot 6\cdot\frac{5!}{2!3!}-7\cdot \frac{5!}{5!}=16380.$$

Answer 2

Here is an answer for trees on $n$ nodes using Pruefer codes. The degree of a node is one more than the number of times it appears in the code, so a node of degree two appears once. Hence for trees not containing a node of degree two all nodes either appear not at all or at least twice. With $n$ nodes this gives the EGF

$$\prod_{q=1}^n \left(1+\sum_{p\ge 2} \frac{z^p}{p!}\right) = (\exp(z)-z)^n.$$

Extracting the coefficient we obtain

$$(n-2)! [z^{n-2}] (\exp(z)-z)^n = (n-2)! [z^{n-2}] \sum_{q=0}^n {n\choose q} \exp((n-q)z) (-1)^q z^q \\ = (n-2)! \sum_{q=0}^{n-2} {n\choose q} (-1)^q [z^{n-2-q}] \exp((n-q)z) \\= (n-2)! \sum_{q=0}^{n-2} {n\choose q} (-1)^q \frac{(n-q)^{n-2-q}}{(n-2-q)!}.$$

Therefore the closed form for trees containing at least one node of degree two is

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

or

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

We get starting at $n=1$ the sequence

$$0, 0, 3, 12, 120, 1200, 16380, 255696, 4726008, 99107280, \ldots $$

which is not in the OEIS. Given this fact we verfied these data by enumeration which produced a match, as seen below.

with(combinat);

trees_deg2 :=
proc(n)
option remember;
local ind, d, a, mset, deg, res;

    if n=1 then return 0 fi;

    res := 0;

    for ind from n^(n-2) to 2*n^(n-2)-1 do
        d := convert(ind, base, n);
        a := [seq(d[q]+1, q=1..n-2)];

        mset := convert(a, `multiset`);
        deg := map(ent -> ent[2]+1, mset);

        if member(2, deg) then
            res := res + 1;
        fi;
    od;

    res;
end;


T := n ->
`if`(n=1, 0,
     (n-2)!*add(binomial(n,q)*(-1)^(q+1)*(n-q)^(n-2-q)/(n-2-q)!,
                q=1..n-2));