login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice. 4

%I #15 Feb 11 2022 11:52:26

%S 1,8,10368,10319560704,23776267862016000000,

%T 299512499409958993920000000000000,

%U 41761084325232750832975432403386368000000000000000,117254360528268768669572531322770730078331396796134195200000000000000000,11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000

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

%C 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 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 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 Michael De Vlieger, <a href="/A343475/b343475.txt">Table of n, a(n) for n = 1..22</a>

%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) = n!^(n+1) * (n-1)!^n.

%e 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 Table[n!^(n + 1) (n - 1)!^n, {n, 10}]

%Y Cf. A001013, A185141, A342573, A340890.

%K nonn

%O 1,2

%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Apr 16 2021

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 17:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)