cp's OEIS Frontend

A343696 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, such that the men's preference profiles form a Latin square.

%I A343696 #14 Feb 11 2022 11:52:31
%S A343696 1,8,2592,191102976,4013162496000000,113241608573209804800000000,
%T A343696 5078594244241245901264634511360000000000,
%U A343696 759796697672599288560347581750936194390876487680000000000,602809439070636186475532789128702956081602819845966698324215778508800000000000
%N A343696 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, such that the men's preference profiles form a Latin square.
%C A343696 Equivalently, these are the profiles where each woman is ranked differently by the n men.
%C A343696 Equivalently, for every rank i, there is exactly one woman who is ranked i by a given man.
%C A343696 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.
%C A343696 Due to symmetry, a(n) is the number of preference profiles in the stable marriage problem with n men and n women, such that the women’s preference profiles form a Latin square.
%H A343696 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 A343696 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
%F A343696 a(n) = n!^n * A002860(n).
%e A343696 For n = 3, there are 3!^3 ways to set up the women's preference profiles and A002860(3) ways to set up the men's preference profiles, where A002860(3) = 12 (there are 12 different Latin squares of order 3). Thus a(3) = 3!^3 * A002860(3) = 216 * 12 = 2592.
%Y A343696 Cf. A002860, A185141, A343697.
%K A343696 nonn
%O A343696 1,2
%A A343696 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 25 2021