A367868 - OEIS

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

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

OFFSET

0,5

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.

LINKS

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

FORMULA

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

EXAMPLE

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

MATHEMATICA

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

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.

Sequence in context: A354026 A232454 A140638 * A372814 A299036 A374141

Adjacent sequences: A367865 A367866 A367867 * A367869 A367870 A367871

KEYWORD

nonn

AUTHOR

Gus Wiseman, Dec 08 2023

EXTENSIONS

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

STATUS

approved