A338665 -id:A338665 - cp's OEIS frontend

A343692 a(n) is the number of men's preference profiles in the stable marriage problem with n men and n women, where every man prefers woman number 1 to woman number 2.

1, 27, 20736, 777600000, 2176782336000000, 645362587921121280000000, 27285016590396539545426329600000000, 213106813311662727500673631554480635904000000000, 386661002072680852777222237092449665784217600000000000000000000

Offset: 2

Tanya Khovanova and MIT PRIMES STEP Senior group, May 23 2021

nonn

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

This is the same as the number of women's preference profiles in the stable marriage problem with n men and n women, where every woman prefers man number 1 to man number 2.

			When n = 2, there is exactly 1 way for each man's profile to be completed such that woman number 1 is before woman number 2. Since we are only looking at men's profiles, this means there are 1^n = 1^2 = 1 preference profiles such that every man prefers woman number 1 to woman number 2.

Wikipedia, Gale-Shapley algorithm.

Cf. A185141, A338665, A343474, A343693.

Mathematica
```
Table[n!^n/2^n, {n, 2, 10}]
```

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

a(n) = A338665(n)/n!^(n) = sqrt(A343693(n)).

A343693 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where every man prefers woman number 1 to woman number 2 and every woman prefers man number 1 to man number 2.

Original entry on oeis.org

1, 729, 429981696, 604661760000000000, 4738381338321616896000000000000, 416492869888246994251567132468838400000000000000, 744472130338214404251254167128703048116389820927836160000000000000000, 45414513879851870274245681660582356320629081347021328317938070440504213897216000000000000000000

Offset: 2

Tanya Khovanova and MIT PRIMES STEP Senior group, May 24 2021

nonn

When implementing the men-proposing Gale-Shapley algorithm on such a preference profile, woman number 1's first engagement comes in an earlier round than the first engagement of woman number 2. Similarly, when implementing the women-proposing Gale-Shapley algorithm on such a preference profile, man number 1's first engagement comes in an earlier round than the first engagement for man number 2.

			When n = 2, each man and each woman have fixed preferences, so every person has exactly 1 way to set their personal preferences, yielding 1 total preference profile.

Wikipedia, Gale-Shapley algorithm.

Cf. A185141, A338665, A343474, A343692.

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

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

a(n) = A338665(n)/2^n = A343692(n)^2.

cp's OEIS Frontend

A343692 a(n) is the number of men's preference profiles in the stable marriage problem with n men and n women, where every man prefers woman number 1 to woman number 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula