A340890 -id:A340890 - cp's OEIS frontend

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

1, 4, 576, 26873856, 1585084524134400, 320979616137216000000000000, 493004666484778531821296025600000000000000, 11093499218496894899774404870401368262117949440000000000000000

Offset: 1

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

nonn

Every preference profile of this type has exactly one pair of people who rank each other first.
This is the same number of preference profiles as when all men rank the same woman at only the i-th place, and all women rank the same man at only the j-th place, where i and j can be anywhere from 1 to n.
The total number of possible profiles is A185141.

			When n=2, there are 4 ways to pick a man and woman who are preferred by all people of the opposite gender, and then 1 way to fill in each of the remaining slots in every person's preference profile.  So, there are 4 different preference profiles.

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.

Cf. A185141, A342573, A340890.

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

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

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

A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice.

Original entry on oeis.org

1, 8, 10368, 10319560704, 23776267862016000000, 299512499409958993920000000000000, 41761084325232750832975432403386368000000000000000, 117254360528268768669572531322770730078331396796134195200000000000000000, 11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000

Offset: 1

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

nonn

This sequence is the number of preference profiles for the Stable Marriage Problem such that the male-proposing Gale-Shapley algorithm terminates in one iteration.
This is the same number of preference profiles as when all men rank the different women at the i-th place, where i can be anywhere from 1 to n.
Note this is the same as the number of preference profiles for n men and n women where the women prefer distinct men as their first choice.

			When n = 3, there are 3! = 6 ways to order the women as first preferences for the men, 2!^3 = 8 ways to finish the mens' profiles, and then 3!^3 = 216 ways to complete the womens' profiles, making a total of 6 * 8 * 216 = 10368 preference profiles.

Michael De Vlieger, Table of n, a(n) for n = 1..22
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.
Wikipedia, Gale-Shapley algorithm

Cf. A001013, A185141, A342573, A340890.

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

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

A343694 a(n) is the number of men's preference profiles in the stable marriage problem with n men and n women, such that all men prefer different women as their first choices.

Original entry on oeis.org

1, 2, 48, 31104, 955514880, 2149908480000000, 505542895416115200000000, 16786680128857246009393152000000000, 102199258264429373853760111996211036160000000000, 143679021498505654124337567125614729953051527872512000000000000

Offset: 1

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

nonn

For such a preference profile, the men-proposing Gale-Shapley algorithm ends in one round since each woman receives exactly one proposal in the first round.

This sequence also counts the preference profiles for n men who rank n women such that all men prefer different women as their i-th choice, for an i between 1 and n, inclusive.

			For n=2, there are two ways to pick men's first preferences, and then one way to complete the preference profile, making a total of 2 preference profiles.

Wikipedia, Gale-Shapley algorithm.

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

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

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

A343695 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where men prefer different women and women prefer different men as their first choices.

Original entry on oeis.org

1, 4, 2304, 967458816, 913008685901414400, 4622106472375910400000000000000, 255573619105709190896159859671040000000000000000, 281792629748570725486109522755987396047015304495104000000000000000000, 10444688389799535672440661668710965357968392730721066975209656086980827545600000000000000000000

Offset: 1

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

For these profiles both men-proposing and women-proposing Gale-Shapley algorithms end in one round.

This is a subsequence of A001013.

			When n = 3, there are 3! ways for men to pick their first choices and 2!^3 ways to complete their lists of preferences. The same calculation works for women's preferences. As the preferences of different genders are independent, we have a total of 3!^2 * 2!^6 = 2304 such preference profiles for n = 3.

Wikipedia, Gale-Shapley algorithm.

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

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

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

a(n) = A343694(n)^2.

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.

Original entry on oeis.org

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

Offset: 2

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

nonn

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.

			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.

Wikipedia, Gale-Shapley algorithm.

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A343694 a(n) is the number of men's preference profiles in the stable marriage problem with n men and n women, such that all men prefer different women as their first choices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A343695 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where men prefer different women and women prefer different men as their first choices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula