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

1, 2, 10, 268, 195472, 104310534400, 29722161121961969778688, 2413441860555924454205324333893477339897004032, 15913289476042091181119569948276231488639535067163704670852319029791565485433738366445158400

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.

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, and 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, and 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 Computing, June 2018, pp. 920-925.

D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 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.

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

Formula and comment swapped by N. J. A. Sloane, Mar 01 2020

Status

approved