cp's OEIS Frontend

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.

%I A344671 #13 Jan 15 2023 09:37:28
%S A344671 1,4,4608,5317484544
%N 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.
%C A344671 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 A344671 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 A344671 The Gale-Shapley algorithm (both men-proposing and women-proposing) for such a profile needs at least n rounds to terminate.
%C A344671 A344670(n) is the number of preference profiles such that there exists a stable matching with a hell-couple.
%C A344671 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 A344671 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 A344671 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%e A344671 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 A344671 Cf. A185141, A344670.
%K A344671 nonn,more
%O A344671 1,2
%A A344671 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 05 2021