|
%I M1992 #50 Oct 27 2023 08:21:07
%S 1,2,10,268,195472,104310534400,29722161121961969778688,
%T 2413441860555924454205324333893477339897004032,
%U 15913289476042091181119569948276231488639535067163704670852319029791565485433738366445158400
%N a(0) = 1, a(1) = 2; thereafter a(n) = 3*a(n-1)^2 - 2*a(n-2)^4.
%C A lower bound for maximal number of stable matchings (or marriages) possible with 2^n men and 2^n women for suitable preference ordering.
%D D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, p. 25.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H R. W. Irving and P. Leather, <a href="https://doi.org/10.1137/0215048">The complexity of counting stable marriages</a>, SIAM J. Computing 15 (1986), 655-667. [The sequence is v_n =g(2^n), where g(n) appears on page p. 657.]
%H Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber, <a href="https://arxiv.org/abs/1711.01032">A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings</a>, arXiv:1711.01032 [cs.DM], 2017.
%H Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber, <a href="https://doi.org/10.1145/3188745.3188848">A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings</a>, STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, June 2018, pp. 920-925.
%H D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/ms.html">Mariages Stables</a>, Presses Univ. de Montréal, 1976 (gives 10 matchings illustrating a(2)).
%H J. C. Lagarias, J. H. Spencer and J. P. Vinson, <a href="https://doi.org/10.1016/S0012-365X(02)00508-3">Counting dyadic equipartitions of the unit square</a>, Discrete Math. 257 (2002), 481-499.
%H Clayton Thomas, <a href="/A005154/a005154.pdf">A recurrence giving a lower bound for stable matchings</a> (analysis of the asymptotic behavior of a_n, with proof due to Peter Shor)
%H E. G. Thurber, <a href="https://doi.org/10.1016/S0012-365X(01)00194-7">Concerning the maximum number of stable matchings in the stable marriage problem</a>, Discrete Math., 248 (2002), 195-219 (see Eq. (1)).
%F a(n) ~ r*s^(2^n), where r = (sqrt(3)-1)/2 = 0.366025... and s = 2.28014... . - _Clayton Thomas_, Aug 09 2019
%F The Karlin, Gharan, Weber upper bound is C^(2^n) for a large C. - _Domotor Palvolgyi_, Feb 09 2020
%p A005154 := proc(n) option remember; if n <= 1 then n+1 else 3*A005154(n-1)^2-2*A005154(n-2)^4; fi; end;
%t 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 *)
%o (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
%Y Recurrence is similar to A076725.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
%E Formula and comment swapped by _N. J. A. Sloane_, Mar 01 2020
| 