A k_n Latin rectangle is a k_n matrix of entries from [1, 2, ..., n] such that no symbol occurs twice in any row or column. An intercalate is a 2_2 Latin subrectangle. Let N(R) be the number of intercalates in R, a randomly chosen k_n Latin rectangle. We obtain a number of results about the distribution of N(R) including its asymptotic expectation and a bound on the probability that N(R)=0. For =>0 we prove most Latin squares of order n have N(R) n 3ร2&= . We also provide data from a computer enumeration of Latin rectangles for small k, n. 1999 Academic Press 1. INTRODUCTION AND PRELIMINARY DEFINITIONS For any positive integer c, let I c =[1, 2, 3, ..., c] and
A k_n Latin rectangle is a k_n array with entries from I n with the property that no symbol is repeated within any row or column. Not surprisingly, a n_n Latin rectangle is a Latin square. An intercalate is a Latin 2_2 subsquare, or in other words a 2_2 submatrix containing only 2 distinct symbols. Note that the cells involved in an intercalate need not be contiguous.
Various papers have dealt with the construction of so-called N 2 Latin squares, or Latin squares containing no intercalates. In [5,6,9] such squares are shown to exist for all orders other than n=2 and n=4. Upper bounds on the number of intercalates have also been investigated in [3]. However, little work seems to have been published on the distribution between these two extremes or on the proportion of Latin squares which are N 2 . We will show that such squares are very rare.
We begin with some notation. Let L(k, n) denote the set of k_n Latin rectangles, which we think of as a probability space equipped with measure P( } ) corresponding to the discrete uniform distribution. For any subset