[go: up one dir, main page]

login
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
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.
The labeled version is A105784. The connected case is A000055. This is the covering case of A005195. - Gus Wiseman, Apr 29 2024
LINKS
FORMULA
a(n) = A005195(n) - A005195(n-1).
EXAMPLE
From Gus Wiseman, Apr 29 2024: (Start)
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
The connected case is A000055.
This is the covering case of A005195, labeled A001858.
The labeled version is A105784.
For triangles instead of cycles we have A372169, non-covering A006785.
Unique cycle: A372191 (lab A372195), non-covering A236570 (lab A372193).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Sequence in context: A172416 A317883 A337089 * A034775 A280246 A338012
KEYWORD
nonn
AUTHOR
Washington Bomfim, Sep 27 2008
EXTENSIONS
Name changed and 1 prepended by Gus Wiseman, Apr 29 2024.
STATUS
approved