cp's OEIS Frontend

A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).

%I A343699 #10 Feb 11 2022 11:52:39
%S A343699 0,12,9216,2418647040,913008685901414400,
%T A343699 1348114387776307200000000000000,
%U A343699 17038241273713946059743990644736000000000000000,3522407871857134068576369034449842450587691306188800000000000000000
%N A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).
%C A343699 Such profiles have exactly one stable matching, where soulmates are married to each other.
%C A343699 The men-proposing Gale-Shapley algorithm when used on these preference profiles will end in j rounds if the man in the non-soulmate pair ranks his partner as j-th. A similar statement is true for the women-proposing Gale-Shapley algorithm.
%H A343699 Michael De Vlieger, <a href="/A343699/b343699.txt">Table of n, a(n) for n = 1..23</a>
%H A343699 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 A343699 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%F A343699 a(n) = (n - 1)!^(2n + 1) * n^2 * (n^2 - 1).
%e A343699 When n = 2, there are 2 ways to pick the man in the soulmate pair and 2 ways to pick the woman in the soulmate pair. After this, the soulmate's preference profiles are fixed. There are 4 ways to complete the profiles for the other two people, but 1 of the ways creates a second pair of soulmates, which is forbidden. Thus, there are 12 profiles with exactly one pair of soulmates.
%t A343699 Table[(n - 1)!^(2 n + 1) n^2 (n^2 - 1), {n, 10}]
%Y A343699 Cf. A185141, A343698, A343700.
%K A343699 nonn
%O A343699 1,2
%A A343699 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 26 2021