cp's OEIS Frontend

A344665 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where both the men's preferences and women's preferences form a Latin square when arranged in a matrix, with no paired man and woman who rank each other first.

%I A344665 #21 Jun 01 2024 19:28:57
%S A344665 0,2,48,124416,9537454080,243184270049280000,
%T A344665 1390396658530114967961600000,
%U A344665 4352862027490648408300099378983469056000,11228731998377005106060609036300637077741992056717312000,36658843398022550531624696117934603340895735930389121945136191766528000000
%N A344665 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where both the men's preferences and women's preferences form a Latin square when arranged in a matrix, with no paired man and woman who rank each other first.
%C A344665 The profiles in this sequence are the intersection of the profiles in A343696 and A343697. The Gale-Shapley algorithm on such a set of preference profiles ends in one round.
%H A344665 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 A344665 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%F A344665 a(n) = A002860(n)^2 * Sum_{i=0..n} (-1)^i/i! = A344664(n) * A000166(n).
%e A344665 For n = 2, there are A002860(2) = 2 ways to set up the men's profiles. Since the women don't want to rank the man who ranked them first as first, there is exactly 1 way to set up the women's profiles. So, there are 2 * 1 = 2 preference profiles for n = 2.
%Y A344665 Cf. A002860, A185141, A343696, A343697, A344664.
%K A344665 nonn
%O A344665 1,2
%A A344665 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 22 2021