Latin Rectangle

A $k\times n$ Latin rectangle is a $k\times n$ Matrix with elements $a_{ij}\in\{1, 2, \ldots, 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, \ldots, n\}$ and first column $\{1, 2, \ldots, k\}$. Let $L(k,n)$ be the number of normalized $k\times n$ Latin rectangles, then the total number of $k\times n$ Latin rectangles is

$$N(k,n)={n!(n-1)!L(k,n)\over(n-k)!}$$

(McKay and Rogoyski 1995), where $n!$ is a Factorial. Kerewala (1941) found a Recurrence Relation for $L(3,n)$, and Athreya, Pranesachar, and Singhi (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\times 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$$

$$L(n,n) = L(n-1,n),$$

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 Sloane's A001009.

$n$	$k$	$L(k,n)$
1	1	1
2	1	1
3	2	1
4	2	3
4	3	4
5	2	11
5	3	46
5	4	56
6	2	53
6	3	1064
6	4	6552
6	5	9408
7	2	309
7	3	35792
7	4	1293216
7	5	11270400
7	6	16942080
8	2	2119
8	3	1673792
8	4	420909504
8	5	27206658048
8	6	335390189568
8	7	535281401856
9	2	16687
9	3	103443808
9	4	207624560256
9	5	112681643083776
9	6	12952605404381184
9	7	224382967916691456
9	8	377597570964258816
10	2	148329
10	3	8154999232
10	4	147174521059584
10	5	746988383076286464
10	6	870735405591003709440
10	7	177144296983054185922560
10	8	4292039421591854273003520
10	9	7580721483160132811489280

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, N3 1-4, 1995. http://www.combinatorics.org/Volume_2/volume2.html#N3.

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 Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.