A189831 Labeled simple graphs with n nodes and n-1 edges that are not trees.

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

G. C. Greubel, Table of n, a(n) for n = 1..370

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

Cf. A084546, A000272, A014068.

Sequence in context: A184100 A059830 A358439 * A223955 A116330 A055776

Adjacent sequences: A189828 A189829 A189830 * A189832 A189833 A189834

Keyword

nonn

Author

Geoffrey Critzer, Apr 28 2011

Status

approved