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.

See also the references to Latin square.

References

[1]	J. Riordan, "An introduction to combinatorial analysis" , Wiley (1967)

Comments

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 $.