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

Author

Geoffrey Critzer, Jul 10 2013

Keywords

• nonn
• more

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.

Examples

			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}).
		

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.
• Wikipedia, Hall's marriage theorem

Crossrefs

Cf. A002416, A088672, A089482, A089479.

Programs

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}]

Formula

a(n) = A002416(n) - A088672(n).

a(n) = Sum_{k=1..n!} A089479(n,k). - Geoffrey Critzer, Dec 20 2023

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