

A343699


a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n  1 pairs of soulmates (people who rank each other first).


4



0, 12, 9216, 2418647040, 913008685901414400, 1348114387776307200000000000000, 17038241273713946059743990644736000000000000000, 3522407871857134068576369034449842450587691306188800000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Such profiles have exactly one stable matching, where soulmates are married to each other.
The menproposing GaleShapley algorithm when used on these preference profiles will end in j rounds if the man in the nonsoulmate pair ranks his partner as jth. A similar statement is true for the womenproposing GaleShapley algorithm.


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.


FORMULA

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


EXAMPLE

When n = 2, there are 2 ways to pick the man in the soulmate pair and 2 ways to pick the woman in the soulmate pair. After this, the soulmate's preference profiles are fixed. There are 4 ways to complete the profiles for the other two people, but 1 of the ways creates a second pair of soulmates, which is forbidden. Thus, there are 12 profiles with exactly one pair of soulmates.


MATHEMATICA

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


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



