login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A227414 Number of ordered n-tuples of subsets of {1,2,...,n} which satisfy the conditions in Hall's Marriage Problem. 0
1, 7, 247, 37823, 23191071, 54812742655, 494828369491583 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 3 20:41 EDT 2020. Contains 335418 sequences. (Running on oeis4.)