cp's OEIS Frontend

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

%I A369201 #10 Feb 02 2024 14:22:33
%S A369201 0,0,0,0,0,1,7,30,124,507,2036,8216,33515,138557,583040,2503093,
%T A369201 10985364,49361893,227342301,1073896332,5204340846,25874724616,
%U A369201 131937166616,689653979583,3693193801069,20247844510508,113564665880028,651138092719098,3813739129140469
%N A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).
%C A369201 These are graphs with n vertices and n edges having at least two cycles in the same component.
%H A369201 Andrew Howroyd, <a href="/A369201/b369201.txt">Table of n, a(n) for n = 0..50</a>
%H A369201 Gus Wiseman, <a href="/A369201/a369201.png">The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges</a>.
%F A369201 a(n) = A001434(n) - A137917(n).
%e A369201 The a(0) = 0 through a(6) = 7 simple graphs:
%e A369201   .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
%e A369201                                          {{12}{13}{14}{15}{23}{45}}
%e A369201                                          {{12}{13}{14}{23}{24}{34}}
%e A369201                                          {{12}{13}{14}{23}{24}{35}}
%e A369201                                          {{12}{13}{14}{23}{24}{56}}
%e A369201                                          {{12}{13}{14}{23}{25}{45}}
%e A369201                                          {{12}{13}{14}{25}{35}{45}}
%t A369201 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 A369201 Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]
%Y A369201 Without the choice condition we have A001434, covering A006649.
%Y A369201 The labeled version without choice is A116508, covering A367863, A367862.
%Y A369201 The complement is counted by A137917, labeled A137916.
%Y A369201 For any number of edges we have A140637, complement A134964.
%Y A369201 For labeled set-systems we have A368600.
%Y A369201 The case with loops is A368835, labeled A368596.
%Y A369201 The labeled version is A369143, covering A369144.
%Y A369201 A006129 counts covering graphs, unlabeled A002494.
%Y A369201 A007716 counts unlabeled multiset partitions, connected A007718.
%Y A369201 A054548 counts graphs covering n vertices with k edges, with loops A369199.
%Y A369201 A129271 counts connected choosable simple graphs, unlabeled A005703.
%Y A369201 Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.
%K A369201 nonn
%O A369201 0,7
%A A369201 _Gus Wiseman_, Jan 22 2024
%E A369201 a(25) onwards from _Andrew Howroyd_, Feb 02 2024