OFFSET
1,3
LINKS
Marko Riedel et al., How many trees have a vertex of degree two
FORMULA
a(n) = (n-2)!*Sum_{q=1..n-2} C(n,q)*(-1)^(q+1)*(n-q)^(n-2-q)/(n-2-q)! where n >= 2.
EXAMPLE
When n=4 there are two types of trees: paths (24!/2 trees) or a star (4 trees) for a total of 4^(4-2) trees. Of these only the paths contain a vertex of degree 2 (2 in fact). When n=5 there are three types of trees: paths (5!/2 trees), a star (5 trees) or a fork (C(5,1) x C(4, 2) x 2) for a total of 5^(5-2) trees. Of these only the paths and the fork contain a vertex of degree 2.
MATHEMATICA
a[1] = 0; a[n_] := (n-2)! Sum[Binomial[n, q] (-1)^(q+1) (n-q)^(n-2-q) / (n-2-q)!, {q, 1, n-2}]; Array[a, 20] (* Jean-François Alcover, Feb 15 2018 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Marko Riedel, Feb 11 2018
STATUS
approved