A340890 a(n) is the number of preference profiles for n men and n women, where all men prefer the same woman.

1, 8, 5184, 1719926784, 990677827584000000, 2495937495082991616000000000000, 58001506007267709490243656115814400000000000000, 23264754073069200132851692722771970253637181903994880000000000000000

Offset

1,2

Comments

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

Note that we can swap men and women in the definition of the sequence.

The total number of possible profiles is A185141.

a(n) = n!^n A342573(n), where A342573 ignores women's preferences.

a(n) is a subsequence of A001013.

Links

Table of n, a(n) for n=1..8.

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(n-1)!^n * n!^n.

Example

When n=2, the total number of profiles is 16, and in half of them, the same woman is ranked 1st by both men.

Mathematica

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

Crossrefs

Cf. A001013, A185141, A342573.

Sequence in context: A055319 A029736 A206460 * A093937 A318897 A178329

Adjacent sequences: A340887 A340888 A340889 * A340891 A340892 A340893

Keyword

nonn

Author

Tanya Khovanova and MIT PRIMES STEP Senior group, Mar 31 2021

Status

approved