A351409 -id:A351409 - cp's OEIS frontend

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

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

Offset: 1

Dan Eilers, Feb 11 2022

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

Cf. A344667, A351409, A010790.

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

A357269 Maximum number of stable matchings in the stable marriage problem of order n.

Original entry on oeis.org

1, 2, 3, 10, 16

Offset: 1

Dan Eilers, Sep 21 2022

Finding a(n) (denoted f(n) in the literature) is a research problem posed by Knuth in 1976 and reiterated by Gusfield and Irving in 1989.
a(5)=16 was found by Eilers using a MiniZinc constraint satisfaction model, showing previous lower bound of Eilers reported by Thurber to be exact.
A357271 gives lower bounds for a(n) reported by Thurber, previously known to be exact up to n=4, which is not to be confused with A069156 which gives looser lower bounds for n > 11.
Thurber proved a(n) to be strictly increasing.
There are 176130 reduced instances of order 5 with 16 stable matchings, and 498320 reduced instances with 15 stable matchings, compared with A351430 for order 4, and A369597 for order 3.
The total number of reduced instances for order n is A351409(n), which is 214990848000000000 for order 5, so about one in 1.22*10^12 such instances are maximal.
The maximum number of stable matchings for order 5, where the men's (or women's, respectively) ranking table is a latin square, is 14, with 300 such reduced instances, making order 5 the first order not containing any maximal instances where the men's ranking table is a Latin square.

