A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

0, 0, 0, 3, 164, 18625, 5491851

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..6.

Wikipedia, Axiom of choice.

Formula

a(n) = A136556(n) - A368601(n).

Example

The a(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

Mathematica

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

Prog

(Python)
from itertools import combinations, product, chain
from scipy.special import comb
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(int(comb(2**n-1, n) - a(n))) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

Crossrefs

For a unique choice we have A003024, any length A367904 (ranks A367908).

Sets of n nonempty subsets of {1..n} are counted by A136556.

For any length we have A367903, ranks A367907, no singletons A367769.

The complement is A368601, any length A367902 (see also A367770, 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, unlabeled A323819.

Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367868, A367901, A368094, A368097.

Sequence in context: A364302 A212845 A212806 * A030258 A154737 A285488

Adjacent sequences: A368597 A368598 A368599 * A368601 A368602 A368603

Keyword

nonn,more

Author

Gus Wiseman, Jan 01 2024

Extensions

a(6) from Robert P. P. McKone, Jan 02 2024

Status

approved