TOPICS
Search

Latin Rectangle


A k×n Latin rectangle is a k×n matrix with elements a_(ij) in {1,2,...,n} such that entries in each row and column are distinct. If k=n, the special case of a Latin square results. A normalized Latin rectangle has first row {1,2,...,n} and first column {1,2,...,k}. Let L(k,n) be the number of normalized k×n Latin rectangles, then the total number of k×n Latin rectangles is

 N(k,n)=(n!(n-1)!L(k,n))/((n-k)!)
(1)

(McKay and Rogoyski 1995), where n! is a factorial. Kerewala (1941) found a recurrence relation for L(3,n), and Athreya et al. (1980) found a summation formula for L(4,n).

The asymptotic value of L(o(n^(6/7)),n) was found by Godsil and McKay (1990). The numbers of k×n Latin rectangles are given in the following table from McKay and Rogoyski (1995). The entries L(1,n) and L(n,n) are omitted, since

L(1,n)=1
(2)
L(n,n)=L(n-1,n),
(3)

but L(1,1) and L(2,1) are included for clarity. The values of L(k,n) are given as a "wrap-around" series by OEIS A001009.

nkL(k,n)
111
211
321
423
434
5211
5346
5456
6253
631064
646552
659408
72309
7335792
741293216
7511270400
7616942080
822119
831673792
84420909504
8527206658048
86335390189568
87535281401856
9216687
93103443808
94207624560256
95112681643083776
9612952605404381184
97224382967916691456
98377597570964258816
102148329
1038154999232
104147174521059584
105746988383076286464
106870735405591003709440
107177144296983054185922560
1084292039421591854273003520
1097580721483160132811489280

Explore with Wolfram|Alpha

References

Athreya, K. B.; Pranesachar, C. R.; and Singhi, N. M. "On the Number of Latin Rectangles and Chromatic Polynomial of L(K_(r,s))." Europ. J. Combin. 1, 9-17, 1980.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, 1996.Godsil, C. D. and McKay, B. D. "Asymptotic Enumeration of Latin Rectangles." J. Combin. Th. Ser. B 48, 19-44, 1990.Kerawla, S. M. "The Enumeration of Latin Rectangle of Depth Three by Means of Difference Equation" [sic]. Bull. Calcutta Math. Soc. 33, 119-127, 1941.McKay, B. D. and Rogoyski, E. "Latin Squares of Order 10." Electronic J. Combinatorics 2, No. 1, N3, 1-4, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1n3.html.Ryser, H. J. "Latin Rectangles." §3.3 in Combinatorial Mathematics. Buffalo, NY: Math. Assoc. of Amer., pp. 35-37, 1963.Sloane, N. J. A. Sequence A001009 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Latin Rectangle

Cite this as:

Weisstein, Eric W. "Latin Rectangle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LatinRectangle.html

Subject classifications