A137917 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.