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

0, 0, 1, 67, 30997

Offset

0,4

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

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

Wikipedia, Axiom of choice.

Formula

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

Example

The a(2) = 1 set-system is {{1},{2},{1,2}}.
The a(3) = 67 set-systems have following 21 non-isomorphic representatives:
  {{1},{2},{1,2}}
  {{1},{2},{3},{1,2}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,2},{1,3}}
  {{1},{2},{1,2},{1,2,3}}
  {{1},{2},{1,3},{2,3}}
  {{1},{2},{1,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3}}
  {{1},{1,2},{1,3},{1,2,3}}
  {{1},{1,2},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3}}
  {{1},{2},{3},{1,2},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3}}
  {{1},{2},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,3},{2,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Mathematica

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

Crossrefs

Multisets of multisets of this type are ranked by A355529.

The version without singletons is A367769.

The version for simple graphs is A367867, covering A367868.

The version allowing empty edges is A367901.

The complement is A367902, without singletons A367770, ranks A367906.

For a unique choice (instead of none) we have A367904, ranks A367908.

These set-systems have ranks A367907.

An unlabeled version is A368094, for multiset partitions A368097.

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, A368409, A368413.

Sequence in context: A144940 A211962 A263463 * A279798 A191941 A087536

Adjacent sequences: A367900 A367901 A367902 * A367904 A367905 A367906

Keyword

nonn,more

Author

Gus Wiseman, Dec 05 2023

Status

approved