C. Converse, Lower bounds for the maximum number of stable pairings for the general marriage problem based on the latin marriage problem, Ph. D. Thesis, Claremont Graduate School, Claremont, CA (1992).
D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.
D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, (Open Problem #1).

A. T. Benjamin, C. Converse, and H. A. Krieger, Note. How do I marry thee? Let me count the ways, Discrete Appl. Math. 59 (1995) 285-292.
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, [Section 5, Distribution for the number of stable matchings].
D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 1976 (Research Problem #5).
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Cf. A357271 and A069156 (lower bound of 16 for a(5)).
Cf. A351430 (order 4), A369597 (order 3).
Cf. A351409 (total number of reduced instances).

A368419 a(n) is the number of reduced stable marriage problem instances of order 5 that generate 16 - n possible stable matchings.

Original entry on oeis.org

176130, 498320, 19193670, 143035180, 348655065

Offset: 0

Dan Eilers, Dec 23 2023

"Reduced" instances are counted, as in A351430 for order 4.
Reduced instances are fewer than all instances by a factor of n!(n-1)! due to participant-renaming isomorphism, analogous to reduced latin squares.
The counts are listed in reverse order from A351430 so that the known terms appear first.  The first term gives the number of maximal instances (with 16 stable matchings, per A357269).
The total number of reduced instances for order 5 is 214990848000000000, given by A351409(5).
The corresponding sequence for order 3 is [91,957,2840], with 91 maximal instances.
a(0) = A368433(5) = A344669(5) / (5! * 4!).
Results were obtained using the MiniZinc constraint modeling language, by extending the "Model for the Stable Marriage Problem" given in the MiniZinc Handbook, Section 2.2.6.
The first two terms were obtained on a PC with 12GB RAM; the next three terms on a PC with 64GB RAM.

D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.
Dr Jason Wilson, Director, Biola Quantitative Consulting Center, "Stable Marriage Problem Project Report", crediting team of Annika Miller, Henry Lin, and Joseph Liu; December 22, 2023.

A. T. Benjamin, C. Converse, and H. A. Krieger, Note. How do I marry thee? Let me count the ways, Discrete Appl. Math. 59 (1995) 285-292.
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, [Section 5, Distribution for the number of stable matchings].
D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 1976 (Research Problem #5).
David F. Manlove, Algorithmics of Matching Under Preferences, World Scientific (2013) [Section 2.2.2].
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Cf. A351430 (order 4, in reverse order).

Cf. A357269, A351409, A344669, A368433.

A368433 a(n) is the number of reduced instances in the stable marriage problem of order n that generate the maximum possible number of stable matchings.

Original entry on oeis.org

1, 1, 91, 1, 176130

Offset: 1

Dan Eilers, Dec 24 2023

Reduced instances (A351409) are fewer than all instances by a factor of n!(n-1)! due to participant-renaming isomorphism, analogous to reduced latin squares.

For n in [1,2,4], a(n) = 1 showing uniqueness up to isomorphism.

David F. Manlove, Algorithmics of Matching Under Preferences, World Scientific (2013) [Section 2.2.2].

Cf. A344669 (unreduced), A351430 (order 4), A368419 (order 5), A351409 (total reduced instances), A010790 (reduction factor offset by 1).

a(n) = A344669(n) / A010790(n-1).
a(4) = A351430(10).
a(5) = A368419(0).

A351580 a(n) is the number of multisets of size n-1 consisting of permutations of n elements.

Original entry on oeis.org

1, 2, 21, 2600, 9078630, 1634935320144, 22831938997720867560, 34390564970975286088924022400, 7457911916650283082000186530740981347120, 300682790088737748950725540713718365319268411170195200, 2830053444386286847574443631356044745870287426798365860653876609636480

Offset: 1

Dan Eilers, Feb 13 2022

nonn

a(n) is the number of reduced men's ranking tables in the stable marriage problem of order n. In the SMP (as noted in A351409), relabeling men or women has no effect on the number of stable matchings. So the women can be relabeled to normalize the order of man #1's rankings (with woman #1 as his first choice and woman n as his last choice), and then the men except man #1 can be relabeled to normalize the lexicographic order of those men's rankings. Since man #1's rankings end up fixed in natural order, they do not contribute to the number of possibilities, leaving n! multichoose (n-1) ways to arrange the rankings of the other n-1 men.
The number of unreduced men's ranking tables is given by A036740. Relabeling just the women reduces this to A134366. Alternately, relabeling just the men reduces A036740 to A344690. Relabeling both men and women reduces the men's relabeling reduction, A344690, by a factor of (n!+n-1)/n to a(n).
It might be tempting to try to reduce A344690 by a factor of n!, but that doesn't work because not all of man #1's rankings are equally likely after relabeling all the men to give man #1 the lexicographically least rankings.
There is room for further relabeling reduction from a(n), given by A263921. The reduction from a(n) to A263921 is analogous to the reduction from reduced latin squares, A000315, to A123234.
Each of the a(n) reduced men's ranking tables can be combined with the A036740 possible unreduced women's ranking tables to form complete instances, but these instances have more possibilities than A351409. For example, a(3)*A036740(3)=21*216=4536 > A351409(3)=3888. However, fewer possibilities result from using A263921 in place of a(n), although the men's ranking tables of A263921 may not be as straightforward to generate. With A263921(3)=10, 10*216=2160 < 3888.

			Starting with the following men's ranking table of order 3, where row k represents man k's rankings, the 1 in the 2nd position of row 3 means that man #3 ranks woman #2 as his 1st choice.
  213
  321
  213
Step 1: reorder columns so row 1 is in natural order:
  123
  231
  123
Step 2: reorder rows 2 to n so rows are in lexical order:
  123
  123
  231
a(3)=21 because there are 1+2+3+4+5+6 = 21 possibilities for the last two rows in lexical order, with 3!=6 possible permutations for each row.
The 21 tables for a(3) are the following:
  123   123   123   123   123   123   123
  123   123   123   123   123   123   132
  123   132   213   231   312   321   132
.
  123   123   123   123   123   123   123
  132   132   132   132   213   213   213
  213   231   312   321   213   231   312
.
  123   123   123   123   123   123   123
  213   231   231   231   312   312   321
  321   231   312   321   312   321   321

Alois P. Heinz, Table of n, a(n) for n = 1..31
Wikipedia, Counting multisets

Cf. A036740, A071919, A134366, A344690, A263921, A351409, A000315, A185141, A030495.

Table[Binomial[n!+n-2,n-1],{n,15}] (* Harvey P. Dale, Jun 02 2023 *)

a(n) = binomial(n! + n - 2, n - 1) \\ Andrew Howroyd, Feb 13 2022

a(n) = binomial(n! + n - 2, n - 1).
a(n) = n*A344690(n)/A030495(n-1).
a(n) = A344690*n/(n! + n - 1).
a(n) = A071919(n-1,n!). - Alois P. Heinz, Feb 16 2022

Erroneous Mathematica program deleted by N. J. A. Sloane, Jun 02 2023

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

Dan Eilers, Jan 27 2024

nonn

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

A360213 Number of distinct stable marriage problem instances up to gender exchange.

Original entry on oeis.org

1, 10, 23436, 55037822976, 309586821132441600000, 9704204980882671472665034752000000, 3411909590124519376908837990487929799751761920000000, 24394862766922609598505096548473341484170343775734092352694570188800000000

Offset: 1

Dan Eilers, Jan 29 2023

nonn

In the Stable Marriage Problem, the men's and women's preference lists can be swapped without affecting the number of blocking pairs or stable matchings, because the definitions of blocking pairs and stable matchings are symmetrical with respect to gender. a(n) is the number of instances in a canonical form where the men's preferences are lexicographically less than or equal to the women's preferences.
The A185141(n) instances of order n can be arranged in a square table with rows and columns indexed respectively by all possible men's and women's preferences in lexical order. The main diagonal of the square would be instances with men's preferences equal to women's preferences. The upper triangular region above the diagonal would contain instances with men's preferences less than women's preferences. The number of rows and columns in the table is given by A036740. The number of elements in the upper triangular region of a square, including the diagonal, is given by A000217. So a(n) composes A000217 with A036740 (performing A036740 first).
This sequence is like A351409 and A343700 in that they all involve means of reducing the search space, applied either individually or in combination, when searching for instances that maximize the number of stable matchings.

			For order 2 we have A185141(2) = 16 instances that can be arranged in a 4 X 4 square with A000217(4) = (4 * 5) / 2 = 10 distinct instances up to gender exchange in the upper triangular region including the diagonal. So a(2) = 10.

Wikipedia, Stable Marriage Problem

Cf. A185141, A036740, A000217, A351409, A343700.

Table[((n!)^n) * ((n!)^n + 1) / 2, {n, 1, 8}]

a(n) = A000217(A036740(n)).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Crossrefs

Formula

A357269 Maximum number of stable matchings in the stable marriage problem of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A368419 a(n) is the number of reduced stable marriage problem instances of order 5 that generate 16 - n possible stable matchings.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A368433 a(n) is the number of reduced instances in the stable marriage problem of order n that generate the maximum possible number of stable matchings.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A351580 a(n) is the number of multisets of size n-1 consisting of permutations of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Crossrefs

A360213 Number of distinct stable marriage problem instances up to gender exchange.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula