A343700 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are no pairs of people who rank each other first.

0, 2, 9984, 28419102720, 175302739963548794880, 5801674463718565478400000000000000, 2113937863028052653298578438638220083200000000000000, 15500609395854457241550377325238753195602871153217230602240000000000000000

Offset: 1

Author

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

Keywords

• nonn

Comments

Two people who rank each other first are called soulmates. Thus, this sequence enumerates the profiles without soulmates.

This sequence is in contrast to the sequence A343698 which enumerates profiles with n pairs of soulmates.

The preference profiles with the most stable matchings do not have soulmates.

Examples

			For n=2, suppose A and B are the men and C and D are the women, then the only two possibilities are the following: a) A prefers C, C prefers B, B prefers D, and D prefers A; 2) A prefers D, D prefers B, B prefers C, and C prefers A.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..22
• 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.

Crossrefs

Cf. A185141, A343698, A343699, A350558, A284458.

Programs

Mathematica

Table[Total[
  Table[(-1)^i Binomial[n, i]^2 (n - 1)!^(2 i) i! n!^(2 n - 2 i), {i,
    0, n}]], {n, 10}]

PARI

a(n) = sum(i=0, n, ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2*i) * i! * n!^(2*n - 2*i))); \\ Michel Marcus, Jan 20 2023

Formula

a(n) = Sum_{i = 0..n} ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2i) * i! * n!^(2n - 2i)).

a(n) = A350558(n)*A284458(n). - Dan Eilers, Jan 17 2023