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!)
A005154 a(0) = 1, a(1) = 2; thereafter a(n) = 3*a(n-1)^2 - 2*a(n-2)^4.
(Formerly M1992)
2
1, 2, 10, 268, 195472, 104310534400, 29722161121961969778688, 2413441860555924454205324333893477339897004032, 15913289476042091181119569948276231488639535067163704670852319029791565485433738366445158400 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber, A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings, arXiv:1711.01032 [cs.DM], 2017.

Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber, A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings, STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingJune 2018 Pages 920-925.

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(n) ~ r*s^(2^n), where r = (sqrt(3)-1)/2 = 0.366025... and s = 2.28014... . - Clayton Thomas, Aug 09 2019

The Karlin, Gharan, Weber upper bound is C^(2^n) for a large C. - Domotor Palvolgyi, Feb 09 2020

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 is similar to A076725.

Sequence in context: A225371 A088310 A134473 * A074056 A206158 A144288

Adjacent sequences:  A005151 A005152 A005153 * A005155 A005156 A005157

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Swapped formula and comment. - N. J. A. Sloane, Mar 01 2020

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 30 16:16 EDT 2020. Contains 333127 sequences. (Running on oeis4.)