A368834 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

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

FORMULA

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

First differences of A134964.

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

EXAMPLE

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}

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}]

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.