|
|
A344665
|
|
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.
|
|
2
|
|
|
0, 2, 48, 124416, 9537454080, 243184270049280000, 1390396658530114967961600000, 4352862027490648408300099378983469056000, 11228731998377005106060609036300637077741992056717312000, 36658843398022550531624696117934603340895735930389121945136191766528000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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.
|
|
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
|
|
|
EXAMPLE
|
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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|