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-5 of 5 results.

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

Original entry on oeis.org

1, 2, 1092, 144, 507254400
Offset: 1

Views

Author

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

Keywords

Comments

From Dan Eilers, Dec 23 2023: (Start)
A357271 provides the best known lower bounds for the maximum number of stable matchings of order n.
A357269 provides exact results. (End)

Examples

			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) = 2.

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. A069124, A185141, A344666, A344667, A344668, A357269, A357271, A368433.

Formula

a(n) = A368433(n) * A010790(n-1). - Dan Eilers, Dec 24 2023

Extensions

a(5) from Dan Eilers, Dec 23 2023

A351430 a(n) is the number of reduced stable marriage problem instances of order 4 that generate n possible stable matchings.

Original entry on oeis.org

457411536, 249495038, 50719534, 5983183, 774164, 24157, 4038, 253, 0, 1
Offset: 1

Views

Author

Dan Eilers, Feb 11 2022

Keywords

Comments

A344667(10) is reduced from 144 to 1, demonstrating that it is a unique maximal instance up to relabeling of the participants.

Crossrefs

Cf. A344667, A351409, A010790.

Formula

a(n) = A344667(n)/A010790(3) as described in A351409.

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

Views

Author

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

Keywords

Comments

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

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

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

Views

Author

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

Keywords

Comments

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.

Examples

			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.

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

A369597 a(n) is the number of reduced stable marriage problem instances of order 3 that generate n possible stable matchings.

Original entry on oeis.org

2840, 957, 91
Offset: 1

Views

Author

Dan Eilers, Jan 27 2024

Keywords

Crossrefs

Cf. A351430 (order 4, reduced), A368419 (order 5, reduced).
Cf. A344666 (order 3 unreduced), A344667 (order 4 unreduced).
Cf. A351409 (number of reduced instances of order n).
Cf. A010790 (reduction factor for order n).
Showing 1-5 of 5 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.