%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 hellcouple. A stable matching cannot have more than one hellcouple.
%C Given a profile, if there exists a stable matching with a hellcouple, then all the stable matchings for this profile have the same hellcouple.
%C The GaleShapley algorithm (both menproposing and womenproposing) 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">GaleShapley algorithm</a>.
%e 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.
%Y Cf. A185141, A344671.
%K nonn,more
%O 1,2
%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 02 2021
