cp's OEIS Frontend

A357271 Lower bounds for the maximum number of stable matchings in the stable marriage problem based on composing smaller instances.

%I A357271 #23 May 26 2025 15:56:20
%S A357271 1,2,3,10,16,48,71,268,330,1000,1231,6472,6720,20176,25011,195472,
%T A357271 200832,456300,637336,3419680,3506880,11221136,15481956,126112960,
%U A357271 127885440,262860800,384418176,2000043808
%N A357271 Lower bounds for the maximum number of stable matchings in the stable marriage problem based on composing smaller instances.
%C A357271 a(n) is from Appendix C of Thurber's 2002 paper, using the maximum from each row. At the time of publication, the bounds were known to be exact up to n=4. A357269 shows that they are also exact for n=5. This sequence is not to be confused with A069156, also from Thurber's Appendix C, which uses only the first column, making for looser bounds for n > 11. a(6), a(8), a(10), a(12), and a(16) are also conjectured to be exact.
%C A357271 Improved lower bounds for n=7, 9, 11, 13, 15 are shown in linked Ong et al. (2025) file.
%H A357271 Ryan Ong, Bethany Ang, Abigail Ho, Dan Eilers, Justin Marks, and Genti Buzi, <a href="/A357271/a357271_1.txt">Improved lower bounds for n=7, 9, 11, 13, 15</a>, 2025.
%H A357271 Ryan Ong, Bethany Ang, Abigail Ho, Dan Eilers, Justin Marks, and Genti Buzi, <a href="https://www.jstor.org/stable/community.39515645">Improved Hill Climbing for the Stable Marriage Problem</a> IFoRE 2024 Poster (2024).
%H A357271 Peter J. Stuckey, Kim Marriott, and Guido Tack, <a href="https://docs.minizinc.dev/en/stable/modelling2.html#array-access-constraints">The MiniZinc Handbook, Listing 2.2.12, stable-marriage.mzn</a>, Version 2.9.2, 6 March 2025.
%H A357271 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.
%Y A357271 Cf. A357269, A069156.
%K A357271 nonn
%O A357271 1,2
%A A357271 _Dan Eilers_, Sep 21 2022