cp's OEIS Frontend

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.

%I A368600 #16 Jul 25 2024 19:06:30
%S A368600 0,0,0,3,164,18625,5491851,4649088885,12219849683346
%N 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.
%C A368600 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.
%H A368600 Wikipedia, <a href="https://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of choice</a>.
%F A368600 a(n) = A136556(n) - A368601(n).
%e A368600 The a(3) = 3 set-systems:
%e A368600   {{1},{2},{1,2}}
%e A368600   {{1},{3},{1,3}}
%e A368600   {{2},{3},{2,3}}
%t A368600 Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]==0&]],{n,0,3}]
%o A368600 (Python)
%o A368600 from itertools import combinations, product, chain
%o A368600 from scipy.special import comb
%o A368600 def v(c):
%o A368600     for elements in product(*c):
%o A368600         if len(set(elements)) == len(elements):
%o A368600             return True
%o A368600     return False
%o A368600 def a(n):
%o A368600     if n == 0:
%o A368600         return 1
%o A368600     subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
%o A368600     cs = combinations(subsets, n)
%o A368600     c = sum(1 for c in cs if v(c))
%o A368600     return c
%o A368600 [print(int(comb(2**n-1,n) - a(n))) for n in range(7)] # _Robert P. P. McKone_, Jan 02 2024
%Y A368600 For a unique choice we have A003024, any length A367904 (ranks A367908).
%Y A368600 Sets of n nonempty subsets of {1..n} are counted by A136556.
%Y A368600 For any length we have A367903, ranks A367907, no singletons A367769.
%Y A368600 The complement is A368601, any length A367902 (see also A367770, A367906).
%Y A368600 A000372 counts antichains, covering A006126, nonempty A014466.
%Y A368600 A003465 counts covering set-systems, unlabeled A055621.
%Y A368600 A058891 counts set-systems, unlabeled A000612.
%Y A368600 A059201 counts covering T_0 set-systems.
%Y A368600 A323818 counts covering connected set-systems, unlabeled A323819.
%Y A368600 Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367868, A367901, A368094, A368097.
%K A368600 nonn,more
%O A368600 0,4
%A A368600 _Gus Wiseman_, Jan 01 2024
%E A368600 a(6) from _Robert P. P. McKone_, Jan 02 2024
%E A368600 a(7)-a(8) from _Christian Sievers_, Jul 25 2024