Namespaces
Variants
Actions

Difference between revisions of "Latin rectangle"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
A rectangular matrix of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576102.png" />, each row of which is a permutation (without repetitions) of the elements of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576103.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576104.png" /> elements, and in the columns each element occurs at most once. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576105.png" /> a Latin rectangle is a [[Latin square|Latin square]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576106.png" />. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576107.png" />, and one says that the Latin rectangle is constructed on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576108.png" />.
+
<!--
 +
l0576101.png
 +
$#A+1 = 72 n = 0
 +
$#C+1 = 72 : ~/encyclopedia/old_files/data/L057/L.0507610 Latin rectangle
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A Latin rectangle exists for any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l0576109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761011.png" />. An example of a Latin rectangle is a matrix with first row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761012.png" /> and where any subsequent row is obtained from the previous row by a cyclic shift by one place. A Latin rectangle of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761014.png" />, can always be completed to a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761015.png" /> in such a way that the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761016.png" /> rows of the Latin square are the same as those of the Latin rectangle.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
For the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761017.png" /> of Latin rectangles of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761018.png" /> one has the following lower bound:
+
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|Latin square]] of order  $  n $.
 +
Usually  $  S = \{ 1 \dots n \} $,
 +
and one says that the Latin rectangle is constructed on the set  $  S $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761019.png" /></td> </tr></table>
+
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.
  
A Latin rectangle is said to be normalized if its first row is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761020.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761021.png" /> of normalized Latin rectangles is connected with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761022.png" /> by the relation
+
For the number $  L ( m , n ) $
 +
of Latin rectangles of dimension  $  m \times n $
 +
one has the following lower bound:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761023.png" /></td> </tr></table>
+
$$
 +
L ( m , n )  \geq  n ! ( n - 1 ) ! \dots ( n - m + 1 ) ! .
 +
$$
  
The calculation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761024.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761025.png" /> and 3 is connected with the following [[Classical combinatorial problems|classical combinatorial problems]]: the problem of the number of derangements (see also [[Inversion (in combinatorics)|Inversion (in combinatorics)]]) and the married-couples problem. Thus, the number of derangements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761026.png" /> equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761027.png" />, and the number of arrangements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761028.png" /> in the married-couples problem is the number of Latin rectangles of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761029.png" /> with first two rows
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761030.png" /></td> </tr></table>
+
$$
 +
L ( m , n )  = n ! K ( m , n ) .
 +
$$
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761031.png" /> one has the formulas
+
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 [[derangement]]s 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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761032.png" /></td> </tr></table>
+
$$
 +
\left (
 +
\begin{array}{ccccc}
 +
1  & 2  & 3  &\dots  & n  \\
 +
n  & 1  & 2  &\dots  &n- 1  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761033.png" /></td> </tr></table>
+
\right ) .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761034.png" /></td> </tr></table>
+
For  $  U _ {n} $
 +
one has the formulas
  
The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761035.png" /> can be expressed in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761037.png" />:
+
$$
 +
U _ {n}  = \sum _ { k= } 0 ^ { n }
 +
( - 1 )  ^ {k}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761038.png" /></td> </tr></table>
+
\frac{2 k }{2 k - 1 }
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761040.png" />. One also has the following asymptotic expansion:
+
\left ( 2k-
 +
\frac{1}{k}
 +
\right ) ( n - k ) ! ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761041.png" /></td> </tr></table>
+
$$
 +
U _ {n}  \sim  n ! e  ^ {-} 2 \left ( 1 -
 +
\frac{1}{n-}
 +
1 + \dots +
 +
\frac{
 +
( - 1 )  ^ {k} }{k ! ( n - 1 ) _ {k} }
 +
+ \dots \right ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761043.png" /> being the [[Hermite polynomials|Hermite polynomials]]. It is also known that
+
$$
 +
( m) _ {k}  = m ( m - 1 ) \dots ( m - k + 1 ) .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761044.png" /></td> </tr></table>
+
The number  $  K ( 3 , n ) $
 +
can be expressed in terms of  $  D _ {k} $
 +
and  $  U _ {l} $:
  
The problem of enumerating Latin rectangles having more than three rows is unsolved (1982). For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761045.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761046.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761047.png" />, the following asymptotic behaviour holds:
+
$$
 +
K ( 3 , n ) = \sum _ { k= } 0 ^ { m }
 +
\left ( \begin{array}{c}
 +
n \\
 +
k
 +
\end{array}
 +
\right )
 +
D _ {n-} k D _ {k} U _ {n-} 2k ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761048.png" /></td> </tr></table>
+
where  $  m = [ n / 2 ] $,
 +
$  U _ {0} = 1 $.
 +
One also has the following asymptotic expansion:
  
Certain concepts and theorems connected with Latin squares can be extended to Latin rectangles. Thus, two Latin rectangles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761050.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761051.png" /> are said to be orthogonal if all pairs of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761052.png" /> are distinct. A set of Latin rectangles in which any two of them are orthogonal has at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761053.png" /> Latin rectangles.
+
$$
 +
K ( 3 , n )  \sim  ( n ! )  ^ {2} e  ^ {-} 3
 +
\left (
 +
1 -
 +
\frac{1}{n}
 +
-
 +
\frac{1}{2 ! ( n ) _ {2} }
 +
+ \dots +
  
The term  "Latin rectangle"  is often used in a more general sense: A generalized Latin rectangle of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761054.png" />, constructed on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761055.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761056.png" /> elements, is a matrix of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761057.png" /> with elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761058.png" /> that occur at most once in each row and column. A (generalized) Latin rectangle of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761059.png" /> constructed on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761060.png" /> symbols can be extended to a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761061.png" /> if and only if each symbol occurs at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761062.png" /> times in the Latin rectangle.
+
\frac{b _ {s} }{s ! ( n ) _ {s} }
 +
+ \dots
 +
\right ) ,
 +
$$
 +
 
 +
where  $  b _ {s} = H _ {s} ( - 1 / 2 ) $,
 +
$  H _ {s} ( t) $
 +
being the [[Hermite polynomials|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|Latin square]].
 
See also the references to [[Latin square|Latin square]].
Line 47: Line 169:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinatorial analysis" , Wiley  (1967)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Riordan,  "An introduction to combinatorial analysis" , Wiley  (1967)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
The married-couples problem (or problème des ménages) asks for the number of ways of seating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761063.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761064.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761065.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761066.png" />-th ménage number. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761067.png" /> is equal to the number of permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761068.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761069.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761070.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761071.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057610/l05761072.png" />.
+
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 $.

Latest revision as of 22:15, 5 June 2020


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

How to Cite This Entry:
Latin rectangle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_rectangle&oldid=12105
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article