A367867 Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.

0, 0, 0, 0, 7, 416, 24244, 1951352, 265517333, 68652859502, 35182667175398, 36028748718835272, 73786974794973865449, 302231454853009287213496, 2475880078568912926825399800, 40564819207303268441662426947840, 1329227995784915869870199216532048487

Offset: 0

Author

Gus Wiseman, Dec 07 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.

In the connected case, these are just graphs with more than one cycle.

Examples

			Non-isomorphic representatives of the a(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,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 complement is A133686, connected A129271, covering A367869.

The connected case is A140638 (graphs with more than one cycle).

The covering case is A367868.

For set-systems we have A367903, ranks A367907.

A001187 counts connected graphs, A001349 unlabeled.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

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

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

A143543 counts simple labeled graphs by number of connected components.

Cf. A057500, A116508, A326754, A355739, A355740, A367769, A367770, A367863, A367901, A367902, A367904.

Programs

Mathematica

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

Formula

a(n) = A006125(n) - A133686(n). - Andrew Howroyd, Dec 30 2023

Extensions

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