login
A343693
a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where every man prefers woman number 1 to woman number 2 and every woman prefers man number 1 to man number 2.
1
1, 729, 429981696, 604661760000000000, 4738381338321616896000000000000, 416492869888246994251567132468838400000000000000, 744472130338214404251254167128703048116389820927836160000000000000000, 45414513879851870274245681660582356320629081347021328317938070440504213897216000000000000000000
OFFSET
2,2
COMMENTS
When implementing the men-proposing Gale-Shapley algorithm on such a preference profile, woman number 1's first engagement comes in an earlier round than the first engagement of woman number 2. Similarly, when implementing the women-proposing Gale-Shapley algorithm on such a preference profile, man number 1's first engagement comes in an earlier round than the first engagement for man number 2.
FORMULA
a(n) = n!^(2*n) / 4^n.
a(n) = A338665(n)/2^n = A343692(n)^2.
EXAMPLE
When n = 2, each man and each woman have fixed preferences, so every person has exactly 1 way to set their personal preferences, yielding 1 total preference profile.
MATHEMATICA
Table[n!^(2 n)/4^n, {n, 2, 10}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Tanya Khovanova and MIT PRIMES STEP Senior group, May 24 2021
STATUS
approved