A344663 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where the men's preferences form a Latin square when arranged in a matrix, and no man and woman rank each other first.

0, 2, 768, 60466176, 1315033086689280, 37924385587200000000000000, 1726298879786383239996474654720000000000, 261072919520121696668385285116754694244904468480000000000, 208836950100011929062766575947297434628338701720339215752571230617600000000000, 1378135848291144955393621267341374054991268978878673434553714544944450408726397427961036800000000000000

Offset: 1

Author

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

Keywords

• nonn

Comments

This sequence is in contrast to A344662: a(n) is the number of preference profiles in the stable marriage problem with n men and n women so that they form n pairs of people of different genders who rank each other first, and so that the men's preferences form a Latin square when arranged in a matrix.

Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have no soulmate pairs.

The number of profiles without soulmates is counted by sequence A343700. The number of profiles such that the men's preferences form a Latin square is counted by A343696. The profiles in this sequence are the intersection of profiles in A343696 and A343700.

The men-proposing Gale-Shapley algorithm on the preference profiles described by this sequence ends in one round.

Examples

			For n = 3, there are A002860(3) = 12 ways to set up the men's preference profiles, where A002860(n) is the number of Latin squares of order n. Then, since the women can't rank the men who ranked them first as their first preference, there are 2^3 = 8 ways to set up the women's first preferences, and then 2!^3 = 8 ways to finish the women's profiles. So, A344663(3) = 12 * 8 * 8 = 768 preference profiles.
		

Links

• Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.
• Wikipedia, Gale-Shapley algorithm.

Crossrefs

Cf. A002860, A185141, A343696, A344662, A343700.

Formula

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