cp's OEIS Frontend

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.

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