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,3

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

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

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

Crossrefs

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

Sequence in context: A036718 A372102 A380052 * A318798 A318851 A052328

Adjacent sequences: A134961 A134962 A134963 * A134965 A134966 A134967

Keyword

nonn

Author

Washington Bomfim, May 14 2008

Extensions

Edited by Washington Bomfim, Jun 27 2012

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

Status

approved