login
This site is supported by donations to The OEIS 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 (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..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

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 March 20 05:29 EDT 2019. Contains 321344 sequences. (Running on oeis4.)