|
| |
|
|
A343695
|
|
a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where men prefer different women and women prefer different men as their first choices.
|
|
3
|
|
|
|
1, 4, 2304, 967458816, 913008685901414400, 4622106472375910400000000000000, 255573619105709190896159859671040000000000000000, 281792629748570725486109522755987396047015304495104000000000000000000, 10444688389799535672440661668710965357968392730721066975209656086980827545600000000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For these profiles both men-proposing and women-proposing Gale-Shapley algorithms end in one round.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = n!^2 * (n-1)!^(2n).
|
|
|
EXAMPLE
|
When n = 3, there are 3! ways for men to pick their first choices and 2!^3 ways to complete their lists of preferences. The same calculation works for women's preferences. As the preferences of different genders are independent, we have a total of 3!^2 * 2!^6 = 2304 such preference profiles for n = 3.
|
|
|
MATHEMATICA
|
Table[n!^2 (n - 1)!^(2 n), {n, 10}].
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
