login
A344668
a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate exactly 1 possible stable matching.
3
1, 14, 34080, 65867261184
OFFSET
1,2
COMMENTS
A069124(n) provides the lower bound for the maximum number of stable matchings with n men and n women. It is exact for n below 5.
LINKS
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.
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) = 14.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Tanya Khovanova and MIT PRIMES STEP Senior group, May 27 2021
STATUS
approved