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.

1, 4, 2304, 967458816, 913008685901414400, 4622106472375910400000000000000, 255573619105709190896159859671040000000000000000, 281792629748570725486109522755987396047015304495104000000000000000000, 10444688389799535672440661668710965357968392730721066975209656086980827545600000000000000000000

Offset: 1

Author

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

Keywords

• nonn
• easy

Comments

For these profiles both men-proposing and women-proposing Gale-Shapley algorithms end in one round.

This is a subsequence of A001013.

Examples

			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.
		

Links

• Wikipedia, Gale-Shapley algorithm.

Crossrefs

Cf. A001013, A185141, A343474, A343694, A342573, A340890.

Programs

Mathematica

Table[n!^2 (n - 1)!^(2 n), {n, 10}]

Formula

a(n) = n!^2 * (n-1)!^(2*n).

a(n) = A343694(n)^2.