login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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: A229185 A184100 A059830 * A223955 A116330 A055776

Adjacent sequences:  A189828 A189829 A189830 * A189832 A189833 A189834

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Apr 28 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 16:44 EST 2021. Contains 349430 sequences. (Running on oeis4.)