A002860 -id:A002860 - cp's OEIS frontend

A249026 Array read by antidiagonals upwards: T(d,n) = number of d-dimensional permutations of n letters (d >= 0, n >= 1).

1, 1, 2, 1, 2, 3, 1, 2, 6, 4, 1, 2, 12, 24, 5, 1, 2, 24, 576, 120, 6, 1, 2, 48, 55296, 161280, 720, 7, 1, 2, 96, 36972288, 2781803520, 812851200, 5040, 8, 1, 2, 192, 6268637952000, 52260618977280, 994393803303936000, 61479419904000, 40320, 9

Offset: 0

N. J. A. Sloane, Oct 23 2014

By definition, this is the number of  nXnXnX...Xn = n^(d+1) arrays of 0's and 1's with exactly one 1 in each row, column, ..., line, ... .
An ordinary permutation is the case d = 1 (ordinary matrices with a single 1 in each row and column).
Rows d=2,3,... correspond to Latin squares, cubes, etc.

			The array begins:
d\n: 1, 2, 3,  4,  5,   6,   7,    8,     9,      10,      11,
--------------------------------------------------------------
0:   1, 2, 3,  4,  5,   6,   7,    8,     9,      10,      11,
1:   1, 2, 6,  24, 120, 720, 5040, 40320, 362880, 3628800, 39916800,  ...
2:   1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800,...
3:   1, 2, 24, 55296, 2781803520, 994393803303936000, ...
4:   1, 2, 48, 36972288, 52260618977280, ...
5:   1, 2, 96, 6268637952000, 2010196727432478720, ...
6:   1, 2, 192, ...
7:   1, 2, 384, ...
8:   1, 2, 768, ...
...

Linial, Nathan, and Zur Luria, An upper bound on the number of high-dimensional permutations, arXiv preprint arXiv:1106.0649 [math.CO], (2011).
Linial, Nathan, and Zur Luria, An upper bound on the number of high-dimensional permutations, Combinatorica, 34 (2014), 471-486.

Rows: A000142, A002860, A098679, A100540, A132206.
Column 4 = A249028.
See A249027 for another version.

A221438 T(n,k) is the number of n X k 1..(max n,k) arrays with each row and column having unrepeated values.

Original entry on oeis.org

1, 2, 2, 6, 2, 6, 24, 12, 12, 24, 120, 216, 12, 216, 120, 720, 5280, 576, 576, 5280, 720, 5040, 190800, 66240, 576, 66240, 190800, 5040, 40320, 9344160, 15321600, 161280, 161280, 15321600, 9344160, 40320, 362880, 598066560, 5411750400, 283046400

Offset: 1

R. H. Hardin, Jan 16 2013

Table starts:
....1.......2..........6...........24............120............720
....2.......2.........12..........216...........5280.........190800
....6......12.........12..........576..........66240.......15321600
...24.....216........576..........576.........161280......283046400
..120....5280......66240.......161280.........161280......812851200
..720..190800...15321600....283046400......812851200......812851200
.5040.9344160.5411750400.782137036800.20449013760000.61479419904000

			Some solutions for n=3 and k=4:
..4..1..3..2....3..1..4..2....1..2..4..3....3..4..2..1....2..3..4..1
..2..3..4..1....1..3..2..4....3..4..1..2....1..2..3..4....1..4..3..2
..1..4..2..3....2..4..3..1....2..1..3..4....2..1..4..3....3..2..1..4

R. H. Hardin, Table of n, a(n) for n = 1..83

Diagonal is A002860.
Column 1 is A000142.
Column 2 is A082491.

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

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.

Original entry on oeis.org

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.

A114629 Number of odd Latin squares of order n.

Original entry on oeis.org

0, 0, 6, 0, 80640, 306892800, 30739709952000, 53756954453370470400

Offset: 1

Eric W. Weisstein, Dec 18 2005

Eric Weisstein's World of Mathematics, Alon-Tarsi Paradox
Eric Weisstein's World of Mathematics, Latin Square

Cf. A002860, A065711, A114629, A114630.

A035483 Number of 2n X 2n symmetric matrices whose first row is 1..2n and whose rows and columns are all permutations of 1..2n.

Original entry on oeis.org

1, 1, 4, 456, 10936320, 130025295912960, 2209617218725251404267520

Offset: 0

Joshua Zucker and Joe Keane

Cf. A000438, A035481, A000315, A002860, A003090, A040082.

a(n) = A035481(2*n). - Max Alekseyev, Apr 23 2010

a(5)-a(6) from Ian Wanless, Oct 20 2019

A072377 Number of pairs of orthogonal Latin squares of order n.

Original entry on oeis.org

1, 0, 36, 3456, 3110400, 0, 3131834388480000, 32162058365970677760000, 19083454070548282639185346560000

Offset: 1

Eric W. Weisstein, Jul 19 2002

This sequence counts unordered pairs. The number of ordered pairs of MOLS is exactly double this sequence.

J. Egan and I. M. Wanless, Enumeration of MOLS of small order, Mathematics of Computation 85, 2016, 799-824.
Ian Wanless, Data on MOLS
Eric Weisstein's World of Mathematics, Latin Square

Equals n!n!(n-1)!/2 times A266166 (except for the degenerate case n=1). Cf. A000315, A002860, A266167, A266168, A266169, A266170, A266171, A266172, A266173.

More terms (and corrected the degenerate first term) from Ian Wanless, Dec 22 2015

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.

A383368 Number of intercalates in pine Latin squares of order 2n.

Original entry on oeis.org

1, 12, 27, 80, 125, 252, 343, 576, 729, 1100, 1331, 1872, 2197, 2940, 3375, 4352, 4913, 6156, 6859, 8400, 9261, 11132, 12167, 14400, 15625

Offset: 1

Eduard I. Vatutin, Apr 24 2025

Pine Latin square is a none canonical composite Latin square of order N=2*K formed from specially arranged cyclic Latin squares of order K.
By construction, pine Latin square is determined one-to-one by the cyclic square used, so number of pine Latin squares of order N is equal to number of cyclic Latin squares of order N/2.
All pine Latin squares are horizontally symmetric column-inverse Latin squares.
All pine Latin squares for selected order N are isomorphic one to another as Latin squares, so they have same properties (number of transversals, intercalates, etc.).
Pine Latin squares have interesting properties, for example, maximum known number of intercalates for some orders N (at least N in {2, 4, 6, 10, 18}).
Pine Latin squares do not exist for odd orders due to they are horizontally symmetric.
Pine Latin squares of order N=2n exists for all even orders due to existing of corresponding cyclic Latin squares of order n. According to this, maximum number of intercalates in a Latin square A092237(N) >= (2k)^2 * (2k + 1) for N=4k and A092237(N) >= (2k+1)^3 for N=4k+2. Therefore, asimptotically maximum number of intercalates in Latin squares of even orders N greater or equal than o(k1*N^3), where k1 = 1/8.

			For order N=8 pine Latin square
  0 1 2 3 4 5 6 7
  1 2 3 0 7 4 5 6
  2 3 0 1 6 7 4 5
  3 0 1 2 5 6 7 4
  4 5 6 7 0 1 2 3
  5 6 7 4 3 0 1 2
  6 7 4 5 2 3 0 1
  7 4 5 6 1 2 3 0
have 80 intercalates.
.
For order N=10 pine Latin square
  0 1 2 3 4 5 6 7 8 9
  1 2 3 4 0 9 5 6 7 8
  2 3 4 0 1 8 9 5 6 7
  3 4 0 1 2 7 8 9 5 6
  4 0 1 2 3 6 7 8 9 5
  5 6 7 8 9 0 1 2 3 4
  6 7 8 9 5 4 0 1 2 3
  7 8 9 5 6 3 4 0 1 2
  8 9 5 6 7 2 3 4 0 1
  9 5 6 7 8 1 2 3 4 0
have 125 intercalates.
.
For order N=12 pine Latin square
  0 1 2 3 4 5 6 7 8 9 10 11
  1 2 3 4 5 0 11 6 7 8 9 10
  2 3 4 5 0 1 10 11 6 7 8 9
  3 4 5 0 1 2 9 10 11 6 7 8
  4 5 0 1 2 3 8 9 10 11 6 7
  5 0 1 2 3 4 7 8 9 10 11 6
  6 7 8 9 10 11 0 1 2 3 4 5
  7 8 9 10 11 6 5 0 1 2 3 4
  8 9 10 11 6 7 4 5 0 1 2 3
  9 10 11 6 7 8 3 4 5 0 1 2
  10 11 6 7 8 9 2 3 4 5 0 1
  11 6 7 8 9 10 1 2 3 4 5 0
have 252 intercalates.

R. Bean, Critical sets in Latin squares and associated structures, Ph.D. Thesis, The University of Queensland, 2001.
Eduard I. Vatutin, About the properties of pine Latin squares (in Russian).
Eduard I. Vatutin, Proving list (examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A002860, A016755, A089207, A092237, A099721, A338522, A383570.

Hypothesis: For all known pine Latin squares of orders N=4k+2 number of intercalates a(n) = a(N/2)= a(2k+1) = (N/2)^3 = (2k+1)^3 = A016755((n-1)/2) (verified for N<29).

Hypothesis: For all known pine Latin squares of orders N=4k number of intercalates a(n) = a(N/2) = a(2k) = (N/2)^2 + (N/2)^3 = 4*k^2 + 8*k^3 = (2k)^2 * (2k+1) = 2*A089207(n/2) = 4*A099721(n/2) (verified for N<29).

A000528 Number of types of Latin squares of order n. Equivalently, number of nonisomorphic 1-factorizations of K_{n,n}.

Original entry on oeis.org

1, 1, 1, 2, 2, 17, 324, 842227, 57810418543, 104452188344901572, 6108088657705958932053657

Offset: 1

N. J. A. Sloane

Here "type" means an equivalence class of Latin squares under the operations of row permutation, column permutation, symbol permutation and transpose. In the 1-factorizations formulation, these operations are labeling of left side, labeling of right side, permuting the order in which the factors are listed and swapping the left and right sides, respectively. - Brendan McKay

There are 6108088657705958932053657 isomorphism classes of one-factorizations of K_{11,11}. - Petteri Kaski (petteri.kaski(AT)cs.helsinki.fi), Sep 18 2009

CRC Handbook of Combinatorial Designs, 1996, p. 660.
Denes and Keedwell, Latin Squares and Applications, Academic Press 1974.

A. Hulpke, Petteri Kaski and Patric R. J. Östergård, The number of Latin squares of order 11, Math. Comp. 80 (2011) 1197-1219
B. D. McKay, A. Meynert and W. Myrvold, Small Latin Squares, Quasigroups and Loops, J. Combin. Designs, to appear (2005).
Index entries for sequences related to Latin squares and rectangles

See A040082 for another version.

Cf. A002860, A003090, A000315, A040082, A000479.

More terms from Richard Bean, Feb 17 2004

a(11) from Petteri Kaski (petteri.kaski(AT)cs.helsinki.fi), Sep 18 2009

cp's OEIS Frontend

A249026 Array read by antidiagonals upwards: T(d,n) = number of d-dimensional permutations of n letters (d >= 0, n >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A221438 T(n,k) is the number of n X k 1..(max n,k) arrays with each row and column having unrepeated values.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A114629 Number of odd Latin squares of order n.

Views

Author

Keywords

Links

Crossrefs

A035483 Number of 2n X 2n symmetric matrices whose first row is 1..2n and whose rows and columns are all permutations of 1..2n.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A072377 Number of pairs of orthogonal Latin squares of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

A383368 Number of intercalates in pine Latin squares of order 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A000528 Number of types of Latin squares of order n. Equivalently, number of nonisomorphic 1-factorizations of K_{n,n}.

Views

Author

Keywords

Comments

References