login
A189831
Labeled simple graphs with n nodes and n-1 edges that are not trees.
1
0, 0, 0, 4, 85, 1707, 37457, 921896, 25477371, 786163135, 26890701739, 1012165431744, 41638805754078, 1860589088529164, 89802422444553825, 4658465562594667088, 258566755450911870007, 15294477441385413149679, 960641026388207044487891, 63861339527473864490450300
OFFSET
1,4
COMMENTS
Equivalently a(n) is the number of labeled simple graphs on n nodes having n-1 edges that have at least two connected components.
Evidently almost all such graphs are disconnected.
LINKS
FORMULA
a(n) = C(C(n,2),n-1) - n^(n-2) = A014068(n-1)-A000272(n), where C(x,y) is the binomial coefficient.
EXAMPLE
a(4) = 4 because there are 20 labeled simple graphs on four nodes with three edges but 16 of these are connected i.e. they are trees.
MATHEMATICA
Table[Binomial[Binomial[n, 2], n-1]-n^(n-2), {n, 1, 20}]
PROG
(PARI) for(n=1, 20, print1(binomial(binomial(n, 2), n-1) - n^(n-2), ", ")) \\ G. C. Greubel, Jan 14 2018
(Magma) [Binomial(Binomial(n, 2), n-1) - n^(n-2): n in [1..20]]; // G. C. Greubel, Jan 14 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Apr 28 2011
STATUS
approved