A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice.

1, 8, 10368, 10319560704, 23776267862016000000, 299512499409958993920000000000000, 41761084325232750832975432403386368000000000000000, 117254360528268768669572531322770730078331396796134195200000000000000000, 11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000

Offset

1,2

Comments

This sequence is the number of preference profiles for the Stable Marriage Problem such that the male-proposing Gale-Shapley algorithm terminates in one iteration.

This is the same number of preference profiles as when all men rank the different women at the i-th place, where i can be anywhere from 1 to n.

Note this is the same as the number of preference profiles for n men and n women where the women prefer distinct men as their first choice.

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.

Wikipedia, Gale-Shapley algorithm

Formula

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

Example

When n = 3, there are 3! = 6 ways to order the women as first preferences for the men, 2!^3 = 8 ways to finish the mens' profiles, and then 3!^3 = 216 ways to complete the womens' profiles, making a total of 6 * 8 * 216 = 10368 preference profiles.

Mathematica

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

Crossrefs

Cf. A001013, A185141, A342573, A340890.

Sequence in context: A188890 A175881 A165429 * A242852 A079235 A134373

Adjacent sequences: A343472 A343473 A343474 * A343476 A343477 A343478

Keyword

nonn

Author

Tanya Khovanova and MIT PRIMES STEP Senior group, Apr 16 2021

Status

approved