VOOZH about

URL: https://oeis.org/A343700

⇱ A343700 - OEIS

login
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.
7
0, 2, 9984, 28419102720, 175302739963548794880, 5801674463718565478400000000000000, 2113937863028052653298578438638220083200000000000000, 15500609395854457241550377325238753195602871153217230602240000000000000000
OFFSET
1,2
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.
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.
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
EXAMPLE
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.
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}]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021
STATUS
approved