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

1, 1, 3, 32, 1201, 151286, 62453670, 84707326890, 384641855115279

Offset: 0

Author

Gus Wiseman, Jan 01 2024

Keywords

• nonn
• hard
• 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) = 3 set-systems:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
Non-isomorphic representatives of the a(3) = 32 set-systems:
  {{1},{2},{3}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{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 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 A367902, ranks A367906, no singletons A367770.

The complement is A368600, any length A367903 (see also A367907, A367769).

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, A367901, A367905, 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
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(a(n)) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

Formula

a(n) + A368600(n) = A136556(n).

Extensions

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

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