Graeco-Latin square
An n×n Graeco-Latin square is a table, each cell of which contains a pair of symbols, composed of a symbol from each of two sets of n elements. Each pair occurs exactly once in the table. Each symbol in the two, not necessarily distinct, sets occurs exactly once in each row and exactly once in each column. Graeco-Latin squares have applications in the design of experiments.
A 4×4 Graeco-Latin square on the sets {A, B, C, D} and {α, β, γ, δ} is:
|
A α
|
B γ
|
C δ
|
D β
|
|
B β
|
A δ
|
D γ
|
C α
|
|
C γ
|
D α
|
A β
|
B δ
|
|
D δ
|
C β
|
B α
|
A γ
|
The tabular arrangements of {A, B, C, D} (Latin characters) alone and {α, β, γ, δ} (Greek characters) alone each forms a Latin square. Each pair from the two sets (i.e. every element of their cartesian product) occurs exactly once and we say that the two Latin squares are orthogonal.
History
In the 1780s, Leonard Euler demonstrated methods for constructing Graeco-Latin squares where n is odd or a multiple of 4. He further proved that no 2×2 square exists and conjectured that none existed for n=4k+2, where k is a natural number.
In 1901, Gaston Tarry demonstrated that there was no 6×6 square by enumerating all the possible arrangements of symbols. However, in 1959, Parker, Bose and Shrikhande constructed a 10×10 square.
In 1978, the French writer Georges Perec used the 10×10 square (believed then to be the only one possible) for the structure of constraints underlying his novel La Vie mode d'emploi.
Referenced By
Gaston Tarry | La Vie mode d'emploi | List of combinatorics topics | List of statistical topics | ProbabilityApplications | Probability Applications
|
