A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

0, 0, 0, 1, 1490, 67027582, 144115188036455750, 1329227995784915872903806998967001298, 226156424291633194186662080095093570025917938800079226639565284090686126876

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.

Includes all set-systems with more edges than covered vertices, but this condition is not sufficient.

Links

Table of n, a(n) for n=0..8.

Wikipedia, Axiom of choice.

Formula

a(n) = 2^(2^n-n-1) - A367770(n) = A016031(n+1) - A367770(n). - Christian Sievers, Jul 28 2024

Example

The a(3) = 1 set-system is: {{1,2},{1,3},{2,3},{1,2,3}}.

Mathematica

Table[Length[Select[Subsets[Select[Subsets[Range[n]], Length[#]>1&]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 3}]

Crossrefs

Set-systems without singletons are counted by A016031, covering A323816.

The complement is A367770, with singletons allowed A367902 (ranks A367906).

The version for simple graphs is A367867, covering A367868.

The version allowing singletons and empty edges is A367901.

The version allowing singletons is A367903, ranks A367907.

A000372 counts antichains, covering A006126, nonempty A014466.

A003465 counts covering set-systems, unlabeled A055621.

A058891 counts set-systems, unlabeled A000612.

A059201 counts covering T_0 set-systems.

A323818 counts covering connected set-systems.

Cf. A007716, A092918, A102896, A283877, A306445, A326031, A355739, A355740, A355741, A367904, A367905.

Sequence in context: A028515 A288727 A137705 * A171617 A067841 A237968

Adjacent sequences: A367766 A367767 A367768 * A367770 A367771 A367772

Keyword

nonn,more

Author

Gus Wiseman, Dec 05 2023

Extensions

a(6)-a(8) from Christian Sievers, Jul 28 2024

Status

approved