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

0, 0, 0, 0, 0, 30, 1335, 47460, 1651230, 59636640, 2284113762, 93498908580, 4099070635935, 192365988161490, 9646654985111430, 515736895712230192, 29321225548502776980, 1768139644819077541440, 112805126206185257070660, 7595507651522103787077270, 538504704005397535690160274

Offset: 0

Author

Gus Wiseman, Jan 21 2024

Keywords

• nonn

Examples

			The term a(5) = 30 counts all permutations of the graph {{1,2},{1,3},{1,4},{2,3},{2,4}}.
		

Links

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

Crossrefs

The version without the choice condition is A116508, covering A367863.

The complement is A137916.

Allowing any number of edges gives A367867, covering A367868.

The version with loops is A368596, covering A368730, unlabeled A368835.

For set-systems we have A368600, for any number of edges A367903.

The covering case is A369144.

A006125 counts simple graphs, unlabeled A000088.

A058891 counts set-systems (without singletons A016031), unlabeled A000612.

Cf. A000085, A057500, A062740, A129271, A133686, A333331, A367769, A367869, A367901, A367907.

Programs

Mathematica

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

Formula

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

Extensions

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