A144958 - OEIS

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

(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

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.