cp's OEIS Frontend

A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).

%I A343698 #8 Feb 11 2022 11:52:35
%S A343698 1,2,384,40310784,7608405715845120,6419592322744320000000000000,
%T A343698 50709051409862934701619019776000000000000000,
%U A343698 6988904507653043786857875068352862005134308147200000000000000000
%N A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).
%C A343698 For such profiles, each person has exactly one valid partner: their soulmate. Consequently, there is only one stable matching: where the soulmates are married to each other.
%C A343698 For these profiles, the Gale-Shapley algorithm, whether it is men-proposing or women proposing, ends in one round.
%C A343698 This is a subsequence of A001013.
%H A343698 Michael De Vlieger, <a href="/A343698/b343698.txt">Table of n, a(n) for n = 1..23</a>
%H A343698 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 A343698 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%F A343698 a(n) = (n - 1)!^(2n) * n!.
%e A343698 For n = 3, there are 3! = 6 ways to pair the men and women into soulmate pairs, then 2! ways to finish each person's preference profile, making 6 * 2!^6 = 384 ways to set up the preference profiles.
%t A343698 Table[(n - 1)!^(2 n) n!, {n, 10}]
%Y A343698 Cf. A001013, A185141, A343699, A343700.
%K A343698 nonn
%O A343698 1,2
%A A343698 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 26 2021