The OEIS is supported by the many generous donors to the OEIS Foundation.


(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)



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.


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

Wikipedia, Gale-Shapley algorithm.


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.


Cf. A185141, A344671.

Sequence in context: A079682 A127235 A274972 * A344671 A203036 A306962

Adjacent sequences:  A344667 A344668 A344669 * A344671 A344672 A344673




Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 02 2021



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 19:00 EST 2022. Contains 350572 sequences. (Running on oeis4.)