login
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
OFFSET
1,2
COMMENTS
For these profiles both men-proposing and women-proposing Gale-Shapley algorithms end in one round.
This is a subsequence of A001013.
FORMULA
a(n) = n!^2 * (n-1)!^(2n).
a(n) = A343694(n)^2.
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
Tanya Khovanova and MIT PRIMES STEP Senior group, May 25 2021
STATUS
approved