cp's OEIS Frontend

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

%I A343700 #21 Jan 20 2023 09:03:57
%S A343700 0,2,9984,28419102720,175302739963548794880,
%T A343700 5801674463718565478400000000000000,
%U A343700 2113937863028052653298578438638220083200000000000000,15500609395854457241550377325238753195602871153217230602240000000000000000
%N A343700 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are no pairs of people who rank each other first.
%C A343700 Two people who rank each other first are called soulmates. Thus, this sequence enumerates the profiles without soulmates.
%C A343700 This sequence is in contrast to the sequence A343698 which enumerates profiles with n pairs of soulmates.
%C A343700 The preference profiles with the most stable matchings do not have soulmates.
%H A343700 Michael De Vlieger, <a href="/A343700/b343700.txt">Table of n, a(n) for n = 1..22</a>
%H A343700 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.
%F A343700 a(n) = Sum_{i = 0..n} ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2i) * i! * n!^(2n - 2i)).
%F A343700 a(n) = A350558(n)*A284458(n). - _Dan Eilers_, Jan 17 2023
%e A343700 For n=2, suppose A and B are the men and C and D are the women, then the only two possibilities are the following: a) A prefers C, C prefers B, B prefers D, and D prefers A; 2) A prefers D, D prefers B, B prefers C, and C prefers A.
%t A343700 Table[Total[
%t A343700   Table[(-1)^i Binomial[n, i]^2 (n - 1)!^(2 i) i! n!^(2 n - 2 i), {i,
%t A343700     0, n}]], {n, 10}]
%o A343700 (PARI) a(n) = sum(i=0, n, ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2*i) * i! * n!^(2*n - 2*i))); \\ _Michel Marcus_, Jan 20 2023
%Y A343700 Cf. A185141, A343698, A343699, A350558, A284458.
%K A343700 nonn
%O A343700 1,2
%A A343700 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 26 2021