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

0, 0, 0, 0, 0, 0, 90, 4935, 200970, 7636860, 291089610, 11459170800, 471932476290, 20447369179380, 933942958593645, 44981469288560805, 2282792616992648670, 121924195590795244920, 6843305987751060036720, 403003907531795513467260, 24861219342100679072572470

Offset: 0

Author

Gus Wiseman, Jan 21 2024

Keywords

• nonn

Examples

			The term a(6) = 90 counts all permutations of the (non-connected) graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}}.
		

Links

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

Crossrefs

The covering complement is counted by A137916.

Without the choice condition we have A367863, covering case of A116508.

Allowing any number of edges gives A367868, covering case of A367867.

With loops we have A368730, covering case of A368596, unlabeled A368835.

This is the covering case of A369143.

A003465 counts covering set-systems, unlabeled A055621.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A058891 counts set-systems, unlabeled A000612.

A322661 counts covering loop-graphs, connected A062740.

Cf. A000085, A057500, A129271, A133686, A333331, A367869, A367901, A367903, A367907, A368600.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{2}], {n}],Union@@#==Range[n]&&Length[Select[Tuples[#], UnsameQ@@#&]]==0&]],{n,0,6}]

Formula

a(n) = A367863(n) - A137916(n). - Andrew Howroyd, Feb 02 2024

Extensions

a(8) onwards from Andrew Howroyd, Feb 02 2024