cp's OEIS Frontend

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

%I A137917 #58 Feb 16 2025 08:33:07
%S A137917 1,0,0,1,2,5,14,35,97,264,733,2034,5728,16101,45595,129327,368093,
%T A137917 1049520,2999415,8584857,24612114,70652441,203075740,584339171,
%U A137917 1683151508,4852736072,14003298194,40441136815,116880901512,338040071375,978314772989,2833067885748,8208952443400
%N A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.
%C A137917 a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - _Geoffrey Critzer_, Oct 12 2012
%C A137917 Also the number of unlabeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. - _Gus Wiseman_, Jan 25 2024
%H A137917 Andrew Howroyd, <a href="/A137917/b137917.txt">Table of n, a(n) for n = 0..500</a>
%H A137917 F. Ruskey, <a href="http://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf">Combinatorial Generation, p. 79, Eq.(4.27)</a>, 2003
%H A137917 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Pseudoforest.html">Pseudoforest</a>.
%H A137917 Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>.
%F A137917 a(n) = Sum_{1*j_1 + 2*j_2 + ... = n} (Product_{i=3..n} binomial(A001429(i) + j_i -1, j_i)). [F. Ruskey p. 79, (4.27) with n replaced by n+1, and a_i replaced by A001429(i)].
%F A137917 Euler transform of A001429. - _Geoffrey Critzer_, Oct 12 2012
%e A137917 From _Gus Wiseman_, Jan 25 2024: (Start)
%e A137917 Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
%e A137917   {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
%e A137917                         {12,13,24,34}  {12,13,14,23,25}
%e A137917                                        {12,13,14,23,45}
%e A137917                                        {12,13,14,25,35}
%e A137917                                        {12,13,24,35,45}
%e A137917 (End)
%t A137917 Needs["Combinatorica`"];
%t A137917 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}];c=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];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]   (* _Geoffrey Critzer_, Oct 12 2012, after code given by _Robert A. Russell_ in A000081 *)
%t A137917 brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
%t A137917 Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]!={}&]]],{n,0,5}] (* _Gus Wiseman_, Jan 25 2024 *)
%Y A137917 Cf. A008483, A137918.
%Y A137917 The connected case is A001429.
%Y A137917 Without the choice condition we have A001434, covering A006649.
%Y A137917 For any number of edges we have A134964, complement A140637.
%Y A137917 The labeled version is A137916.
%Y A137917 The version with loops is A369145, complement A368835.
%Y A137917 The complement is counted by A369201, labeled A369143, covering A369144.
%Y A137917 A006129 counts covering graphs, unlabeled A002494.
%Y A137917 A054548 counts graphs covering n vertices with k edges, with loops A369199.
%Y A137917 A129271 counts connected choosable simple graphs, unlabeled A005703.
%Y A137917 Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.
%K A137917 nonn
%O A137917 0,5
%A A137917 _Washington Bomfim_, Feb 24 2008
%E A137917 Edited by _Washington Bomfim_, Jun 27 2012
%E A137917 Terms a(30) and beyond from _Andrew Howroyd_, May 05 2018
%E A137917 Offset changed to 0 by _Gus Wiseman_, Jan 27 2024