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

1, 2, 3, 10, 16, 48, 71, 268, 330, 1000, 1231, 6472, 6720, 20176, 25011, 195472, 200832, 456300, 637336, 3419680, 3506880, 11221136, 15481956, 126112960, 127885440, 262860800, 384418176, 2000043808

Offset

1,2

Comments

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.

Improved lower bounds for n=7, 9, 11, 13, 15 are shown in linked Ong et al. (2025) file.

Links

Table of n, a(n) for n=1..28.

Ryan Ong, Bethany Ang, Abigail Ho, Dan Eilers, Justin Marks, and Genti Buzi, Improved lower bounds for n=7, 9, 11, 13, 15, 2025.

Ryan Ong, Bethany Ang, Abigail Ho, Dan Eilers, Justin Marks, and Genti Buzi, Improved Hill Climbing for the Stable Marriage Problem IFoRE 2024 Poster (2024).

Peter J. Stuckey, Kim Marriott, and Guido Tack, The MiniZinc Handbook, Listing 2.2.12, stable-marriage.mzn, Version 2.9.2, 6 March 2025.

E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Crossrefs

Cf. A357269, A069156.

Sequence in context: A357269 A106672 A069156 * A060744 A213391 A328343

Adjacent sequences: A357268 A357269 A357270 * A357272 A357273 A357274

Keyword

nonn

Author

Dan Eilers, Sep 21 2022

Status

approved