|
|
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)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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).
|
|
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^4*(n-1)!^(2n) for n != 2; a(2) = 14.
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
{1, 14}~Join~Table[n^4 (n - 1)!^(2 n), {n, 3, 10}] (* corrected by Michael De Vlieger, Feb 11 2022 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|