A134964 Number of unlabeled n-node simple graphs with at most one cycle in each connected component.

1, 1, 2, 4, 9, 19, 46, 108, 273, 696, 1836, 4896, 13323, 36541, 101323, 282693, 793697, 2237982, 6335978, 17992622, 51235887, 146228734, 418181860, 1197972026, 3437159492, 9875198568, 28407202891, 81807809714, 235831978115, 680478488927, 1965160731704

Offset: 0

Author

Washington Bomfim, May 14 2008

Keywords

• nonn

Comments

a(n) is the number of pseudoforests on n nodes. - Eric W. Weisstein, Jun 11 2012

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500
• F. Ruskey, Combinatorial Generation, Eq.(4.27), 2003
• Eric Weisstein's World of Mathematics, Pseudoforest
• Wikipedia, Pseudoforest

Crossrefs

Cf. A005703 (number of pseudotrees), A137917 (number of maximal pseudoforests).

Programs

Mathematica

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];cu=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]],1];t[n_,k_]:=t[n,k]=b[n+1-k]+If[n<2k,0,t[n-k,k]];b[1]=1;b[n_]:=b[n]=Sum[b[i]t[n-1,i]i,{i,1,n-1}]/(n-1);ft=Table[b[i]-Sum[b[j]b[i-j],{j,1,i/2}]+If[OddQ[i],0,b[i/2](b[i/2]+1)/2],{i,1,nn}];
CoefficientList[Series[Product[1/(1-x^i)^(cu[[i]]+ft[[i]]),{i,1,nn-1}],{x,0,nn}],x]  (* Geoffrey Critzer, Oct 13 2012, after codes given by Robert A. Russell in A134964 and A000055 *)

Formula

a(0) = 1, for n >= 1, a(n) = Sum_{1*j_1 + 2*j_2 + ··· = n} ( Product_{i = 1..n} binomial(A005703(i+1) + j_i -1, j_i) ) [(4.27) of [F. Ruskey] with n replaced by n+1, and a_i replaced by A005703(i+1)].

Euler transform of A001429 + A000055. - Geoffrey Critzer, Oct 13 2012

Extensions

Edited by Washington Bomfim, Jun 27 2012

Terms a(29) and beyond from Andrew Howroyd, May 16 2021