

A343697


a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that both the men's and women's profiles form Latin squares.


5



1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, 11832225237539469009819996424230666240000, 30522879094287825948996777484664523152536511038095360000, 99649061600109839440372937690884668992908741561885362729330828902400000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Equivalently, these are the profiles where each woman is ranked differently by the n men and each man is ranked differently by the women.
The menproposing GaleShapley algorithm on such a set of preferences ends in one round, since every woman receives one proposal in the first round. Similarly, the womenproposing GaleShapley algorithm 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

There are 12 Latin squares of order 3, where 12 = A002860(3). Thus, for n = 3, there are A002860(3) ways to set up the men's profiles and A002860(3) ways to set up the women's profiles, making A002860(3)^2 = 144 ways to set up all the preference profiles.


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



