Latin rectangle

Template:Short description In combinatorial mathematics, a Latin rectangle is an Template:Math matrix (where Template:Math), using Template:Mvar symbols, usually the numbers Template:Math or Template:Math as its entries, with no number occurring more than once in any row or column.Template:Sfn

An Template:Math 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.Template:Sfn

An example of a 3 × 5 Latin rectangle is:

0	1	2	3	4
3	4	0	1	2
4	0	3	2	1

Normalization

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

The example above is not normalized.

Enumeration

Let Template:Mvar(Template:Mvar) denote the number of normalized Template:Mvar × Template:Mvar Latin rectangles. Then the total number of Template:Mvar × Template:Mvar Latin rectangles is

$\frac{n!(n-1)!L(k,n)}{(n-k)!}.$

A 2 × Template:Mvar Latin rectangle corresponds to a permutation with no fixed points. Such permutations have been called discordant permutations. 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.

The number of normalized Latin rectangles, Template:Math, of small sizes is given by

k\n	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2		1	1	3	11	53	309	2119
3			1	4	46	1064	35792	1673792
4				4	56	6552	1293216	420909504
5					56	9408	11270400	27206658048
6						9408	16942080	335390189568
7							16942080	535281401856
8								535281401856

When Template:Mvar = 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 Template:Math, 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 Template:Math, then it is possible to append Template:Math rows to an Template:Math Latin rectangle to form a Latin square, using Hall's marriage theorem.

Semi-Latin squares

A semi-Latin square is another type of incomplete Latin square. A semi-Latin square is an Template:Mvar × Template:Mvar array, Template:Mvar, in which some positions are unoccupied and other positions are occupied by one of the integers Template:Math}, such that, if an integer Template:Mvar occurs in Template:Mvar, then it occurs Template:Mvar times and no two Template:Mvar's belong to the same row or column. If Template:Mvar different integers occur in Template:Mvar, then Template:Mvar has index Template:Mvar.

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

1		0		2
	2	1		0
0	1		2
2	0		1
		2	0	1

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

Let Template:Mvar be a semi-Latin square of order Template:Mvar and index Template:Mvar, where Template:Mvar. Then Template:Mvar can be completed to a Latin square.

One way to prove this is to observe that a semi-Latin square of order Template:Mvar and index Template:Mvar is equivalent to an Template:Mvar × Template:Mvar Latin rectangle. Let Template:Math be a Latin rectangle and Template:Math be a semi-Latin square, then the equivalence is given by

$b_{ij}=k\text{ if and only if }{a}_{kj}=i.$

For instance, the 3×5 Latin rectangle

0	1	2	3	4
3	4	1	0	2
1	0	4	2	3

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

0	2		1
2	0	1
		0	2	1
1			0	2
	1	2		0

since, for example, Template:Mvar₁₀ = 3 in the Latin rectangle so Template:Mvar₃₀ = 1 in the semi-Latin square.

Applications

In statistics, Latin rectangles have applications in the design of experiments.Template:How?

See also

• Combinatorial design
• Rainbow matching

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

Further reading

• Template:Citation
• Template:Citation

External links

• Template:Citation