A144958 Number of unlabeled acyclic graphs covering n vertices.

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

Andrew Howroyd, Table of n, a(n) for n = 0..1000

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.

Cf. A000272, A053530, A054548, A137917, A144959, A372174.

Sequence in context: A172416 A317883 A337089 * A034775 A280246 A338012

Adjacent sequences: A144955 A144956 A144957 * A144959 A144960 A144961

Keyword

nonn

Author

Washington Bomfim, Sep 27 2008

Extensions

Name changed and 1 prepended by Gus Wiseman, Apr 29 2024.

Status

approved