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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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;

Sequence in context: A001528 A088310 A134473 this_sequence A074056 A144288 A003047

Adjacent sequences: A005151 A005152 A005153 this_sequence A005155 A005156 A005157

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).