The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 4, 4536, 5113774080 (list; graph; refs; listen; history; text; internal format)
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.
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 hell-couple 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
Sequence in context: A079682 A127235 A274972 * A344671 A203036 A306962
KEYWORD
nonn,more
AUTHOR
Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 02 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 09:54 EDT 2024. Contains 372620 sequences. (Running on oeis4.)