A137352 Number of labeled graphs with at least one cycle in which every connected component has at most one cycle.

1, 19, 317, 5592, 108839, 2356175, 56590729, 1499304898, 43532688017, 1376491137807, 47122376352941, 1737338689842008, 68657874376063231, 2896049933653455241, 129892644397271578571, 6173717934189145195530, 309998781844881257871161, 16399060640250318161199785

Offset: 3

Author

Washington Bomfim, May 17 2008

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A140144, A001858, A057500.

Programs

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 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 *)

Formula

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

Extensions

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