

A294198


Labeled trees on n nodes with at least one node of degree two.


1



0, 0, 3, 12, 120, 1200, 16380, 255696, 4726008, 99107280, 2346042600, 61706210280, 1788467429892, 56618211155688, 1944581982268380, 72019509651227040, 2861473883255362800, 121414006972684901664, 5479661140682410928592, 262122044885503316203320
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


LINKS



FORMULA

a(n) = (n2)!*Sum_{q=1..n2} C(n,q)*(1)^(q+1)*(nq)^(n2q)/(n2q)! 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^(42) 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^(52) trees. Of these only the paths and the fork contain a vertex of degree 2.


MATHEMATICA

a[1] = 0; a[n_] := (n2)! Sum[Binomial[n, q] (1)^(q+1) (nq)^(n2q) / (n2q)!, {q, 1, n2}]; Array[a, 20] (* JeanFrançois Alcover, Feb 15 2018 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



