cp's OEIS Frontend

A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.

%I A227414 #51 Dec 20 2023 19:08:52
%S A227414 1,1,7,247,37823,23191071,54812742655,494828369491583
%N A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.
%C A227414 In a group of n women and n men, each woman selects a subset of men that she would happily marry.  Hall's marriage problem gives the conditions on the subsets so that every woman can become happily married.
%C A227414 a(n)/2^(n^2) is the probability that if the subsets are selected at random then all the women can be happy.
%C A227414 Equivalently, a(n) is the number of n x n {0,1} matrices such that if in any arbitrarily selected r rows we note the columns that have at least one 1 in the selected rows then the number of such columns must not be less than r.
%H A227414 F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, <a href="https://arxiv.org/abs/2012.10323">Minimal generating sets for matrix monoids</a>, arXiv:2012.10323 [math.RA], 2020, p. 2.
%H A227414 Alexander Postnikov, <a href="http://arxiv.org/abs/math/0507163">Permutohedra, associahedra, and beyond</a>, 2005, arXiv:math/0507163 [math.CO], 2005.
%H A227414 Stefan Schwarz, <a href="https://dml.cz/handle/10338.dmlcz/101153">The semigroup of fully indecomposable relations and Hall relations</a>, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
%H A227414 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem">Hall's marriage theorem</a>
%F A227414 a(n) = A002416(n) - A088672(n).
%F A227414 a(n) = Sum_{k=1..n!} A089479(n,k). - _Geoffrey Critzer_, Dec 20 2023
%e A227414 a(2) = 7 because we have:
%e A227414 1: ({1}, {2});
%e A227414 2: ({1}, {1,2});
%e A227414 3: ({2}, {1});
%e A227414 4: ({2}, {1,2});
%e A227414 5: ({1,2}, {1});
%e A227414 6: ({1,2}, {2});
%e A227414 7: ({1,2}, {1,2}).
%t A227414 f[list_]:=Apply[And,Flatten[Table[Map[Length[#]>=n&,Map[Apply[Union,#]&, Subsets[list,{n}]]],{n,1,Length[list]}]]]; Table[Total[Boole[Map[f, Tuples[Subsets[n],n]]]],{n,1,4}]
%Y A227414 Cf. A002416, A088672, A089482, A089479.
%K A227414 nonn,more
%O A227414 0,3
%A A227414 _Geoffrey Critzer_, Jul 10 2013
%E A227414 a(5) from _James Mitchell_, Nov 13 2015
%E A227414 a(6) from _James Mitchell_, Nov 16 2015
%E A227414 a(7) from _Noam Zeilberger_, Jun 04 2019
%E A227414 a(0)=1 prepended by _Alois P. Heinz_, Dec 19 2023