Латын квадраты: комбинаторика және эксперименттік жобалау

Square array with symbols that each occur once per row and column

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin square is
A B C C A B B C A

The name "Latin square" was inspired by mathematical papers by Leonhard Euler (1707–1783), who used Latin characters as symbols, but any set of symbols can be used: in the above example, the alphabetic sequence A, B, C can be replaced by the integer sequence 1, 2, 3. Euler began the general theory of Latin squares.

The Korean mathematician Choi Seok jeong was the first to publish an example of Latin squares of order nine, in order to construct a magic square in 1700, predating Leonhard Euler by 67 years.

A transversal in a Latin square is a choice of n cells, where each row contains one cell, each column contains one cell, and there is one cell containing each symbol. One can consider a Latin square as a complete bipartite graph in which the rows are vertices of one part, the columns are vertices of the other part, each cell is an edge (between its row and its column), and the symbols are colors. The rules of the Latin squares imply that this is a proper edge coloring. With this definition, a Latin transversal is a matching in which each edge has a different color; such a matching is called a rainbow matching. Therefore, many results on Latin squares/rectangles are contained in papers with the term "rainbow matching" in their title, and vice versa. Some Latin squares have no transversal. For example, when n is even, an n by n Latin square in which the value of cell i,j is (i+j) mod n has no transversal. Here are two examples:In 1967, H. J. Ryser conjectured that, when n is odd, every n by n Latin square has a transversal. In 1975, S. K. Stein and Brualdi conjectured that, when n is even, every n by n Latin square has a partial transversal of size n−1. A more general conjecture of Stein is that a transversal of size n−1 exists not only in Latin squares but also in any n by n array of n symbols, as long as each symbol appears exactly n times. Every n by n Latin square has a partial transversal of size n − sqrt(n). Every n by n Latin square has a partial transversal of size n − 11 log(n). Every n by n Latin square has a partial transversal of size n − O(log n/loglog n). Every large enough n by n Latin square has a partial transversal of size n −1. (Preprint)

For small squares it is possible to generate permutations and test whether the Latin square property is met. For larger squares, Jacobson and Matthews' algorithm allows sampling from a uniform distribution over the space of n × n Latin squares.

In the design of experiments, Latin squares are a special case of row column designs for two blocking factors. In algebra, Latin squares are related to generalizations of groups; in particular, Latin squares are characterized as being the multiplication tables (Cayley tables) of quasigroups. A binary operation whose table of values forms a Latin square is said to obey the Latin square property.

The problem of determining if a partially filled square can be completed to form a Latin square is NP complete. The popular Sudoku puzzles are a special case of Latin squares; any solution to a Sudoku puzzle is a Latin square. Sudoku imposes the additional restriction that nine particular 3×3 adjacent subsquares must also contain the digits 1–9 (in the standard version). See also Mathematics of Sudoku. The more recent KenKen and Strimko puzzles are also examples of Latin squares.

Latin squares have been used as the basis for several board games, notably the popular abstract strategy game Kamisado.

Latin squares are used in the design of agronomic research experiments to minimise experimental errors.

The Latin square also figures in the arms of the Statistical Society of Canada, being specifically mentioned in its blazon. Also, it appears in the logo of the International Biometric Society.

A Latin rectangle is a generalization of a Latin square in which there are n columns and n possible values, but the number of rows may be smaller than n. Each value still appears at most once in each row and column. A Graeco Latin square is a pair of two Latin squares such that, when one is laid on top of the other, each ordered pair of symbols appears exactly once. A Latin hypercube is a generalization of a Latin square from two dimensions to multiple dimensions.