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

 

Logo


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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 18:26 EDT 2018. Contains 315240 sequences. (Running on oeis4.)