|
|
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 man-woman 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 women-proposing Gale-Shapley 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
|
|
|
|