A367772 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice in more than one way.

0, 0, 1, 23, 1105, 154941, 66072394, 88945612865, 396990456067403

Offset: 0

Author

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

			Non-isomorphic representatives of the a(3) = 23 set-systems:
  {{1,2}}
  {{1,2,3}}
  {{1},{2,3}}
  {{1},{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}
		

Links

• Wikipedia, Axiom of choice.

Crossrefs

For at least one choice we have A367902.

For no choices we have A367903, no singletons A367769, ranks A367907.

For a unique choice we have A367904, ranks A367908.

These set-systems have ranks A367909.

A000372 counts antichains, covering A006126, nonempty A014466.

A003465 counts covering set-systems, unlabeled A055621.

A058891 counts set-systems, unlabeled A000612.

Cf. A059201, A102896, A133686, A283877, A306445, A323818, A355741, A367770, A367862, A367869, A367901, A367905.

Programs

Mathematica

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

Formula

A367903(n) + A367904(n) + a(n) = A058891(n).

Extensions

a(5)-a(8) from Christian Sievers, Jul 26 2024