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