A367868 Number of labeled simple graphs covering n vertices and contradicting a strict version of the axiom of choice.

0, 0, 0, 0, 7, 381, 21853, 1790135, 250562543, 66331467215, 34507857686001, 35645472109753873, 73356936892660012513, 301275024409580265134121, 2471655539736293803311467943, 40527712706903494712385171632959, 1328579255614092966328511889576785109

Offset: 0

Author

Gus Wiseman, Dec 08 2023

Keywords

• nonn

Comments

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

Examples

			The a(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{3,4}}
  {{1,2},{1,3},{1,4},{2,4},{3,4}}
  {{1,2},{1,3},{2,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{2,4},{3,4}}
  {{1,3},{1,4},{2,3},{2,4},{3,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
		

Links

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

Crossrefs

The connected case is A140638, unlabeled A140636.

The non-covering case is A367867.

The complement is A367869, connected A129271, non-covering A133686.

The version for set-systems is A367903, ranks A367907.

A001187 counts connected graphs, A001349 unlabeled.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

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

A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.

A143543 counts simple labeled graphs by number of connected components.

Cf. A057500, A116508, A367769, A367770, A367863, A367901, A367902, A367904.

Programs

Mathematica

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

Formula

a(n) = A006129(n) - A367869(n). - Andrew Howroyd, Dec 30 2023

Extensions

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023