

A344670


a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there exists a stable matching with one couple where both the man and the woman rank each other last.


1




OFFSET

1,2


COMMENTS

A man and a woman who rank each other last and end up in a marriage are called a hellcouple. A stable matching cannot have more than one hellcouple.
Given a profile, if there exists a stable matching with a hellcouple, then all the stable matchings for this profile have the same hellcouple.
The GaleShapley algorithm (both menproposing and womenproposing) for such a profile needs at least n rounds to terminate.


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 is a stable matching with a hellcouple if and only if the other two people rank each other first. Now, there are 2 ways to pair the men and women, and 2 ways to choose which couple has a man and woman ranking each other first, making a(2) = 2 * 2 = 4.


CROSSREFS



KEYWORD

nonn,more


AUTHOR



STATUS

approved



