

A227414


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


0




OFFSET

1,2


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=1..7.
Alexander Postnikov, Permutohedra, associahedra, and beyond, 2005, arXiv:math/0507163 [math.CO], 2005.
Wikipedia, Hall's marriage theorem


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

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


STATUS

approved



