# Enumeration of Latin Squares and Rectangles

From Combinatorics Wiki

Author's note: This is currently a snippet from my PhD thesis *On the number of Latin rectangles*^{[1]} and the paper *The many formulae for the number of Latin rectangles*^{[2]}. I can be contacted by email: douglas.stones (at) sci.monash.edu.au

- Douglas S. Stones

## Contents

## Introduction

A *Latin rectangle* is a array of symbols such that each symbol occurs exactly once in each row and at most once in each column. If then is called a *Latin square*^{[3]}. A Latin rectangle on the symbols is called *normalised* if the first row is and called *reduced* if the first row is and the first column is . Let denote the number of Latin rectangles, denote the number of normalised Latin rectangles and let denote the number of reduced Latin rectangles.. The total number of Latin rectangles is . In the case of Latin squares, the numbers , and shall be denoted , and respectively.

The values of for were given by McKay and Wanless ^{[4]}, which we reproduce below. We omit . Sloane's ^{[5]} A002860 lists .

The enumeration of has a history stretching back to Euler^{[6]}, Cayley^{[7]} and MacMahon^{[8]}^{[9]}. A survey is provided by McKay, Meynert and Myrvold^{[10]}. An upper bound on are obtained through the study of permanents^{[11]}^{[12]}. A lower bound on is given by van Lint and Wilson^{[13]}. Estimates for the number of Latin squares were given by McKay and Rogoyski^{[14]}, Zhang and Ma^{[15]} and Kuznetsov^{[16]}.

A survey of the enumeration of Latin rectangles was given by Stones and Wanless. An asymptotic formula for the number of Latin rectangles was given by Goldsil and McKay^{[17]} as with . The value of , and is given by Sloane's A000166^{[18]}, A000186^{[19]} and A000573^{[20]}, respectively.

Bailey and Cameron^{[21]} (see also the CRC Handbook^{[22]}) discuss combinatorial objects equivalent to Latin squares. Wikipedia host a list of problems in the theory of Latin squares^{[23]}.

The number of derangements^{[24]} is related to the number of Latin rectangles by

Riordan^{[25]} gave the credit to Yamamoto for the equation

Let be a prime. Stones and Wanless showed that if and then is divisible by if and only if is divisible by . For example, in the following table we can see that is indivisible by for all . Furthermore, if then divides . We will inspect the divisors of , and in the following sections.

## Four-line Latin rectangles

A formula for the number of reduced Latin rectangles is given by Doyle, from which the following table of values of was calculated. The c code used has been uploaded to Google Code^{[26]} along with code for and . We use to denote an -digit prime number and to denote an -digit composite number. Factorisations were performed using Dario Alpern's applet^{[27]}. Other formulae for the number of four-line Latin rectangles are given by Light Jr.^{[28]}, Athreya, Pranesachar and Singhi^{[29]} (see also Pranesachar^{[30]}) and Gessel^{[31]}. A similar claim is made by de Gennaro^{[32]}.

## Five-line Latin rectangles

Doyle's method can be adapted to also find , from which the following table was calculated.

## Six-line Latin rectangles

Doyle's method can be adapted to also find , from which the following table was calculated.

## Notes

- ↑ D. S. Stones, On the number of Latin rectangles, Ph.D. thesis, Monash University, 2010. [1]
- ↑ D. S. Stones, The many formulae for the number of Latin rectangles. Electron. J. Combin., 17 (2010), A1. [2]
- ↑ http://en.wikipedia.org/wiki/Latin_square
- ↑ B. D. McKay, I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) 335--344.
- ↑ N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences/A002860
- ↑ L. Euler, Recherches sur une nouvelle espéce de quarrés magiques, Verh. Zeeuwsch. Gennot. Weten. Vliss. 9 (1782) 85--239, Eneström E530, Opera Omnia OI7, 291--392.
- ↑ A. Cayley, On Latin squares, Messenger of Math., 19 (1890) 135--137.
- ↑ P. A. MacMahon, A new method in combinatory analysis, with applications to Latin squares and associated questions, Trans. Camb. Phil. Soc., 16 (1898) 262--290.
- ↑ P. A. MacMahon, Combinatory Analysis, Chelsea, 1960.
- ↑ B. D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007) 98--119.
- ↑ H. Minc, Permanents, Addison-Wesley, 1978. Encyclopedia of Mathematics and its Applications, volume 6.
- ↑ L. M. Brègman, Certain properties of nonnegative matrices and their permanents, Soviet Math. Dokl., 14 (1973) 945--949. Dokl. Akad. Nauk SSSR 211 (1973) 27--30.
- ↑ J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
- ↑ B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combin., 2 (1995) N3, 4 pp. http://www.combinatorics.org/Volume_2/PDFFiles/v2i1n3.pdf
- ↑ C. Zhang and J. Ma, Counting solutions for the N-queens and Latin square problems by efficient Monte Carlo simulations, Phys. Rev. E, 79 (2009), 016703.
- ↑ N. Y. Kuznetsov, Estimating the number of Latin rectangles by the fast simulation method, Cybernet. Systems Anal., 45 (2009) 69--75.
- ↑ C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 10 (1984) 91--92.
- ↑ http://www.research.att.com/~njas/sequences/A000166
- ↑ http://www.research.att.com/~njas/sequences/A000186
- ↑ http://www.research.att.com/~njas/sequences/A000573
- ↑ R. A. Bailey and P. J. Cameron, Latin squares: Equivalences and equivalents, (2003). Encyclopedia of Design Theory. http://designtheory.org/library/encyc/topics/lsee.pdf
- ↑ C. J. Colbourn, J. H. Dinitz, et al., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
- ↑ http://en.wikipedia.org/wiki/Problems_in_Latin_squares
- ↑ http://en.wikipedia.org/wiki/Derangement
- ↑ J. Riordan, A recurrence relation for three-line Latin rectangles, Amer. Math. Monthly 59 (3) (1952) 159-162.
- ↑ http://code.google.com/p/latinrectangles/downloads/list
- ↑ http://www.alpertron.com.ar/ECM.HTM
- ↑ F. W. Light, Jr, A procedure for the enumeration of Latin rectangles, Fibonacci Quart., 11 (1973) 241-246.
- ↑ K. B. Athreya, C. R. Pranesachar, and N. M. Singhi, On the number of Latin rectangles and chromatic polynomial of , European J. Combin., 1 (1980) 9-17.
- ↑ C. R. Pranesachar, Enumeration of Latin rectangles via SDR's, in Combinatorics and Graph Theory, A. Dold, B. Eckmann, and S. B. Rao, eds., Springer, 1981, 380-390.
- ↑ I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc., 16 (1987), 79-83.
- ↑ A. de Gennaro, How many Latin rectangles are there?, (2007). arXiv:0711.0527v1 [math.CO], 20 pp. http://arxiv.org/abs/0711.0527

## References

- J. Denés and A. D. Keedwell, Latin Squares and their Applications, Academic Press, 1974.
- J. Denés and A. D. Keedwell, Latin Squares: New Developments in the Theory and Applications, North-Holland, Amsterdam, 1991.
- P. G. Doyle, The number of Latin rectangles, (2007). arXiv:math/0703896v1 [math.CO], 15 pp. http://arxiv1.library.cornell.edu/abs/math/0703896v1
- D. S. Stones and I. M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A., 117 (2010), pp. 204-215.