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

Author

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

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Cf. A001013, A185141, A342573.

Programs

Mathematica

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

Formula

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