A342573 The number of ordered n-tuples consisting of n permutations (not necessarily distinct) such that the first element of each of them is the same.

1, 2, 24, 5184, 39813120, 17915904000000, 702142910300160000000, 3330690501757390081228800000000, 2534703826002712645182542460223488000000000, 395940866122425193243875570782668457763038822400000000000

Offset

1,2

Comments

This is related to the stable marriage problem, as this counts the preference profiles for n men trying to marry n women when all of them prefer the same woman.

This sequence also counts the sets of n permutations of size n such that the i-th element of each of them is the same.

a(n) is a subsequence of A001013: products of factorial numbers.

Links

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

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

Example

When n=3, we have 3 ways to fix the first element, and the remaining elements in each permutation can be in any order, yielding (3 - 1)! possible ways of ordering the rest of each permutation, so there are 3 * (2!)^3 = 24 sets of permutations.

Mathematica

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

Crossrefs

Cf. A001013, A091868.

Sequence in context: A159907 A242484 A088912 * A203465 A055462 A088600

Adjacent sequences: A342570 A342571 A342572 * A342574 A342575 A342576

Keyword

nonn

Author

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

Status

approved