login
Number of unlabeled acyclic graphs covering n vertices.
18

%I #18 Aug 01 2024 12:07:10

%S 1,0,1,1,3,4,10,17,39,77,176,381,891,2057,4941,11915,29391,73058,

%T 184236,468330,1202349,3108760,8097518,21218776,55925742,148146312,

%U 394300662,1053929982,2828250002,7617271738,20584886435,55802753243

%N Number of unlabeled acyclic graphs covering n vertices.

%C 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.

%C The labeled version is A105784. The connected case is A000055. This is the covering case of A005195. - _Gus Wiseman_, Apr 29 2024

%H Andrew Howroyd, <a href="/A144958/b144958.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = A005195(n) - A005195(n-1).

%e From _Gus Wiseman_, Apr 29 2024: (Start)

%e Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 4 forests:

%e {} . {12} {13,23} {12,34} {12,35,45}

%e {13,24,34} {13,24,35,45}

%e {14,24,34} {14,25,35,45}

%e {15,25,35,45}

%e (End)

%t brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}]]];

%t 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[#]&];

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

%o (PARI)

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}

%o 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)}

%o 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

%Y The connected case is A000055.

%Y This is the covering case of A005195, labeled A001858.

%Y The labeled version is A105784.

%Y For triangles instead of cycles we have A372169, non-covering A006785.

%Y Unique cycle: A372191 (lab A372195), non-covering A236570 (lab A372193).

%Y A006125 counts simple graphs, unlabeled A000088.

%Y A006129 counts covering graphs, unlabeled A002494.

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

%K nonn

%O 0,5

%A _Washington Bomfim_, Sep 27 2008

%E Name changed and 1 prepended by _Gus Wiseman_, Apr 29 2024.