Latin rectangle

In combinatorial mathematics, a Latin rectangle is an r × n matrix (where r  n), using n symbols, usually the numbers 1, 2, 3, ..., n or 0, 1, ..., n − 1 as its entries, with no number occurring more than once in any row or column.[1]

An n × n Latin rectangle is called a Latin square. Latin rectangles and Latin squares may also be described as the optimal colorings of rook's graphs, or as optimal edge colorings of complete bipartite graphs.[2]

An example of a 3 × 5 Latin rectangle is:[3]

01234
34012
40321

Normalization

A Latin rectangle is called normalized (or reduced) if its first row is in natural order and so is its first column.[4][5]

The example above is not normalized.

Enumeration

Let L(k, n) denote the number of normalized k × n Latin rectangles. Then the total number of k × n Latin rectangles is[6]

A 2 × n Latin rectangle corresponds to a permutation with no fixed points. Such permutations have been called discordant permutations.[4] An enumeration of permutations discordant with a given permutation is the famous problème des rencontres. The enumeration of permutations discordant with two permutations, one of which is a simple cyclic shift of the other, is known as the reduced problème des ménages.[4]

The number of normalized Latin rectangles, L(k, n), of small sizes is given by[6]

k\n12345678
1 11111111
2 11311533092119
3 14461064357921673792
4 45665521293216420909504
5 5694081127040027206658048
6 940816942080335390189568
7 16942080535281401856
8 535281401856

When k = 1, that is, there is only one row, since the Latin rectangles are normalized there is no choice for what this row can be. The table also shows that L(n 1, n) = L(n, n), which follows since if only one row is missing, the missing entry in each column can be determined from the Latin square property and the rectangle can be uniquely extended to a Latin square.

Extendability

The property of being able to extend a Latin rectangle missing one row to a Latin square mentioned above, can be significantly strengthened. Namely, if r < n, then it is possible to append n  r rows to an r × n Latin rectangle to form a Latin square, using Hall's marriage theorem.[7]

Semi-Latin squares

A semi-Latin square is another type of incomplete Latin square. A semi-Latin square is an n × n array, L, in which some positions are unoccupied and other positions are occupied by one of the integers {0, 1, ..., n − 1}, such that, if an integer k occurs in L, then it occurs n times and no two k's belong to the same row or column. If m different integers occur in L, then L has index m.[8]

For example, a semi-Latin square of order 5 and index 3 is:[8]

102
210
012
201
201

A semi-Latin square of order n and index m will have nm filled positions. The question arises, can a semi-Latin square be completed to a Latin square? Somewhat surprisingly, the answer is always.

Let L be a semi-Latin square of order n and index m, where m < n. Then L can be completed to a Latin square.[8]

One way to prove this is to observe that a semi-Latin square of order n and index m is equivalent to an m × n Latin rectangle. Let L = ||aij|| be a Latin rectangle and S = ||bij|| be a semi-Latin square, then the equivalence is given by[9]

For instance, the 3×5 Latin rectangle

01234
34102
10423

is equivalent to this semi-Latin square of order 5 and index 3:[9]

021
201
021
102
120

since, for example, a10 = 3 in the Latin rectangle so b30 = 1 in the semi-Latin square.

Applications

In statistics, Latin rectangles have applications in the design of experiments.

See also

Notes

  1. Colbourn & Dinitz 2007, p. 141.
  2. Stones 2010.
  3. Brualdi 2010, p. 385
  4. Dénes & Keedwell 1974, p. 150
  5. Some authors, notably J. Riordan, do not require the first column to be in order and this will effect the validity of some formulas mentioned below.
  6. Colbourn & Dinitz 2007, p. 142
  7. Brualdi 2010, p. 386
  8. Brualdi 2010, p. 387
  9. Brualdi 2010, p. 388

References

  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice Hall, ISBN 978-0-13-602040-0
  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
  • Dénes, J.; Keedwell, A. D. (1974), Latin squares and their applications, New York-London: Academic Press, p. 547, ISBN 0-12-209350-X, MR 0351850
  • Stones, Douglas S. (2010), "The many formulae for the number of Latin rectangles", Electronic Journal of Combinatorics, 17 (1): Article 1, 46, doi:10.37236/487, MR 2661404

Further reading

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.