login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 13 19:49 EDT 2024. Contains 375910 sequences. (Running on oeis4.)