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

1, 0, 0, 1, 2, 5, 14, 35, 97, 264, 733, 2034, 5728, 16101, 45595, 129327, 368093, 1049520, 2999415, 8584857, 24612114, 70652441, 203075740, 584339171, 1683151508, 4852736072, 14003298194, 40441136815, 116880901512, 338040071375, 978314772989, 2833067885748, 8208952443400

Offset

0,5

Comments

a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - Geoffrey Critzer, Oct 12 2012

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

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

F. Ruskey, Combinatorial Generation, p. 79, Eq.(4.27), 2003

Eric Weisstein's World of Mathematics, Pseudoforest.

Wikipedia, Pseudoforest.

Formula

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)].

Euler transform of A001429. - Geoffrey Critzer, Oct 12 2012

Example

From Gus Wiseman, Jan 25 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
                        {12,13,24,34}  {12,13,14,23,25}
                                       {12,13,14,23,45}
                                       {12,13,14,25,35}
                                       {12,13,24,35,45}
(End)

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}]; 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 *)
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n], {2}], {n}], Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 5}] (* Gus Wiseman, Jan 25 2024 *)

Crossrefs

Cf. A008483, A137918.

The connected case is A001429.

Without the choice condition we have A001434, covering A006649.

For any number of edges we have A134964, complement A140637.

The labeled version is A137916.

The version with loops is A369145, complement A368835.

The complement is counted by A369201, labeled A369143, covering A369144.

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A129271 counts connected choosable simple graphs, unlabeled A005703.

Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.

Sequence in context: A369591 A299164 A131408 * A360031 A244099 A201371

Adjacent sequences: A137914 A137915 A137916 * A137918 A137919 A137920

Keyword

nonn

Author

Washington Bomfim, Feb 24 2008

Extensions

Edited by Washington Bomfim, Jun 27 2012

Terms a(30) and beyond from Andrew Howroyd, May 05 2018

Offset changed to 0 by Gus Wiseman, Jan 27 2024

Status

approved