|
|
A005154
|
|
a(0) = 1, a(1) = 2; thereafter a(n) = 3*a(n-1)^2 - 2*a(n-2)^4.
(Formerly M1992)
|
|
4
|
|
|
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 1976 (gives 10 matchings illustrating a(2)).
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|