cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

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.

Original entry on oeis.org

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

Views

Author

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

Keywords

Comments

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.

Examples

			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.

Links

  • 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.

Crossrefs

Cf. A185141, A342573, A340890.

Programs

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

Formula

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

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

Original entry on oeis.org

1, 8, 5184, 1719926784, 990677827584000000, 2495937495082991616000000000000, 58001506007267709490243656115814400000000000000, 23264754073069200132851692722771970253637181903994880000000000000000
Offset: 1

Views

Author

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

Keywords

Comments

This is the same number of preference profiles as when all men rank the same woman at the i-th place, where i can be anywhere from 1 to n.
Note that we can swap men and women in the definition of the sequence.
The total number of possible profiles is A185141.
a(n) = n!^n A342573(n), where A342573 ignores women's preferences.
a(n) is a subsequence of A001013.

Examples

			When n=2, the total number of profiles is 16, and in half of them, the same woman is ranked 1st by both men.

Links

  • 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.

Crossrefs

Cf. A001013, A185141, A342573.

Programs

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

Formula

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

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

Views

Author

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

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

Cf. A001013, A185141, A342573, A340890.

Programs

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

Formula

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

Views

Author

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

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

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

Programs

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

Formula

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

Views

Author

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

Keywords

Comments

For these profiles both men-proposing and women-proposing Gale-Shapley algorithms end in one round.
This is a subsequence of A001013.

Examples

			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.

Links

Crossrefs

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

Programs

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

Formula

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

Views

Author

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

Keywords

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.

Examples

			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.

Links

Crossrefs

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

Programs

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

Formula

a(n) = n!^(2n) / 2^n.
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.