OFFSET
1,2
COMMENTS
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.
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.
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
Michael De Vlieger, Table of n, a(n) for n = 1..22
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.
Wikipedia, Gale-Shapley algorithm
FORMULA
a(n) = n!^(n+1) * (n-1)!^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
Tanya Khovanova and MIT PRIMES STEP Senior group, Apr 16 2021
STATUS
approved