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.

Links

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

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