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

1, 0, 1, 2, 5, 10, 27, 62, 165, 423, 1140, 3060, 8427, 23218, 64782, 181370, 511004, 1444285, 4097996, 11656644, 33243265, 94992847, 271953126, 779790166, 2239187466, 6438039076, 18532004323, 53400606823, 154024168401, 444646510812, 1284682242777

Offset: 0

Author

Gus Wiseman, Jan 23 2024

Keywords

• nonn

Examples

			Representatives of the a(2) = 1 through a(5) = 10 simple graphs:
  {12}  {12}{13}      {12}{34}          {12}{13}{45}
        {12}{13}{23}  {12}{13}{14}      {12}{13}{14}{15}
                      {12}{13}{24}      {12}{13}{14}{25}
                      {12}{13}{14}{23}  {12}{13}{23}{45}
                      {12}{13}{24}{34}  {12}{13}{24}{35}
                                        {12}{13}{14}{15}{23}
                                        {12}{13}{14}{23}{25}
                                        {12}{13}{14}{23}{45}
                                        {12}{13}{14}{25}{35}
                                        {12}{13}{24}{35}{45}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..500

Crossrefs

Without the choice condition we have A002494, labeled A006129.

The connected case is A005703, labeled A129271.

This is the covering case of A134964, complement A140637.

The labeled version is A367869, complement A367868.

The version with loops is A369200, complement A369147.

The complement is counted by A369202.

A007716 counts unlabeled multiset partitions, connected A007718.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A283877 counts unlabeled set-systems, connected A300913.

Cf. A000088, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

Programs

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]],{n,0,5}]

Formula

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

First differences of A134964.

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