cp's OEIS Frontend

A144958 Number of unlabeled acyclic graphs covering n vertices.

%I A144958 #18 Aug 01 2024 12:07:10
%S A144958 1,0,1,1,3,4,10,17,39,77,176,381,891,2057,4941,11915,29391,73058,
%T A144958 184236,468330,1202349,3108760,8097518,21218776,55925742,148146312,
%U A144958 394300662,1053929982,2828250002,7617271738,20584886435,55802753243
%N A144958 Number of unlabeled acyclic graphs covering n vertices.
%C A144958 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 A144958 The labeled version is A105784. The connected case is A000055. This is the covering case of A005195. - _Gus Wiseman_, Apr 29 2024
%H A144958 Andrew Howroyd, <a href="/A144958/b144958.txt">Table of n, a(n) for n = 0..1000</a>
%F A144958 a(n) = A005195(n) - A005195(n-1).
%e A144958 From _Gus Wiseman_, Apr 29 2024: (Start)
%e A144958 Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 4 forests:
%e A144958   {}    .    {12}    {13,23}    {12,34}       {12,35,45}
%e A144958                                 {13,24,34}    {13,24,35,45}
%e A144958                                 {14,24,34}    {14,25,35,45}
%e A144958                                               {15,25,35,45}
%e A144958 (End)
%t A144958 brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}]]];
%t A144958 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 A144958 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 A144958 (PARI)
%o A144958 EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o A144958 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 A144958 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 A144958 The connected case is A000055.
%Y A144958 This is the covering case of A005195, labeled A001858.
%Y A144958 The labeled version is A105784.
%Y A144958 For triangles instead of cycles we have A372169, non-covering A006785.
%Y A144958 Unique cycle: A372191 (lab A372195), non-covering A236570 (lab A372193).
%Y A144958 A006125 counts simple graphs, unlabeled A000088.
%Y A144958 A006129 counts covering graphs, unlabeled A002494.
%Y A144958 Cf. A000272, A053530, A054548, A137917, A144959, A372174.
%K A144958 nonn
%O A144958 0,5
%A A144958 _Washington Bomfim_, Sep 27 2008
%E A144958 Name changed and 1 prepended by _Gus Wiseman_, Apr 29 2024.