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)).
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