

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

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


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

Cf. A185141, A344671.
Sequence in context: A079682 A127235 A274972 * A344671 A203036 A306962
Adjacent sequences: A344667 A344668 A344669 * A344671 A344672 A344673


KEYWORD

nonn


AUTHOR

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


STATUS

approved



