A367902 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice.

1, 2, 7, 61, 1771, 187223, 70038280, 90111497503, 397783376192189

Offset: 0

Author

Gus Wiseman, Dec 05 2023

Keywords

• nonn
• more

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(2) = 7 set-systems:
  {}
  {{1}}
  {{2}}
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
		

Links

• Wikipedia, Axiom of choice.

Crossrefs

The version for simple graphs is A133686, covering A367869.

The version without singletons is A367770.

The complement allowing empty edges is A367901.

The complement is A367903, without singletons A367769, ranks A367907.

For a unique choice we have A367904, ranks A367908.

These set-systems have ranks A367906.

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.

A326031 gives weight of the set-system with BII-number n.

Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367862, A367905, A370636.

Programs

Mathematica

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

Formula

a(n) = A370636(2^n-1). - Alois P. Heinz, Mar 09 2024

Extensions

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