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

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

Table of n, a(n) for n=0..7.

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.

Wikipedia, Hall's marriage theorem

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

Cf. A002416, A088672, A089482, A089479.

Sequence in context: A296377 A223630 A203158 * A203698 A229482 A193371

Adjacent sequences: A227411 A227412 A227413 * A227415 A227416 A227417

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