login
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

%I #14 Jan 15 2023 09:37:35

%S 1,4,4536,5113774080

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

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

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

%Y Cf. A185141, A344671.

%K nonn,more

%O 1,2

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