login
A227414
Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem.
5
1, 1, 7, 247, 37823, 23191071, 54812742655, 494828369491583
OFFSET
0,3
COMMENTS
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.
a(n)/2^(n^2) is the probability that if the subsets are selected at random then all the women can be happy.
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.
LINKS
F. Hivert, J. D. Mitchell, F. L. Smith, and W. A. Wilson, Minimal generating sets for matrix monoids, arXiv:2012.10323 [math.RA], 2020, p. 2.
Alexander Postnikov, Permutohedra, associahedra, and beyond, 2005, arXiv:math/0507163 [math.CO], 2005.
Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
FORMULA
a(n) = A002416(n) - A088672(n).
a(n) = Sum_{k=1..n!} A089479(n,k). - Geoffrey Critzer, Dec 20 2023
EXAMPLE
a(2) = 7 because we have:
1: ({1}, {2});
2: ({1}, {1,2});
3: ({2}, {1});
4: ({2}, {1,2});
5: ({1,2}, {1});
6: ({1,2}, {2});
7: ({1,2}, {1,2}).
MATHEMATICA
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}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Geoffrey Critzer, Jul 10 2013
EXTENSIONS
a(5) from James Mitchell, Nov 13 2015
a(6) from James Mitchell, Nov 16 2015
a(7) from Noam Zeilberger, Jun 04 2019
a(0)=1 prepended by Alois P. Heinz, Dec 19 2023
STATUS
approved