A000479 -id:A000479 - cp's OEIS frontend

A002860 Number of Latin squares of order n; or labeled quasigroups.

1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800, 5524751496156892842531225600, 9982437658213039871725064756920320000, 776966836171770144107444346734230682311065600000

Offset: 1

N. J. A. Sloane

Also the number of minimum vertex colorings in the n X n rook graph. - Eric W. Weisstein, Mar 02 2024

David Nacin, "Puzzles, Parity Maps, and Plenty of Solutions", Chapter 15, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 245.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 53.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ronald Alter, Research Problems: How Many Latin Squares are There?, Amer. Math. Monthly 82 (1975), no. 6, 632-634. MR1537769.
Stanley E. Bammel and Jerome Rothstein, The number of 9 X 9 Latin squares, Discrete Math., 11 (1975), 93-95.
Daniel Berend, On the number of Sudoku squares, Discrete Mathematics 341.11 (2018): 3241-3248. See p. 3241.
Jeranfer Bermúdez, Richard García, Reynaldo López and Lourdes Morales, Some Properties of Latin Squares, Laboratorio Emmy Noether, 2009.
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.
John W. Brown, Enumeration of Latin squares with application to order 8, J. Combin. Theory, 5 (1968), 177-184.
Nikhil Byrapuram, Hwiseo (Irene) Choi, Adam Ge, Selena Ge, Tanya Khovanova, Sylvia Zia Lee, Evin Liang, Rajarshi Mandal, Aika Oki, Daniel Wu, and Michael Yang, Quad Squares, arXiv:2308.07455 [math.HO], 2023.
Gloria S. Choi, Beyond Sudoku: New puzzle variants based on a novel mathematical mapping, J. High Sch. Sci. (2025) Vol. 9, No. 2, 70-84.
Hai-Dang Dau and Nicolas Chopin, Waste-free Sequential Monte Carlo, arXiv:2011.02328 [stat.CO], 2020.
Abdelrahman Desoky, Hany Ammar, Gamal Fahmy, Shaker El-Sappagh, Abdeltawab Hendawi, and Sameh H. Basha, Latin Square and Artificial Intelligence Cryptography for Blockchain and Centralized Systems, Int'l Conf. Adv. Intel. Sys. Informat., Proc. 9th Int'l Conf. (AISI 2023) pp. 444-455.
Thangavelu Geetha, Amritanshu Prasad, and Shraddha Srivastava, Schur Algebras for the Alternating Group and Koszul Duality, arXiv:1902.02465 [math.RT], 2019.
E. N. Gilbert, Latin squares which contain no repeated digrams, SIAM Rev. 7 1965 189-198. MR0179095 (31 #3346). Mentions this sequence. - _N. J. A. Sloane_, Mar 15 2014
Yue Guan, Minjia Shi and Denis S. Krotov, The Steiner triple systems of order 21 with a transversal subdesign TD(3,6), arXiv:1905.09081 [math.CO], 2019.
Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, Fun with Latin Squares, arXiv:2109.01530 [math.HO], 2021.
Yang-Hui He and Minhyong Kim, Learning Algebraic Structures: Preliminary Investigations, arXiv:1905.02263 [cs.LG], 2019.
A.-A. A. Jucys, The number of distinct Latin squares as a group-theoretical constant, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 265-272. MR0419259 (54 #7283).
Dieter Jungnickel and Vladimir D. Tonchev, Counting Steiner triple systems with classical parameters and prescribed rank, arXiv:1709.06044 [math.CO], 2017.
Lintao Liu, Xuehu Yan, Yuliang Lu, and Huaixi Wang, 2-threshold Ideal Secret Sharing Schemes Can Be Uniquely Modeled by Latin Squares, National University of Defense Technology, Hefei, China, (2019).
Brendan D. McKay, Alison Meynert and Wendy Myrvold, Small Latin Squares, Quasigroups and Loops, J. Combin. Des. 15 (2007), no. 2, 98-119.
Brendan D. McKay and Eric Rogoyski, Latin squares of order ten, Electron. J. Combinatorics, 2 (1995) #N3.
Brendan D. McKay and Ian M. Wanless, On the number of Latin squares. Preprint 2004.
Brendan D. McKay and Ian M. Wanless, On the number of Latin squares, Ann. Combinat. 9 (2005) 335-344.
Jia-yu Shao and Wan-di Wei, A formula for the number of Latin squares., Discrete Mathematics 110 (1992) 293-296.
Minjia Shi, Li Xu, and Denis S. Krotov, The number of the non-full-rank Steiner triple systems, arXiv:1806.00009 [math.CO], 2018.
Douglas S. Stones, The many formulas for the number of Latin rectangles, Electron. J. Combin 17 (2010), A1.
Douglas S. Stones and Ian M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204-215.
Eric Weisstein's World of Mathematics, Latin Square.
Eric Weisstein's World of Mathematics, Minimum Vertex Coloring.
Eric Weisstein's World of Mathematics, Rook Graph.
Mark B. Wells, The number of Latin squares of order 8, J. Combin. Theory, 3 (1967), 98-99.
Krasimir Yordzhev, The bitwise operations in relation to obtaining Latin squares, arXiv preprint arXiv:1605.07171 [cs.OH], 2016.
Index entries for sequences related to Latin squares and rectangles
Index entries for sequences related to quasigroups

Cf. A000315, A000479.
Cf. A003090, A040082, A057991.
Cf. A098679 (Latin cubes).
A row of the array in A249026.

Table[Length[ResourceFunction["FindProperColorings"][GraphProduct[CompleteGraph[n], CompleteGraph[n], "Cartesian"], n]], {n, 5}]

a(n) = n!*A000479(n) = n!*(n-1)!*A000315(n).

One more term (from the McKay-Wanless article) from Richard Bean, Feb 17 2004

A000315 Number of reduced Latin squares of order n; also number of labeled loops (quasigroups with an identity element) with a fixed identity element.

Original entry on oeis.org

1, 1, 1, 4, 56, 9408, 16942080, 535281401856, 377597570964258816, 7580721483160132811489280, 5363937773277371298119673540771840

Offset: 1

N. J. A. Sloane

A reduced Latin square of order n is an n X n matrix where each row and column is a permutation of 1..n and the first row and column are 1..n in increasing order. - Michael Somos, Mar 12 2011

The Stones-Wanless (2010) paper shows among other things that a(n) is 0 mod n if n is composite and 1 mod n if n is prime.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 183.
J. Denes, A. D. Keedwell, editors, Latin Squares: new developments in the theory and applications, Elsevier, 1991, pp. 1, 388.
R. A. Fisher and F. Yates, Statistical Tables for Biological, Agricultural and Medical Research. 6th ed., Hafner, NY, 1963, p. 22.
C. R. Rao, S. K. Mitra and A. Matthai, editors, Formulae and Tables for Statistical Work. Statistical Publishing Society, Calcutta, India, 1966, p. 193.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, pp. 37, 53.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 240.

S. E. Bammel and J. Rothstein, The number of 9x9 Latin squares, Discrete Math., 11 (1975), 93-95.
Jeranfer Bermúdez, Richard García, Reynaldo López and Lourdes Morales, Some Properties of Latin Squares, Laboratorio Emmy Noether, 2009.
Nikhil Byrapuram, Hwiseo (Irene) Choi, Adam Ge, Selena Ge, Tanya Khovanova, Sylvia Zia Lee, Evin Liang, Rajarshi Mandal, Aika Oki, Daniel Wu, and Michael Yang, Quad Squares, arXiv:2308.07455 [math.HO], 2023.
B. Cherowitzo, Latin Squares, Comb. Structures Lecture Notes.
Gheorghe Coserea, Solutions for n=5.
Gheorghe Coserea, Solutions for n=6.
Gheorghe Coserea, MiniZinc model for generating solutions.
E. N. Gilbert, Latin squares which contain no repeated digrams, SIAM Rev. 7 1965 189--198. MR0179095 (31 #3346). Mentions this sequence. - _N. J. A. Sloane_, Mar 15 2014
Brian Hopkins, Euler's Enumerations, Enumerative Combinatorics and Applications (2021) Vol. 1, No. 1, Article #S1H1.
B. D. McKay, A. Meynert and W. Myrvold, Small latin squares, quasigroups and loops, J. Combin. Designs, vol. 15, no. 2 (2007) pp. 98-119.
B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combinatorics, 2 (1995) #N3.
B. D. McKay and I. M. Wanless, On the number of Latin squares. Preprint 2004.
B. D. McKay and I. M. Wanless, On the number of Latin squares, Ann. Combinat. 9 (2005) 335-344.
Young-Sik Moon, Jong-Yoon Yoon, Jong-Seon No, and Sang-Hyo Kim, Interference Alignment Schemes Using Latin Square for Kx3 MIMO X Channel, arXiv:1810.05400 [cs.IT], 2018.
Noah Rubin, Curtis Bright, Kevin K. H. Cheung, and Brett Stevens, Integer and Constraint Programming Revisited for Mutually Orthogonal Latin Squares, arXiv:2103.11018 [cs.DM], 2021. Mentions this sequence.
J. Shao and W. Wei, A formula for the number of Latin squares., Discrete Mathematics 110 (1992) 293-296.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
D. S. Stones, The many formulas for the number of Latin rectangles, Electron. J. Combin 17 (2010), A1.
D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204-215.
E. I. Vatutin, V. S. Titov, O. S. Zaikin, S. E. Kochemazov, S. U. Valyaev, A. D. Zhuravlev, and M. O. Manzuk, Using grid systems for enumerating combinatorial objects with example of diagonal Latin squares, Information technologies and mathematical modeling of systems (2016), pp. 154-157. (in Russian)
E. I. Vatutin, O. S. Zaikin, A. D. Zhuravlev, M. O. Manzyuk, S. E. Kochemazov, and V. S. Titov, Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares. CEUR Workshop proceedings. Selected Papers of the 7th International Conference Distributed Computing and Grid-technologies in Science and Education. 2017. Vol. 1787. pp. 486-490. urn:nbn:de:0074-1787-5.
Eric Weisstein's World of Mathematics, Latin Square.
M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]
Index entries for sequences related to Latin squares and rectangles
Index entries for sequences related to quasigroups

Cf. A000479, A002860, A003090, A040082, A057771, A057997.

a(n) = A002860(n) / (n! * (n-1)!) = A000479(n) / (n-1)!.

Added June 1995: the 10th term was probably first computed by Eric Rogoyski

a(11) (from the McKay-Wanless article) from Richard Bean, Feb 17 2004

A274171 Number of diagonal Latin squares of order n with the first row in order.

Original entry on oeis.org

1, 0, 0, 2, 8, 128, 171200, 7447587840, 5056994653507584

Offset: 1

Eduard I. Vatutin, Jul 07 2016

A diagonal Latin square is a Latin square in which both the main diagonal and main antidiagonal contain each element. - Andrew Howroyd, Sep 29 2020

			The a(4) = 2 diagonal Latin squares are:
   0 1 2 3   0 1 2 3
   2 3 0 1   3 2 1 0
   3 2 1 0   1 0 3 2
   1 0 3 2   2 3 0 1
.
The a(5) = 8 diagonal Latin squares are:
   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4
   1 3 4 2 0   1 4 3 0 2   2 3 4 0 1   2 4 1 0 3
   4 2 1 0 3   3 2 1 4 0   4 0 1 2 3   4 0 3 2 1
   2 0 3 4 1   4 3 0 2 1   1 2 3 4 0   3 2 4 1 0
   3 4 0 1 2   2 0 4 1 3   3 4 0 1 2   1 3 0 4 2
.
   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4
   3 4 0 1 2   3 4 1 2 0   4 2 0 1 3   4 2 3 0 1
   1 2 3 4 0   4 2 3 0 1   1 4 3 2 0   3 4 1 2 0
   4 0 1 2 3   2 0 4 1 3   3 0 1 4 2   1 3 0 4 2
   2 3 4 0 1   1 3 0 4 2   2 3 4 0 1   2 0 4 1 3

S. E. Kochemazov, E. I. Vatutin, and O. S. Zaikin, Fast Algorithm for Enumerating Diagonal Latin Squares of Small Order, arXiv:1709.02599 [math.CO], 2017.
S. Kochemazov, O. Zaikin, E. Vatutin, and A. Belyshev, Enumerating Diagonal Latin Squares of Order Up to 9, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.
M. O. Manzuk and N. N. Nikitina, About the number of diagonal Latin squares of order 9 as a one of results of RakeSearch distributed computing project
Eduard I. Vatutin, a(9) value fixed after
E. I. Vatutin, Enumerating the diagonal Latin squares of order 8 using equivalence classes of X-based fillings of diagonals and ESODLS-schemas (in Russian)
E. I. Vatutin, Enumerating the diagonal Latin squares of order 9 using Gerasim@Home volunteer distributed computing project, equivalence classes of X-based fillings of diagonals and ESODLS-schemas (in Russian)
E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
E. I. Vatutin, S. E. Kochemazov, and O. S. Zaikin, Applying Volunteer and Parallel Computing for Enumerating Diagonal Latin Squares of Order 9, Parallel Computational Technologies. PCT 2017. Communications in Computer and Information Science, vol. 753, pp. 114-129. doi: 10.1007/978-3-319-67035-5_9.
Eduard I. Vatutin, Stepan E. Kochemazov, Oleq S.Zaikin, Maxim O. Manzuk, Natalia N. Nikitina, and Vitaly S. Titov, Central symmetry properties for diagonal Latin squares, Problems of Information Technology (2019) No. 2, 3-8.
E. I. Vatutin, O. S. Zaikin, A. D. Zhuravlev, M. O. Manzuk, S. E. Kochemazov and V. S. Titov, Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares, Proceedings of Distributed Computing and grid-technologies in science and education (GRID'16), JINR, Dubna, 2016, pp. 114-115.
Vatutin E. I., Zaikin O. S., Zhuravlev A. D., Manzuk M. O., Kochemazov S. E., and Titov V. S., The effect of filling cells order to the rate of generation of diagonal Latin squares, Information-measuring and diagnosing control systems (Diagnostics - 2016). Kursk: SWSU, 2016. pp. 33-39 (in Russian).
E. I. Vatutin, V. S. Titov, O. S. Zaikin, S. E. Kochemazov, S. U. Valyaev, A. D. Zhuravlev, and M. O. Manzuk, Using grid systems for enumerating combinatorial objects with example of diagonal Latin squares, Information technologies and mathematical modeling of systems (2016), pp. 154-157, (in Russian).
Vatutin E.I., Zaikin O.S., Zhuravlev A.D., Manzyuk M.O., Kochemazov S.E., and Titov V.S., Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares, CEUR Workshop proceedings. Selected Papers of the 7th International Conference Distributed Computing and Grid-technologies in Science and Education. 2017. Vol. 1787. pp. 486-490. urn:nbn:de:0074-1787-5.
E. I. Vatutin, Special types of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 9-18. (in Russian)
Index entries for sequences related to Latin squares and rectangles

Cf. A000315, A000479, A274806, A287764, A309283.

a(n) = A274806(n)/n!.

a(9) added from Vatutin et al. (2016) by Max Alekseyev, Oct 05 2016

a(9) corrected by Eduard I. Vatutin, Oct 20 2016

A274806 Number of diagonal Latin squares of order n.

Original entry on oeis.org

1, 0, 0, 48, 960, 92160, 862848000, 300286741708800, 1835082219864832081920

Offset: 1

Eduard I. Vatutin, Jul 07 2016

A diagonal Latin square is a Latin square in which both the main diagonal and main antidiagonal contain each element. - Andrew Howroyd, Oct 05 2020

S. Kochemazov, O. Zaikin, E. Vatutin, and A. Belyshev, Enumerating Diagonal Latin Squares of Order Up to 9, Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2.
M. O. Manzuk and N. N. Nikitina, About the number of diagonal Latin squares of order 9 as a one of results of RakeSearch distributed computing project
E. I. Vatutin, Enumerating the diagonal Latin squares of order 8 using equivalence classes of X-based fillings of diagonals and ESODLS-schemas (in Russian).
E. I. Vatutin, Enumerating the diagonal Latin squares of order 9 using Gerasim@Home volunteer distributed computing project, equivalence classes of X-based fillings of diagonals and ESODLS-schemas (in Russian).
E. I. Vatutin, A. D. Belyshev, N. N. Nikitina, and M. O. Manzuk, Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main classes of diagonal Latin squares, Telecommunications, 2023, No. 1, pp. 2-16, DOI: 10.31044/1684-2588-2023-0-1-2-16 (in Russian).
E. I. Vatutin, O. S. Zaikin, A. D. Zhuravlev, M. O. Manzuk, S. E. Kochemazov and V. S. Titov, Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares, Proceedings of Distributed Computing and grid-technologies in science and education (GRID'16), JINR, Dubna, 2016, pp. 114-115.
E. I. Vatutin, S. E. Kochemazov, and O. S. Zaikin, Applying Volunteer and Parallel Computing for Enumerating Diagonal Latin Squares of Order 9, Parallel Computational Technologies. PCT 2017. Communications in Computer and Information Science, vol. 753, pp. 114-129. doi: 10.1007/978-3-319-67035-5_9.
Eduard I. Vatutin, Stepan E. Kochemazov, Oleq S. Zaikin, Maxim O. Manzuk, Natalia N. Nikitina, and Vitaly S. Titov, Central symmetry properties for diagonal Latin squares, Problems of Information Technology (2019) No. 2, 3-8.
Vatutin E. I., Zaikin O. S., Zhuravlev A. D., Manzuk M. O., Kochemazov S. E., and Titov V. S., The effect of filling cells order to the rate of generation of diagonal Latin squares, Information-measuring and diagnosing control systems (Diagnostics - 2016). Kursk: SWSU, 2016. pp. 33-39, (in Russian).
E. I. Vatutin, V. S. Titov, O. S. Zaikin, S. E. Kochemazov, S. U. Valyaev, A. D. Zhuravlev, and M. O. Manzuk, Using grid systems for enumerating combinatorial objects with example of diagonal Latin squares, Information technologies and mathematical modeling of systems (2016), pp. 154-157, (in Russian).
Eduard I. Vatutin, a(9) value fixed
E. I. Vatutin, O. S. Zaikin, A. D. Zhuravlev, M. O. Manzyuk, S. E. Kochemazov, and V. S. Titov, Using grid systems for enumerating combinatorial objects on example of diagonal Latin squares, CEUR Workshop proceedings. Selected Papers of the 7th International Conference Distributed Computing and Grid-technologies in Science and Education. 2017. Vol. 1787. pp. 486-490. urn:nbn:de:0074-1787-5.
E. I. Vatutin, Special types of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 9-18. (in Russian)
Index entries for sequences related to Latin squares and rectangles

Cf. A000315, A000479, A274171, A287764, A309283.

a(n) = A274171(n) * n!.

a(9) from Vatutin et al. (2016) added by Max Alekseyev, Oct 05 2016

a(9) corrected by Eduard I. Vatutin, Oct 20 2016

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

A114631 Number of even fixed diagonal Latin squares.

Original entry on oeis.org

1, 1, 0, 24, 384, 702720, 6231859200, 1364560466411520

Offset: 1

Eric W. Weisstein, Dec 18 2005

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

Cf. A000479, A114632.

A114632 Number of odd fixed diagonal Latin squares.

Original entry on oeis.org

0, 0, 2, 0, 960, 426240, 5966438400, 1333257798942720

Offset: 1

Eric W. Weisstein, Dec 18 2005

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

Cf. A000479, A114631.

A344664 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where both the men's and the women's preferences form a Latin square when arranged in a matrix. In addition, it is possible to arrange all people into n man-woman couples such that they rank each other first.

Original entry on oeis.org

1, 2, 24, 13824, 216760320, 917676490752000, 749944260264355430400000, 293457967200879687743551498616832000, 84112872283641495670736269523436185936222748672000, 27460610008848610956892895086773773421767179663217968124264448000000

Offset: 1

Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 01 2021

nonn

Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have n pairs of soulmates.
The profiles with n pairs of soulmates are counted by sequence A343698. The profiles such that the men's preferences form a Latin square are counted by A343696. The profiles such that both men's and women's preferences form a Latin square are counted by A343697. The profiles in this sequence are the intersection of profiles in A343698 and A343697.
Both the men- and the women-proposing Gale-Shapley algorithm on the preference profiles described by this sequence end in one round.

			For n = 3, there are A002860(3) = 12 Latin squares of order 3. Thus, there are A002860(3) = 12 ways to set up the men's preference profiles. After that, the women's preference profiles form a Latin square with a fixed first column, as the first column is uniquely defined to generate 3 pairs of soulmates. Thus, there are A002860(3)/3! = 12/6 = 2 ways to set up the women's preference profiles, making a(3) = 12 * 2 = 24 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. A000479, A002860, A185141, A343696, A343697, A343698, A344665.

a(n) = A002860(n)^2 / n!.

a(n) = A000479(n) * A002860(n).

Corrected by Tanya Khovanova, Aug 17 2021

cp's OEIS Frontend

A094050 Duplicate of A000479.

Views

Author

Keywords

Crossrefs

A002860 Number of Latin squares of order n; or labeled quasigroups.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A000315 Number of reduced Latin squares of order n; also number of labeled loops (quasigroups with an identity element) with a fixed identity element.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A274171 Number of diagonal Latin squares of order n with the first row in order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A274806 Number of diagonal Latin squares of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Links

Crossrefs

Extensions

A114631 Number of even fixed diagonal Latin squares.

Views

Author

Keywords

Links

Crossrefs

A114632 Number of odd fixed diagonal Latin squares.

Views

Author

Keywords

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A264603 Number of structurally distinct Latin squares of order n.

Views

Author