How many trees on $\{1,2,3,4,5,6,7\}$ have a vertex of degree 2? 
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 !
 A: 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.$$
A: 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));

