|
%I #53 Jan 28 2024 04:49:33
%S 1,0,0,1,2,5,14,35,97,264,733,2034,5728,16101,45595,129327,368093,
%T 1049520,2999415,8584857,24612114,70652441,203075740,584339171,
%U 1683151508,4852736072,14003298194,40441136815,116880901512,338040071375,978314772989,2833067885748,8208952443400
%N a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.
%C a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - _Geoffrey Critzer_, Oct 12 2012
%C 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 Andrew Howroyd, <a href="/A137917/b137917.txt">Table of n, a(n) for n = 0..500</a>
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudoforest.html">Pseudoforest</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>.
%F 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 Euler transform of A001429. - _Geoffrey Critzer_, Oct 12 2012
%e From _Gus Wiseman_, Jan 25 2024: (Start)
%e Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
%e {} . . {12,13,23} {12,13,14,23} {12,13,14,15,23}
%e {12,13,24,34} {12,13,14,23,25}
%e {12,13,14,23,45}
%e {12,13,14,25,35}
%e {12,13,24,35,45}
%e (End)
%t Needs["Combinatorica`"];
%t 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 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 Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]!={}&]]],{n,0,5}] (* _Gus Wiseman_, Jan 25 2024 *)
%Y Cf. A008483, A137918.
%Y The connected case is A001429.
%Y Without the choice condition we have A001434, covering A006649.
%Y For any number of edges we have A134964, complement A140637.
%Y The labeled version is A137916.
%Y The version with loops is A369145, complement A368835.
%Y The complement is counted by A369201, labeled A369143, covering A369144.
%Y A006129 counts covering graphs, unlabeled A002494.
%Y A054548 counts graphs covering n vertices with k edges, with loops A369199.
%Y A129271 counts connected choosable simple graphs, unlabeled A005703.
%Y Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.
%K nonn
%O 0,5
%A _Washington Bomfim_, Feb 24 2008
%E Edited by _Washington Bomfim_, Jun 27 2012
%E Terms a(30) and beyond from _Andrew Howroyd_, May 05 2018
%E Offset changed to 0 by _Gus Wiseman_, Jan 27 2024
|
