|
%I #11 Feb 11 2022 12:13:17
%S 0,2,48,124416,9537454080,243184270049280000,
%T 1390396658530114967961600000,
%U 4352862027490648408300099378983469056000,11228731998377005106060609036300637077741992056717312000,36658843398022550531624696117934603340895735930389121945136191766528000000
%N 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 man and woman pairs who rank each other first.
%C 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 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/n! * Sum_{i=0...n} [(-1)^i * n!/i!] = A344664(n) * A000166(n).
%e 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 Cf. A002860, A185141, A343696, A343697, A344664.
%K nonn
%O 1,2
%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 22 2021
| 