

A344664


a(n) is the number of preference profiles in the stable marriage problem with n men and n women where both the men's and the women's preferences form a Latin square when arranged in a matrix. In addition, it is possible to arrange all people into n manwoman couples such that they rank each other first.


2



1, 2, 24, 13824, 216760320, 917676490752000, 749944260264355430400000, 293457967200879687743551498616832000, 84112872283641495670736269523436185936222748672000, 27460610008848610956892895086773773421767179663217968124264448000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have n pairs of soulmates.
The profiles with n pairs of soulmates are counted by sequence A343698. The profiles such that the men's preferences form a Latin square are counted by A343696. The profiles such that both men's and women's preferences form a Latin square are counted by A343697. The profiles in this sequence are the intersection of profiles in A343698 and A343697.
Both the men and the womenproposing GaleShapley algorithm on the preference profiles described by this sequence end 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 = 3, there are A002860(3) = 12 Latin squares of order 3. Thus, there are A002860(3) = 12 ways to set up the men's preference profiles. After that, the women's preference profiles form a Latin square with a fixed first column, as the first column is uniquely defined to generate 3 pairs of soulmates. Thus, there are A002860(3)/3! = 12/6 = 2 ways to set up the women's preference profiles, making a(3) = 12 * 2 = 24 preference profiles.


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



