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, 4649088885, 12219849683346

Offset: 0

Author

Gus Wiseman, Jan 01 2024

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

Links

• Wikipedia, Axiom of choice.

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.

Programs

Mathematica

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

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

Formula

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

Extensions

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

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