cp's OEIS Frontend

A344689 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that one man and one woman are ranked last by all the people of the opposite gender except each other.

%I A344689 #22 Feb 11 2022 12:33:32
%S A344689 1,14,5184,429981696,39627113103360000,11555266180939776000000000000,
%T A344689 24157228657754148059243505254400000000000000,
%U A344689 709983949983801273585561911705687568775548764160000000000000000,520402602329775972199889472492375107519949414596673059590723457777664000000000000000000
%N A344689 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that one man and one woman are ranked last by all the people of the opposite gender except each other.
%C A344689 The members of such a pair of people are called outcasts. The outcasts must be matched with each other in any stable matching independently of how they rank each other.
%C A344689 For n other than 2, there can be at most one pair of outcasts.
%C A344689 The number of profiles where the pair of outcasts exists and they rank each other last is A343474(n).
%H A344689 Michael De Vlieger, <a href="/A344689/b344689.txt">Table of n, a(n) for n = 1..23</a>
%H A344689 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 A344689 a(n) = n^4*(n-1)!^(2n) for n != 2; a(2) = 14.
%e A344689 Each person makes a ranking list for all members of the opposite gender without ties. The outcasts are ranked n-th (last) by at least n-1 persons of the opposite gender. This is why for n>2 at most one pair of outcasts can exist.
%e A344689 For n>2, we have n^2 ways to pick the two outcasts, then n!^2 ways to complete the outcasts' preference profiles, and finally (n-1)!^(2n-2) ways to complete everyone else's profiles.
%t A344689 {1, 14}~Join~Table[n^4 (n - 1)!^(2 n), {n, 3, 10}] (* corrected by _Michael De Vlieger_, Feb 11 2022 *)
%Y A344689 Cf. A185141, A343474.
%K A344689 nonn
%O A344689 1,2
%A A344689 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 30 2021