login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005154 Number of stable matchings.
(Formerly M1992)
1
1, 2, 10, 268, 195472, 104310534400, 29722161121961969778688, 2413441860555924454205324333893477339897004032, 15913289476042091181119569948276231488639535067163704670852319029791565485433738366445158400 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Lower bound for maximal number of stable matchings (or marriages) possible with 2^n men and 2^n women for suitable preference ordering.

REFERENCES

D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, p. 25.

R. W. Irving and P. Leather, The complexity of counting stable marriages, SIAM J. Computing 15 (1986), 655-667. [The sequence is v_n =g(2^n), where g(n) appears on page p. 657.]

D. E. Knuth, Mariages Stables, Presses Univ. de Montreal, 1976 (gives 10 matchings illustrating a(2)).

J. C. Lagarias, J. H. Spencer and J. P. Vinson, Counting dyadic equipartitions of the unit square, Discrete Math. 257 (2002), 481-499. (Sequence is mentioned on fourth page.)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

E. G. Thurber, Concerning the maximum number of stable matchings ..., Discrete Math., 248 (2002), 195-219 (see Eq. (1)).

LINKS

Table of n, a(n) for n=0..8.

FORMULA

a_0 = 1, a_1 = 2; a_n = 3*a_{n-1}^2 - 2*a_{n-2}^4.

MAPLE

A005154 := proc(n) option remember; if n <= 1 then n+1 else 3*A005154(n-1)^2-2*A005154(n-2)^4; fi; end;

MATHEMATICA

RecurrenceTable[{a[0]==1, a[1]==2, a[n]==3a[n-1]^2-2a[n-2]^4}, a, {n, 8}] (* Harvey P. Dale, Mar 19 2012 *)

CROSSREFS

Sequence in context: A225371 A088310 A134473 * A074056 A206158 A144288

Adjacent sequences:  A005151 A005152 A005153 * A005155 A005156 A005157

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

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 December 18 09:25 EST 2018. Contains 318219 sequences. (Running on oeis4.)