A185141 -id:A185141 - cp's OEIS frontend

A306760 a(n) = Product_{i=1..n, j=1..n} (i*j + 1).

1, 2, 90, 705600, 4105057320000, 52487876090562232320000, 3487017405172854771910634342400000000, 2448893405298238642974553493547144534294528000000000000, 33257039167768610289435138215602132823918399655132218973388800000000000000000

Offset: 0

Vaclav Kotesovec, Mar 08 2019

nonn

Cf. A079478, A101686, A185141, A324444, A306765, A324589, A306907.

a:= n-> mul(mul(i*j+1, i=1..n), j=1..n):
seq(a(n), n=0..9);  # Alois P. Heinz, Jun 24 2023

Table[Product[i*j + 1, {i, 1, n}, {j, 1, n}], {n, 1, 10}]
Table[n!^(2*n) * Product[Binomial[n + 1/j, n], {j, 1, n}], {n, 1, 10}]

a(n) ~ c * n^(n*(2*n+1) + 2*gamma) * (2*Pi)^n * exp(1/6 + log(n)^2 - 2*n^2), where c = 1/A306765 and gamma is the Euler-Mascheroni constant A001620.

a(0)=1 prepended by Alois P. Heinz, Jun 24 2023

A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).

Original entry on oeis.org

1, 2, 384, 40310784, 7608405715845120, 6419592322744320000000000000, 50709051409862934701619019776000000000000000, 6988904507653043786857875068352862005134308147200000000000000000

Offset: 1

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

nonn

For such profiles, each person has exactly one valid partner: their soulmate. Consequently, there is only one stable matching: where the soulmates are married to each other.
For these profiles, the Gale-Shapley algorithm, whether it is men-proposing or women proposing, ends in one round.
This is a subsequence of A001013.

			For n = 3, there are 3! = 6 ways to pair the men and women into soulmate pairs, then 2! ways to finish each person's preference profile, making 6 * 2!^6 = 384 ways to set up the preference profiles.

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. A001013, A185141, A343699, A343700.

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

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

A351409 a(n) = n(n!)^(2n-2).

Original entry on oeis.org

1, 8, 3888, 764411904, 214990848000000000, 224634374557469245440000000000, 1880461634768804771224006806208512000000000000, 240091793104790737576620139562796649430329798636339200000000000000, 813675117804798213250391541747787241264315446434692481270971279693253181440000000000000000

Offset: 1

Dan Eilers, Feb 11 2022

nonn

a(n) is the number of reduced Stable Marriage Problem instances of order n. In the SMP, relabeling men or women has no effect on the number of stable matchings. So the men and 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 to similarly normalize the order of woman #1's rankings, except for her ranking of man #1. This reduces the number of possible instances by a factor of n!(n-1)! (A010790 with shifted offset), from (n!)^(2n) (A185141) to a(n). This reduction is directly analogous to the identical reduction from latin squares (A002860) to reduced latin squares (A000315), and can be directly applied to the Latin Stable Marriage Problem (A351413). As with reduced latin squares, some further reduction is possible analogous to row/column reduced latin squares (A123234).
It is tempting to aim for a reduction of (n!)^2 by simultaneously normalizing all of man #1 and woman #1's preferences, but that isn't possible unless man #1 and woman #1 happen to be mutual first choices.
Applying this reduction to A344669 reduces A344669(2) and A344669(4) to 1, demonstrating that these maximal instances arising in A005154 are unique up to participant relabeling. It raises the question of which other values of n make A344669(n) reducible to 1.

Andrew Howroyd, Table of n, a(n) for n = 1..20
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 7, Symmetries].

Cf. A185141, A000315, A351413, A344669.

a[n_] := n*(n!)^(2*n - 2); Table[a[n], {n, 1, 9}] (* Robert P. P. McKone, Feb 12 2022 *)

a(n) = n*(n!)^(2*n-2) \\ Andrew Howroyd, Feb 12 2022

a(n) = A185141(n) / A010790(n-1).

A343700 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are no pairs of people who rank each other first.

Original entry on oeis.org

0, 2, 9984, 28419102720, 175302739963548794880, 5801674463718565478400000000000000, 2113937863028052653298578438638220083200000000000000, 15500609395854457241550377325238753195602871153217230602240000000000000000

Offset: 1

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

nonn

Two people who rank each other first are called soulmates. Thus, this sequence enumerates the profiles without soulmates.
This sequence is in contrast to the sequence A343698 which enumerates profiles with n pairs of soulmates.
The preference profiles with the most stable matchings do not have soulmates.

			For n=2, suppose A and B are the men and C and D are the women, then the only two possibilities are the following: a) A prefers C, C prefers B, B prefers D, and D prefers A; 2) A prefers D, D prefers B, B prefers C, and C prefers A.

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.

Cf. A185141, A343698, A343699, A350558, A284458.

Table[Total[
  Table[(-1)^i Binomial[n, i]^2 (n - 1)!^(2 i) i! n!^(2 n - 2 i), {i,
    0, n}]], {n, 10}]

a(n) = sum(i=0, n, ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2*i) * i! * n!^(2*n - 2*i))); \\ Michel Marcus, Jan 20 2023

a(n) = Sum_{i = 0..n} ((-1)^i * binomial(n, i)^2 * (n - 1)!^(2i) * i! * n!^(2n - 2i)).

a(n) = A350558(n)*A284458(n). - Dan Eilers, Jan 17 2023

A349506 a(n) is the numerator of n!^(2*n)/(n^n^2).

Original entry on oeis.org

1, 1, 64, 6561, 63403380965376, 1000000000000, 10061319724179153710638694400000000000000, 9396559338406702410023114843902587890625, 528450425551613768181656289451784661530463698944000000000000000000, 13597557929083423616920569866317288159544321459878738801559053666747416576

Offset: 1

Stefano Spezia, Nov 20 2021

a(n) is the numerator of a lower bound of the number of the vertices of the polytope of stochastic semi-magic n X n X n cubes, or equivalently, of the number of Latin squares of order n, or equivalently, of the number of n X n X n line-stochastic (0,1)-tensors (see Ahmed et al. and Zhang et al.).

Stefano Spezia, Table of n, a(n) for n = 1..30
Maya Mohsin Ahmed, Algebraic Combinatorics of Magic Squares, University of California - Davis, Ph.D. Thesis, 2004; arXiv:math/0405476 [math.CO], 2004. See p. 43.
Maya Mohsin Ahmed, Jesús De Loera and Raymond Hemmecke, Polyhedral Cones of Magic Cubes and Squares. In: Aronov B., Basu S., Pach J., Sharir M. (eds) Discrete and Computational Geometry. Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg (2003). arXiv:math/0201108 [math.CO], 2002. See p. 3.
Fuzhen Zhang and Xiao-Dong Zhang, Comparison of the upper bounds for the extreme points of the polytopes of line-stochastic tensors, arXiv:2110.12337 [math.CO], 2021. See p. 3.

Cf. A000142, A000290, A002489, A005843, A185141.

Cf. A349507 (denominators), A349508, A349509, A349510, A349511, A349512.

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

a(n) = numerator(n!^(2*n)/n^n^2); \\ Michel Marcus, Nov 22 2021

a(n)/A349507(n) ~ n^(-n^2)*(exp(-n)*n^(n-1/2)*(1+12*n))^(2*n)*(Pi/72)^n.

A349507 a(n) is the denominator of n!^(2*n)/(n^n^2).

Original entry on oeis.org

1, 1, 27, 256, 30517578125, 531441, 378818692265664781682717625943, 1208925819614629174706176, 8727963568087712425891397479476727340041449, 867361737988403547205962240695953369140625, 12527829399838427440107579247354215251149392000034969484678615956504532008683916069945559954314411495091

Offset: 1

Stefano Spezia, Nov 20 2021

a(n) is the denominator of a lower bound of the number of the vertices of the polytope of stochastic semi-magic n X n X n cubes, or equivalently, of the number of Latin squares of order n, or equivalently, of the number of n X n X n line-stochastic (0,1)-tensors (see Ahmed et al. and Zhang et al.).

Stefano Spezia, Table of n, a(n) for n = 1..28
Maya Mohsin Ahmed, Algebraic Combinatorics of Magic Squares, University of California - Davis, Ph.D. Thesis, 2004; arXiv:math/0405476 [math.CO], 2004. See p. 43.
Maya Mohsin Ahmed, Jesús De Loera and Raymond Hemmecke, Polyhedral Cones of Magic Cubes and Squares. In: Aronov B., Basu S., Pach J., Sharir M. (eds) Discrete and Computational Geometry. Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg (2003). arXiv:math/0201108 [math.CO], 2002. See p. 3.
Fuzhen Zhang and Xiao-Dong Zhang, Comparison of the upper bounds for the extreme points of the polytopes of line-stochastic tensors, arXiv:2110.12337 [math.CO], 2021. See p. 3.

Cf. A000142, A000290, A002489, A005843, A185141.

Cf. A349506 (numerators), A349508, A349509, A349510, A349511, A349512.

Table[Denominator[n!^(2n)/(n^n^2)],{n,11}]

a(n) = denominator(n!^(2*n)/n^n^2); \\ Michel Marcus, Nov 22 2021

A349506(n)/a(n) ~ n^(-n^2)*(exp(-n)*n^(n-1/2)*(1+12*n))^(2*n)*(Pi/72)^n.

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

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.

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

Original entry on oeis.org

1, 8, 2592, 191102976, 4013162496000000, 113241608573209804800000000, 5078594244241245901264634511360000000000, 759796697672599288560347581750936194390876487680000000000, 602809439070636186475532789128702956081602819845966698324215778508800000000000

Offset: 1

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

nonn

Equivalently, these are the profiles where each woman is ranked differently by the n men.
Equivalently, for every rank i, there is exactly one woman who is ranked i by a given man.
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.
Due to symmetry, a(n) is the number of preference profiles in the stable marriage problem with n men and n women, such that the women’s preference profiles form a Latin square.

			For n = 3, there are 3!^3 ways to set up the women's preference profiles and A002860(3) ways to set up the men's preference profiles, where A002860(3) = 12 (there are 12 different Latin squares of order 3). Thus a(3) = 3!^3 * A002860(3) = 216 * 12 = 2592.

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, A343697.

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

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

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

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)

			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.

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, A344668, A357269, A357271, A368433.

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

a(5) from Dan Eilers, Dec 23 2023

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

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

nonn

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.

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

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. A001013, A185141, A342573.

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

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

cp's OEIS Frontend

A306760 a(n) = Product_{i=1..n, j=1..n} (i*j + 1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A343700 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are no pairs of people who rank each other first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349506 a(n) is the numerator of n!^(2*n)/(n^n^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349507 a(n) is the denominator of n!^(2*n)/(n^n^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

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

Views

A351409 a(n) = n(n!)^(2n-2).