The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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.

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