A368419 a(n) is the number of reduced stable marriage problem instances of order 5 that generate 16 - n possible stable matchings.

176130, 498320, 19193670, 143035180, 348655065

Offset: 0

Author

Dan Eilers, Dec 23 2023

Keywords

• nonn
• more
• fini

Comments

"Reduced" instances are counted, as in A351430 for order 4.

Reduced instances are fewer than all instances by a factor of n!(n-1)! due to participant-renaming isomorphism, analogous to reduced latin squares.

The counts are listed in reverse order from A351430 so that the known terms appear first. The first term gives the number of maximal instances (with 16 stable matchings, per A357269).

The total number of reduced instances for order 5 is 214990848000000000, given by A351409(5).

The corresponding sequence for order 3 is [91,957,2840], with 91 maximal instances.

a(0) = A368433(5) = A344669(5) / (5! * 4!).

Results were obtained using the MiniZinc constraint modeling language, by extending the "Model for the Stable Marriage Problem" given in the MiniZinc Handbook, Section 2.2.6.

The first two terms were obtained on a PC with 12GB RAM; the next three terms on a PC with 64GB RAM.

References

• D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.
• Dr Jason Wilson, Director, Biola Quantitative Consulting Center, "Stable Marriage Problem Project Report", crediting team of Annika Miller, Henry Lin, and Joseph Liu; December 22, 2023.

Links

• A. T. Benjamin, C. Converse, and H. A. Krieger, Note. How do I marry thee? Let me count the ways, Discrete Appl. Math. 59 (1995) 285-292.
• Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021, [Section 5, Distribution for the number of stable matchings].
• D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 1976 (Research Problem #5).
• David F. Manlove, Algorithmics of Matching Under Preferences, World Scientific (2013) [Section 2.2.2].
• E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Crossrefs

Cf. A351430 (order 4, in reverse order).

Cf. A357269, A351409, A344669, A368433.