cp's OEIS Frontend

A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice.

%I A343475 #15 Feb 11 2022 11:52:26
%S A343475 1,8,10368,10319560704,23776267862016000000,
%T A343475 299512499409958993920000000000000,
%U A343475 41761084325232750832975432403386368000000000000000,117254360528268768669572531322770730078331396796134195200000000000000000,11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000
%N A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice.
%C A343475 This sequence is the number of preference profiles for the Stable Marriage Problem such that the male-proposing Gale-Shapley algorithm terminates in one iteration.
%C A343475 This is the same number of preference profiles as when all men rank the different women at the i-th place, where i can be anywhere from 1 to n.
%C A343475 Note this is the same as the number of preference profiles for n men and n women where the women prefer distinct men as their first choice.
%H A343475 Michael De Vlieger, <a href="/A343475/b343475.txt">Table of n, a(n) for n = 1..22</a>
%H A343475 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 A343475 Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>
%F A343475 a(n) = n!^(n+1) * (n-1)!^n.
%e A343475 When n = 3, there are 3! = 6 ways to order the women as first preferences for the men, 2!^3 = 8 ways to finish the mens' profiles, and then 3!^3 = 216 ways to complete the womens' profiles, making a total of 6 * 8 * 216 = 10368 preference profiles.
%t A343475 Table[n!^(n + 1) (n - 1)!^n, {n, 10}]
%Y A343475 Cf. A001013, A185141, A342573, A340890.
%K A343475 nonn
%O A343475 1,2
%A A343475 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Apr 16 2021