cp's OEIS Frontend

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

%I A134964 #46 Feb 16 2025 08:33:07
%S A134964 1,1,2,4,9,19,46,108,273,696,1836,4896,13323,36541,101323,282693,
%T A134964 793697,2237982,6335978,17992622,51235887,146228734,418181860,
%U A134964 1197972026,3437159492,9875198568,28407202891,81807809714,235831978115,680478488927,1965160731704
%N A134964 Number of unlabeled n-node simple graphs with at most one cycle in each connected component.
%C A134964 a(n) is the number of pseudoforests on n nodes. - _Eric W. Weisstein_, Jun 11 2012
%H A134964 Andrew Howroyd, <a href="/A134964/b134964.txt">Table of n, a(n) for n = 0..500</a>
%H A134964 F. Ruskey, <a href="http://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf">Combinatorial Generation, Eq.(4.27)</a>, 2003
%H A134964 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Pseudoforest.html">Pseudoforest</a>
%H A134964 Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>
%F A134964 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)].
%F A134964 Euler transform of A001429 + A000055. - _Geoffrey Critzer_, Oct 13 2012
%t A134964 Needs["Combinatorica`"];
%t A134964 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}];
%t A134964 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 *)
%Y A134964 Cf. A005703 (number of pseudotrees), A137917 (number of maximal pseudoforests).
%K A134964 nonn
%O A134964 0,3
%A A134964 _Washington Bomfim_, May 14 2008
%E A134964 Edited by _Washington Bomfim_, Jun 27 2012
%E A134964 Terms a(29) and beyond from _Andrew Howroyd_, May 16 2021