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


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A344689 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that one man and one woman are ranked last by all the people of the opposite gender except each other. 1
1, 14, 5184, 429981696, 39627113103360000, 11555266180939776000000000000, 24157228657754148059243505254400000000000000, 709983949983801273585561911705687568775548764160000000000000000, 520402602329775972199889472492375107519949414596673059590723457777664000000000000000000 (list; graph; refs; listen; history; text; internal format)



The members of such a pair of people are called outcasts. The outcasts must be matched with each other in any stable matching independently of how they rank each other.

For n other than 2, there can be at most one pair of outcasts.

The number of profiles where the pair of outcasts exists and they rank each other last is A343474(n).


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.


a(n) = n^4*(n-1)!^(2n) for n != 2; a(2) = 14.


Each person makes a ranking list for all members of the opposite gender without ties. The outcasts are ranked n-th (last) by at least n-1 persons of the opposite gender. This is why for n>2 at most one pair of outcasts can exist.

For n>2, we have n^2 ways to pick the two outcasts, then n!^2 ways to complete the outcasts' preference profiles, and finally (n-1)!^(2n-2) ways to complete everyone else's profiles.


{1, 14}~Join~Table[n^4 (n - 1)!^(2 n), {n, 3, 10}] (* corrected by Michael De Vlieger, Feb 11 2022 *)


Cf. A185141, A343474.

Sequence in context: A180588 A214441 A241326 * A159372 A060856 A030531

Adjacent sequences:  A344686 A344687 A344688 * A344690 A344691 A344692




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



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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 12:35 EDT 2022. Contains 355075 sequences. (Running on oeis4.)