A368433 -id:A368433 - cp's OEIS frontend

A344669 a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate the maximum possible number of stable matchings.

1, 2, 1092, 144, 507254400

Offset: 1

Tanya Khovanova and MIT PRIMES STEP Senior group, May 27 2021

From Dan Eilers, Dec 23 2023: (Start)
A357271 provides the best known lower bounds for the maximum number of stable matchings of order n.
A357269 provides exact results. (End)

			For n=2, there are 16 possible preference profiles: 14 of them generate one stable matching and 2 of them generate two stable matchings. Thus, a(2) = 2.

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.

Cf. A069124, A185141, A344666, A344667, A344668, A357269, A357271, A368433.

a(n) = A368433(n) * A010790(n-1). - Dan Eilers, Dec 24 2023

a(5) from Dan Eilers, Dec 23 2023

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

Original entry on oeis.org

176130, 498320, 19193670, 143035180, 348655065

Offset: 0

Dan Eilers, Dec 23 2023

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

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.

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.

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

Cf. A357269, A351409, A344669, A368433.

cp's OEIS Frontend

A344669 a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate the maximum possible number of stable matchings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions