|
|
A144958
|
|
Number of unlabeled acyclic graphs covering n vertices.
|
|
18
|
|
|
1, 0, 1, 1, 3, 4, 10, 17, 39, 77, 176, 381, 891, 2057, 4941, 11915, 29391, 73058, 184236, 468330, 1202349, 3108760, 8097518, 21218776, 55925742, 148146312, 394300662, 1053929982, 2828250002, 7617271738, 20584886435, 55802753243
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
a(n) is the number of forests with n unlabeled nodes without isolated vertices. This follows from the fact that for n>0 A005195(n-1) counts the forests with one or more isolated nodes.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 4 forests:
{} . {12} {13,23} {12,34} {12,35,45}
{13,24,34} {13,24,35,45}
{14,24,34} {14,25,35,45}
{15,25,35,45}
(End)
|
|
MATHEMATICA
|
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];
cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations/@Subsets[Union@@y, {k}], And@@Table[MemberQ[Sort/@y, Sort[{#[[i]], #[[If[i==k, 1, i+1]]]}]], {i, k}]&], {k, 3, Length[y]}], Min@@#==First[#]&];
Table[Length[Union[Union[brute/@Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[cyc[#]]==0&]]]], {n, 0, 5}] (* Gus Wiseman, Apr 29 2024 *)
|
|
PROG
|
(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n), v=EulerT(Vec(t - t^2/2 + subst(t, x, x^2)/2))); concat([1, 0], vector(#v-1, i, v[i+1]-v[i]))} \\ Andrew Howroyd, Aug 01 2024
|
|
CROSSREFS
|
For triangles instead of cycles we have A372169, non-covering A006785.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Name changed and 1 prepended by Gus Wiseman, Apr 29 2024.
|
|
STATUS
|
approved
|
|
|
|