

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



1, 8, 10368, 10319560704, 23776267862016000000, 299512499409958993920000000000000, 41761084325232750832975432403386368000000000000000, 117254360528268768669572531322770730078331396796134195200000000000000000, 11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This sequence is the number of preference profiles for the Stable Marriage Problem such that the maleproposing GaleShapley algorithm terminates in one iteration.
This is the same number of preference profiles as when all men rank the different women at the ith place, where i can be anywhere from 1 to n.
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.


LINKS

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.


FORMULA

a(n) = n!^(n+1) * (n1)!^n.


EXAMPLE

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.


MATHEMATICA

Table[n!^(n + 1) (n  1)!^n, {n, 10}]


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



