

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..6.
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


STATUS

approved



