|
| |
|
|
A343698
|
|
a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).
|
|
8
|
|
|
|
1, 2, 384, 40310784, 7608405715845120, 6419592322744320000000000000, 50709051409862934701619019776000000000000000, 6988904507653043786857875068352862005134308147200000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For such profiles, each person has exactly one valid partner: their soulmate. Consequently, there is only one stable matching: where the soulmates are married to each other.
For these profiles, the Gale-Shapley algorithm, whether it is men-proposing or women proposing, 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
|
a(n) = (n - 1)!^(2n) * n!.
|
|
|
EXAMPLE
|
For n = 3, there are 3! = 6 ways to pair the men and women into soulmate pairs, then 2! ways to finish each person's preference profile, making 6 * 2!^6 = 384 ways to set up the preference profiles.
|
|
|
MATHEMATICA
|
Table[(n - 1)!^(2 n) n!, {n, 10}]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
