A338665 a(n) is the number of preference profiles for n men and n women where every man prefers woman number 1 to woman number 2.

4, 5832, 6879707136, 19349176320000000000, 303256405652583481344000000000000, 53311087345695615264200592956011315200000000000000, 190584865366582887488321066784947980317795794157526056960000000000000000

Offset

2,1

Comments

This is also the number of preference profiles for n men and n women where every woman prefers man number 1 to man number 2.

When implementing the men-proposing Gale-Shapley algorithm on such a preference profile, woman number 1 gets her first engagement in an earlier round than woman number 2.

Links

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

Wikipedia, Gale-Shapley algorithm.

Formula

a(n) = n!^(2n) / 2^n.

Example

When n = 2, we have exactly 1 way to arrange each man's profiles such that woman number 1 is ranked before woman number 2. Each woman's profile can be set in 2! = 2 ways, so the total number of preference profiles such that every man prefers woman number 1 to woman number 2 is 1^2 * 2^2 = 4.

Mathematica

Table[n!^(2 n)/2^n, {n, 2, 10}]

Crossrefs

Cf. A001013, A185141, A342573, A340890, A343474, A343475.

Sequence in context: A046360 A367942 A079232 * A137045 A368807 A077258

Adjacent sequences: A338662 A338663 A338664 * A338666 A338667 A338668

Keyword

nonn

Author

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

Status

approved