0,2

Lower bound for maximal number of stable matchings (or marriages) possible with 2^n men and 2^n women for suitable preference ordering.

D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, p. 25.

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

D. E. Knuth, Mariages Stables, Presses Univ. de Montreal, 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. (Sequence is mentioned on fourth page.)

E. G. Thurber, Concerning the maximum number of stable matchings ..., Discrete Math., 248 (2002), 195-219 (see Eq. (1)).

a_0 = 1, a_1 = 2; a_n = 3*a_{n-1}^2 - 2*a_{n-2}^4.

A005154 := proc(n) option remember; if n <= 1 then n+1 else 3*A005154(n-1)^2-2*A005154(n-2)^4; fi; end;

Adjacent sequences: A005151 A005152 A005153 this_sequence A005155 A005156 A005157

Sequence in context: A001528 A088310 A134473 this_sequence A074056 A003047 A028580

nonn,easy,nice

njas