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

Author

Dan Eilers, Sep 21 2022

Keywords

• nonn

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

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