|
%I #10 Feb 11 2022 11:52:44
%S 1,4,144,331776,26011238400,660727073341440000,
%T 3779719071732351369216000000,
%U 11832225237539469009819996424230666240000,30522879094287825948996777484664523152536511038095360000,99649061600109839440372937690884668992908741561885362729330828902400000000
%N a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that both the men's and women's profiles form Latin squares.
%C Equivalently, these are the profiles where each woman is ranked differently by the n men and each man is ranked differently by the women.
%C The men-proposing Gale-Shapley algorithm on such a set of preferences ends in one round, since every woman receives one proposal in the first round. Similarly, the women-proposing Gale-Shapley algorithm ends in one round.
%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%F a(n) = A002860(n)^2.
%e There are 12 Latin squares of order 3, where 12 = A002860(3). Thus, for n = 3, there are A002860(3) ways to set up the men's profiles and A002860(3) ways to set up the women's profiles, making A002860(3)^2 = 144 ways to set up all the preference profiles.
%Y Cf. A002860, A185141, A343696.
%K nonn
%O 1,2
%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 26 2021
| 