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)
2
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.

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

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

LINKS

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

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

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

Clayton Thomas, A recurrence giving a lower bound for stable matchings (analysis of the asymptotic behavior of a_n, with proof due to Peter Shor)

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

FORMULA

a(0) = 1, a(1) = 2; a(n) = 3*a(n-1)^2 - 2*a(n-2)^4.

a(n) ~ r*s^(2^n), where r = (sqrt(3)-1)/2 = 0.366025... and s = 2.28014... . - Clayton Thomas, Aug 09 2019

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 *)

PROG

(MAGMA) I:=[1, 2]; [m le 2 select I[m] else 3*Self(m-1)^2-2*Self(m-2)^4: m in [1..9]]; // Marius A. Burtea, Aug 09 2019

CROSSREFS

Recurrence similar to A076725.

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 October 19 16:08 EDT 2019. Contains 328223 sequences. (Running on oeis4.)