Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #14 Feb 02 2024 14:49:24
%S 0,0,0,0,2,13,95,826,11137,261899,11729360,1006989636,164072166301,
%T 50336940172142,29003653625802754,31397431814146891910,
%U 63969589218557753075156,245871863137828405124380563,1787331789281458167615190373076,24636021675399858912682459601585276
%N Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).
%C These are simple graphs covering n vertices such that some connected component has at least two cycles.
%H Andrew Howroyd, <a href="/A369202/b369202.txt">Table of n, a(n) for n = 0..50</a>
%F First differences of A140637.
%F a(n) = A002494(n) - A368834(n).
%e Representatives of the a(4) = 2 and a(5) = 13 simple graphs:
%e {12}{13}{14}{23}{24} {12}{13}{14}{15}{23}{24}
%e {12}{13}{14}{23}{24}{34} {12}{13}{14}{15}{23}{45}
%e {12}{13}{14}{23}{24}{35}
%e {12}{13}{14}{23}{25}{45}
%e {12}{13}{14}{25}{35}{45}
%e {12}{13}{14}{15}{23}{24}{25}
%e {12}{13}{14}{15}{23}{24}{34}
%e {12}{13}{14}{15}{23}{24}{35}
%e {12}{13}{14}{23}{24}{35}{45}
%e {12}{13}{14}{15}{23}{24}{25}{34}
%e {12}{13}{14}{15}{23}{24}{35}{45}
%e {12}{13}{14}{15}{23}{24}{25}{34}{35}
%e {12}{13}{14}{15}{23}{24}{25}{34}{35}{45}
%t brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
%t Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]==0&]]],{n,0,5}]
%Y Without the choice condition we have A002494, labeled A006129.
%Y The connected case is A140636.
%Y This is the covering case of A140637, complement A134964.
%Y The labeled version is A367868, complement A367869.
%Y The complement is counted by A368834.
%Y The version with loops is A369147, complement A369200.
%Y A005703 counts unlabeled connected choosable simple graphs, labeled A129271.
%Y A007716 counts unlabeled multiset partitions, connected A007718.
%Y A054548 counts graphs covering n vertices with k edges, with loops A369199.
%Y A283877 counts unlabeled set-systems, connected A300913.
%Y Cf. A000088, A000612, A006649, A001434, A055621, A137916, A137917, A140638, A368596, A369141, A369146.
%K nonn
%O 0,5
%A _Gus Wiseman_, Jan 23 2024