|
%I #12 Apr 29 2024 10:52:26
%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
%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 *)
%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 A372192 (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.
|
