Difference between revisions of "Latin rectangle"
(links) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
Line 1: | Line 1: | ||
− | + | <!-- | |
+ | 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. | ||
+ | --> | ||
− | + | {{TEX|auto}} | |
+ | {{TEX|done}} | ||
− | For | + | 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 $. | ||
− | + | 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 [[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 | ||
− | + | $$ | |
+ | \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 + | ||
− | The term "Latin rectangle" is often used in a more general sense: A generalized Latin rectangle of dimension | + | \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 | + | 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 $.
Latin rectangle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_rectangle&oldid=47586