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

Comments

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)

Links

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

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.

Formula

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

Example

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.

Crossrefs

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

Sequence in context: A108963 A152510 A324590 * A321633 A244550 A359952

Adjacent sequences: A344666 A344667 A344668 * A344670 A344671 A344672

Keyword

nonn,bref,more

Author

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

Extensions

a(5) from Dan Eilers, Dec 23 2023

Status

approved