A357271 -id:A357271 - 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

A357269 Maximum number of stable matchings in the stable marriage problem of order n.

Original entry on oeis.org

1, 2, 3, 10, 16

Offset: 1

Dan Eilers, Sep 21 2022

Finding a(n) (denoted f(n) in the literature) is a research problem posed by Knuth in 1976 and reiterated by Gusfield and Irving in 1989.
a(5)=16 was found by Eilers using a MiniZinc constraint satisfaction model, showing previous lower bound of Eilers reported by Thurber to be exact.
A357271 gives lower bounds for a(n) reported by Thurber, previously known to be exact up to n=4, which is not to be confused with A069156 which gives looser lower bounds for n > 11.
Thurber proved a(n) to be strictly increasing.
There are 176130 reduced instances of order 5 with 16 stable matchings, and 498320 reduced instances with 15 stable matchings, compared with A351430 for order 4, and A369597 for order 3.
The total number of reduced instances for order n is A351409(n), which is 214990848000000000 for order 5, so about one in 1.22*10^12 such instances are maximal.
The maximum number of stable matchings for order 5, where the men's (or women's, respectively) ranking table is a latin square, is 14, with 300 such reduced instances, making order 5 the first order not containing any maximal instances where the men's ranking table is a Latin square.

C. Converse, Lower bounds for the maximum number of stable pairings for the general marriage problem based on the latin marriage problem, Ph. D. Thesis, Claremont Graduate School, Claremont, CA (1992).
D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.
D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, (Open Problem #1).

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).
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Cf. A357271 and A069156 (lower bound of 16 for a(5)).
Cf. A351430 (order 4), A369597 (order 3).
Cf. A351409 (total number of reduced instances).

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