A185141 -id:A185141 - cp's OEIS frontend

A343697 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that both the men's and women's profiles form Latin squares.

1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, 11832225237539469009819996424230666240000, 30522879094287825948996777484664523152536511038095360000, 99649061600109839440372937690884668992908741561885362729330828902400000000

Offset: 1

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

nonn

Equivalently, these are the profiles where each woman is ranked differently by the n men and each man is ranked differently by the women.

The men-proposing Gale-Shapley algorithm on such a set of preferences ends in one round, since every woman receives one proposal in the first round. Similarly, the women-proposing Gale-Shapley algorithm ends in one round.

			There are 12 Latin squares of order 3, where 12 = A002860(3). Thus, for n = 3, there are A002860(3) ways to set up the men's profiles and A002860(3) ways to set up the women's profiles, making A002860(3)^2 = 144 ways to set up all the 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.
Wikipedia, Gale-Shapley algorithm.

Cf. A002860, A185141, A343696.

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

A344667 a(n) is the number of preference profiles in the stable marriage problem with 4 men and 4 women that generate n possible stable matchings.

Original entry on oeis.org

65867261184, 35927285472, 7303612896, 861578352, 111479616, 3478608, 581472, 36432, 0, 144

Offset: 1

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

A185141(n) is the total number of preference profiles for n men and n women.
A185141(4) = 110075314176 is the sum of the terms of this sequence.
For 2 men and 2 women, the total number of preference profiles is 16, where 14 profiles have 1 stable matching, and 2 profiles have 2 stable matchings.
For 3 men and 3 women, the total number of preference profiles is 46656, where the number of possible stable matchings ranges from 1 to 3. The distribution is provided by sequence A344666(n).

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, A344666, A344668, A344669.

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.

A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).

Original entry on oeis.org

0, 12, 9216, 2418647040, 913008685901414400, 1348114387776307200000000000000, 17038241273713946059743990644736000000000000000, 3522407871857134068576369034449842450587691306188800000000000000000

Offset: 1

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

nonn

Such profiles have exactly one stable matching, where soulmates are married to each other.

The men-proposing Gale-Shapley algorithm when used on these preference profiles will end in j rounds if the man in the non-soulmate pair ranks his partner as j-th. A similar statement is true for the women-proposing Gale-Shapley algorithm.

			When n = 2, there are 2 ways to pick the man in the soulmate pair and 2 ways to pick the woman in the soulmate pair. After this, the soulmate's preference profiles are fixed. There are 4 ways to complete the profiles for the other two people, but 1 of the ways creates a second pair of soulmates, which is forbidden. Thus, there are 12 profiles with exactly one pair of soulmates.

Michael De Vlieger, Table of n, a(n) for n = 1..23
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. A185141, A343698, A343700.

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

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

A344666 a(n) is the number of preference profiles in the stable marriage problem with 3 men and 3 women that generate n possible stable matchings.

Original entry on oeis.org

34080, 11484, 1092

Offset: 1

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

A185141(n) is the total number of preference profiles for n men and n women.
A185141(3) = 46656 is the sum of the terms of this sequence.
For 2 men and 2 women, the total number of preference profiles is 16, where 14 profiles have 1 stable matching, and 2 profiles have 2 stable matchings.
For 4 men and 4 women, the total number of preference profiles is 110075314176, where the number of possible stable matchings ranges from 1 to 10, excluding 9. The distribution is provided by sequence A344667(n).

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, A344667, A344668, A344669.

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.

A344663 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where the men's preferences form a Latin square when arranged in a matrix, and no man and woman rank each other first.

Original entry on oeis.org

0, 2, 768, 60466176, 1315033086689280, 37924385587200000000000000, 1726298879786383239996474654720000000000, 261072919520121696668385285116754694244904468480000000000, 208836950100011929062766575947297434628338701720339215752571230617600000000000, 1378135848291144955393621267341374054991268978878673434553714544944450408726397427961036800000000000000

Offset: 1

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

nonn

This sequence is in contrast to A344662: a(n) is the number of preference profiles in the stable marriage problem with n men and n women so that they form n pairs of people of different genders who rank each other first, and so that the men's preferences form a Latin square when arranged in a matrix.
Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have no soulmate pairs.
The number of profiles without soulmates is counted by sequence A343700. The number of profiles such that the men's preferences form a Latin square is counted by A343696. The profiles in this sequence are the intersection of profiles in A343696 and A343700.
The men-proposing Gale-Shapley algorithm on the preference profiles described by this sequence ends in one round.

			For n = 3, there are A002860(3) = 12 ways to set up the men's preference profiles, where A002860(n) is the number of Latin squares of order n. Then, since the women can't rank the men who ranked them first as their first preference, there are 2^3 = 8 ways to set up the women's first preferences, and then 2!^3 = 8 ways to finish the women's profiles. So, A344663(3) = 12 * 8 * 8 = 768 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.
Wikipedia, Gale-Shapley algorithm.

Cf. A002860, A185141, A343696, A344662, A343700.

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

A344668 a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate exactly 1 possible stable matching.

Original entry on oeis.org

1, 14, 34080, 65867261184

Offset: 1

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

A069124(n) provides the lower bound for the maximum number of stable matchings with n men and n women. It is exact for n below 5.

			For n=2, there are 16 possible preference profiles: 14 of them generate one stable matching and 2 of them generate two stable matchings. Thus, a(2) = 14.

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. A069124, A185141, A344666, A344667, A344669.

A254866 a(n) = (n!!)^n.

Original entry on oeis.org

1, 1, 4, 27, 4096, 759375, 12230590464, 140710042265625, 472769874482845188096, 601016336033894136931640625, 697127546117424200558837760000000000, 153133225508583375568553948649382367138671875, 91653624689233987245068783089656480594395136000000000000

Offset: 0

Vaclav Kotesovec, Feb 19 2015

Eric Weisstein, Double Factorial, (MathWorld)

Cf. A006882, A036740, A185141.

Cf. A000165, A001147.

Mathematica
```
Table[(n!!)^n, {n, 0, 15}]
```

a(n) ~ Pi^(n/2) * n^(n*(n+1)/2) / exp(n^2/2 - 1/6) if n is even.

a(n) ~ 2^(n/2) * n^(n*(n+1)/2) / exp(n^2/2 - 1/6) if n is odd.

cp's OEIS Frontend

A343697 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that both the men's and women's profiles form Latin squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A344667 a(n) is the number of preference profiles in the stable marriage problem with 4 men and 4 women that generate n possible stable matchings.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A344666 a(n) is the number of preference profiles in the stable marriage problem with 3 men and 3 women that generate n possible stable matchings.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A344663 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where the men's preferences form a Latin square when arranged in a matrix, and no man and woman rank each other first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A344668 a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate exactly 1 possible stable matching.

Views

Author