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,1

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

Table of n, a(n) for n=0..4.

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.

Sequence in context: A224650 A262822 A273727 * A203406 A280447 A205177

Adjacent sequences: A368416 A368417 A368418 * A368420 A368421 A368422

Keyword

nonn,more,fini

Author

Dan Eilers, Dec 23 2023

Status

approved