|
|
A137917
|
|
a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.
|
|
28
|
|
|
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
|
|
|
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)].
|
|
EXAMPLE
|
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
|
A054548 counts graphs covering n vertices with k edges, with loops A369199.
Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|