login
Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).
4

%I #11 Feb 02 2024 14:49:55

%S 1,0,1,2,5,10,27,62,165,423,1140,3060,8427,23218,64782,181370,511004,

%T 1444285,4097996,11656644,33243265,94992847,271953126,779790166,

%U 2239187466,6438039076,18532004323,53400606823,154024168401,444646510812,1284682242777

%N Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

%H Andrew Howroyd, <a href="/A368834/b368834.txt">Table of n, a(n) for n = 0..500</a>

%F Euler transform of A005703 with A005703(1) = 0.

%F First differences of A134964.

%F a(n) = A002494(n) - A369202(n).

%e Representatives of the a(2) = 1 through a(5) = 10 simple graphs:

%e {12} {12}{13} {12}{34} {12}{13}{45}

%e {12}{13}{23} {12}{13}{14} {12}{13}{14}{15}

%e {12}{13}{24} {12}{13}{14}{25}

%e {12}{13}{14}{23} {12}{13}{23}{45}

%e {12}{13}{24}{34} {12}{13}{24}{35}

%e {12}{13}{14}{15}{23}

%e {12}{13}{14}{23}{25}

%e {12}{13}{14}{23}{45}

%e {12}{13}{14}{25}{35}

%e {12}{13}{24}{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 A005703, labeled A129271.

%Y This is the covering case of A134964, complement A140637.

%Y The labeled version is A367869, complement A367868.

%Y The version with loops is A369200, complement A369147.

%Y The complement is counted by A369202.

%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, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

%K nonn

%O 0,4

%A _Gus Wiseman_, Jan 23 2024