OFFSET
1,2
COMMENTS
A man and a woman who rank each other last and end up in a marriage are called a hell-couple. A stable matching cannot have more than one hell-couple.
Given a profile, if there exists a stable matching with a hell-couple, then all the stable matchings for this profile have the same hell-couple.
The Gale-Shapley algorithm (both men-proposing and women-proposing) for such a profile needs at least n rounds to terminate.
A344670(n) is the number of preference profiles such that there exists a stable matching with a hell-couple.
This sequence is distinct from A344670 because in this sequence profiles are counted with their respective multiplicity if they yield multiple stable matchings with a hell-couple.
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.
Wikipedia, Gale-Shapley algorithm.
EXAMPLE
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 05 2021
STATUS
approved