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!)
A344671 a(n) is the total number of stable matchings for all possible preference profiles in the stable marriage problem with n men and n women such that there exists a married couple where the woman and the man rank each other last. 1

%I #13 Jan 15 2023 09:37:28

%S 1,4,4608,5317484544

%N a(n) is the total number of stable matchings for all possible preference profiles in the stable marriage problem with n men and n women such that there exists a married couple where the woman and the man rank each other last.

%C 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.

%C 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.

%C The Gale-Shapley algorithm (both men-proposing and women-proposing) for such a profile needs at least n rounds to terminate.

%C A344670(n) is the number of preference profiles such that there exists a stable matching with a hell-couple.

%C 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.

%H Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, <a href="https://arxiv.org/abs/2201.00645">Sequences of the Stable Matching Problem</a>, arXiv:2201.00645 [math.HO], 2021.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.

%e For n = 2, each preference profile that has a hell-couple has exactly one stable matching, thus a(2) = A344670(2) = 4. For n > 2, this is no longer the case and a(n) > A344670(n).

%Y Cf. A185141, A344670.

%K nonn,more

%O 1,2

%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 05 2021

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 June 17 18:36 EDT 2024. Contains 373463 sequences. (Running on oeis4.)