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

Author

Geoffrey Critzer, Apr 28 2011

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A084546, A000272, A014068.

Programs

Magma

[Binomial(Binomial(n,2),n-1) - n^(n-2): n in [1..20]]; // G. C. Greubel, Jan 14 2018

Mathematica

Table[Binomial[Binomial[n,2],n-1]-n^(n-2),{n,1,20}]

PARI

for(n=1,20, print1(binomial(binomial(n,2),n-1) - n^(n-2), ", ")) \\ G. C. Greubel, Jan 14 2018

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.