A005154 a(0) = 1, a(1) = 2; thereafter a(n) = 3*a(n-1)^2 - 2*a(n-2)^4.
1, 2, 10, 268, 195472, 104310534400, 29722161121961969778688, 2413441860555924454205324333893477339897004032, 15913289476042091181119569948276231488639535067163704670852319029791565485433738366445158400
Offset: 0
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
- 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)).
Crossrefs
Recurrence is similar to A076725.
Programs
-
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
-
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 *)
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
Extensions
Formula and comment swapped by N. J. A. Sloane, Mar 01 2020
Comments