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

Table of n, a(n) for n=0..31.

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 *)

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 A372192 (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