The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 men-proposing Gale-Shapley algorithm when used on these preference profiles will end in j rounds if the man in the non-soulmate pair ranks his partner as j-th. A similar statement is true for the women-proposing Gale-Shapley algorithm. LINKS Michael De Vlieger, Table of n, a(n) for n = 1..23 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. 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 Cf. A185141, A343698, A343700. Sequence in context: A107254 A345679 A012532 * A346717 A012732 A001322 Adjacent sequences: A343696 A343697 A343698 * A343700 A343701 A343702 KEYWORD nonn AUTHOR Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 21 02:30 EST 2024. Contains 370219 sequences. (Running on oeis4.)