Difference between revisions of "Latin rectangle"

A rectangular matrix of dimension $m \times n$, $m \leq n$, each row of which is a permutation (without repetitions) of the elements of a set $S$ consisting of $n$ elements, and in the columns each element occurs at most once. For $m = n$ a Latin rectangle is a Latin square of order $n$. Usually $S = \{ 1 \dots n \}$, and one says that the Latin rectangle is constructed on the set $S$.

A Latin rectangle exists for any natural numbers $m$ and $n$, $m \leq n$. An example of a Latin rectangle is a matrix with first row $( 1 \dots n )$ and where any subsequent row is obtained from the previous row by a cyclic shift by one place. A Latin rectangle of dimension $m \times n$, $m < n$, can always be completed to a Latin square of order $n$ in such a way that the first $m$ rows of the Latin square are the same as those of the Latin rectangle.

For the number $L ( m , n )$ of Latin rectangles of dimension $m \times n$ one has the following lower bound:

$$L ( m , n ) \geq n ! ( n - 1 ) ! \dots ( n - m + 1 ) ! .$$

A Latin rectangle is said to be normalized if its first row is $( 1 \dots n )$. The number $K ( m , n )$ of normalized Latin rectangles is connected with $L ( m , n )$ by the relation

$$L ( m , n ) = n ! K ( m , n ) .$$

The calculation of $L ( m , n )$ for $m = 2$ and 3 is connected with the following classical combinatorial problems: the problem of the number of derangements and the married-couples problem. Thus, the number of derangements $D _ {n}$ equals $K ( 2 , n )$, and the number of arrangements $U _ {n}$ in the married-couples problem is the number of Latin rectangles of dimension $3 \times n$ with first two rows

$$\left ( \begin{array}{ccccc} 1 & 2 & 3 &\dots & n \\ n & 1 & 2 &\dots &n- 1 \\ \end{array} \right ) .$$

For $U _ {n}$ one has the formulas

$$U _ {n} = \sum _ { k= } 0 ^ { n } ( - 1 ) ^ {k} \frac{2 k }{2 k - 1 } \left ( 2k- \frac{1}{k} \right ) ( n - k ) ! ,$$

$$U _ {n} \sim n ! e ^ {-} 2 \left ( 1 - \frac{1}{n-} 1 + \dots + \frac{ ( - 1 ) ^ {k} }{k ! ( n - 1 ) _ {k} } + \dots \right ) ,$$

$$( m) _ {k} = m ( m - 1 ) \dots ( m - k + 1 ) .$$

The number $K ( 3 , n )$ can be expressed in terms of $D _ {k}$ and $U _ {l}$:

$$K ( 3 , n ) = \sum _ { k= } 0 ^ { m } \left ( \begin{array}{c} n \\ k \end{array} \right ) D _ {n-} k D _ {k} U _ {n-} 2k ,$$

where $m = [ n / 2 ]$, $U _ {0} = 1$. One also has the following asymptotic expansion:

$$K ( 3 , n ) \sim ( n ! ) ^ {2} e ^ {-} 3 \left ( 1 - \frac{1}{n} - \frac{1}{2 ! ( n ) _ {2} } + \dots + \frac{b _ {s} }{s ! ( n ) _ {s} } + \dots \right ) ,$$

where $b _ {s} = H _ {s} ( - 1 / 2 )$, $H _ {s} ( t)$ being the Hermite polynomials. It is also known that

$$K ( 3 , r + s ) \equiv 2 ^ {r} K ( 3 , s ) ( \mathop{\rm mod} r ) .$$

The problem of enumerating Latin rectangles having more than three rows is unsolved (1982). For $m < n ^ {( 1 / 3 ) - \delta }$, where $\delta = \delta ( n) \rightarrow 0$ such that $n ^ {- \delta ( n) } \rightarrow 0$, the following asymptotic behaviour holds:

$$L ( m , n ) \sim ( n ! ) ^ {m} \mathop{\rm exp} \left \{ - \frac{m ( m - 1 ) }{2} \right \} .$$

Certain concepts and theorems connected with Latin squares can be extended to Latin rectangles. Thus, two Latin rectangles $\| a _ {ij} \|$ and $\| b _ {ij} \|$ of dimension $m \times n$ are said to be orthogonal if all pairs of the form $( a _ {ij} , b _ {ij} )$ are distinct. A set of Latin rectangles in which any two of them are orthogonal has at most $m - 1$ Latin rectangles.

The term "Latin rectangle" is often used in a more general sense: A generalized Latin rectangle of dimension $r \times s$, constructed on a set $S$ consisting of $n$ elements, is a matrix of dimension $r \times s$ with elements from $S$ that occur at most once in each row and column. A (generalized) Latin rectangle of dimension $r \times s$ constructed on $n$ symbols can be extended to a Latin square of order $n$ if and only if each symbol occurs at least $r + s - n$ times in the Latin rectangle.

The married-couples problem (or problème des ménages) asks for the number of ways of seating $n$ married couples at a circular table with men and women alternating and so that no wife sits next to her husband. The number of solutions is $M _ {n} = 2 n ! U _ {n}$, where $U _ {n}$ is called the $n$- th ménage number. The number $U _ {n}$ is equal to the number of permutations $\sigma$ of $\{ 1 \dots n \}$ such that $\sigma ( i) \neq i , i + 1$ for all $i = 1 \dots n - 1$ and $\sigma ( n) \neq 1 , n$.