login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137352 Number of labeled graphs with at least one cycle in which every connected component has at most one cycle. 3
1, 19, 317, 5592, 108839, 2356175, 56590729, 1499304898, 43532688017, 1376491137807, 47122376352941, 1737338689842008, 68657874376063231, 2896049933653455241, 129892644397271578571, 6173717934189145195530, 309998781844881257871161, 16399060640250318161199785 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 3..150

Wikipedia, Pseudoforest.

FORMULA

a(n) = A133686(n) - A001858(n).

EXAMPLE

a(6)=5592 because we have several cases of one unicyclic graph or two. Namely,

-One triangle and a forest of order 3. The unique triangle can be relabeled in C(6,3)=20 ways, we have 20*7= 140 graphs.

-One unicyclic graph with 4 nodes and a forest of order 2. The 15 distinct unicyclic graphs of 4 nodes can be relabeled in C(6,4) ways, so we have 2*15C(6,2), or 450 graphs.

-One unicyclic graph with 5 nodes and an isolated vertex. There are 222 different graphs that can be relabeled in C(6,5) ways, so 6 * 222 = 1332 graphs.

-One unicyclic graph with 6 nodes, so 3660 graphs.

-Two triangles. The triangles can be relabeled in C(6,3)/2 ways. So 10 graphs.

The total of all cases is 5592.

MAPLE

cy:= proc(n) option remember; local t; binomial(n-1, 2) *add ((n-3)! /(n-2-t)! *n^(n-2-t), t=1..n-2) end: T:= proc(n, k) option remember; local j; if k=0 then 1 elif k<0 or n<k then 0 else add (binomial (n-1, j) *((j+1)^(j-1) *T(n-j-1, k-j) +cy(j+1) *T(n-j-1, k-j-1)), j=0..k) fi end: a1:= n-> add (T(n, k), k=0..n): a2:= proc(n) option remember; if n=0 then 1 else add (binomial (n-1, j) *(j+1)^(j-1) *a2(n-1-j), j=0..n-1) fi end: a:= n-> a1(n)-a2(n): seq (a(n), n=3..25); # Alois P. Heinz, Sep 15 2008

MATHEMATICA

nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]!CoefficientList[Series[ Exp[Log[1/(1-t)]/2+t/2-3t^2/4]-Exp[t-t^2/2], {x, 0, nn}], x], 3]  (* Geoffrey Critzer, Mar 23 2013 *)

CROSSREFS

Cf. A140144, A001858, A057500.

Sequence in context: A138943 A111420 A166965 * A027541 A143699 A015676

Adjacent sequences:  A137349 A137350 A137351 * A137353 A137354 A137355

KEYWORD

nonn

AUTHOR

Washington Bomfim, May 17 2008

EXTENSIONS

Corrected and extended by Alois P. Heinz, Sep 15 2008

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 August 21 19:04 EDT 2019. Contains 326168 sequences. (Running on oeis4.)