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, 729, 429981696, 604661760000000000, 4738381338321616896000000000000, 416492869888246994251567132468838400000000000000, 744472130338214404251254167128703048116389820927836160000000000000000, 45414513879851870274245681660582356320629081347021328317938070440504213897216000000000000000000

Offset: 2

Author

Tanya Khovanova and MIT PRIMES STEP Senior group, May 24 2021

Keywords

• nonn

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.

Examples

			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.
		

Links

• Wikipedia, Gale-Shapley algorithm.

Crossrefs

Cf. A185141, A338665, A343474, A343692.

Programs

Mathematica

Table[n!^(2 n)/4^n, {n, 2, 10}]

Formula

a(n) = n!^(2*n) / 4^n.

a(n) = A338665(n)/2^n = A343692(n)^2.