Concept

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. 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. An example of a 3 × 5 Latin rectangle is: {| class="wikitable" |- |0|| 1|| 2|| 3|| 4 |- |3|| 4 ||0 ||1|| 2 |- |4|| 0|| 3|| 2|| 1 |} 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. Let L(k, n) denote the number of normalized k × n Latin rectangles. Then the total number of k × n Latin rectangles is A 2 × n 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, L(k, n), of small sizes is given by {| class="wikitable" style="text-align:center;" |-

! k\n !!1!!2!!3!!4!!5!!6!!7!!8
! 1
1
-
! 2
-
! 3
-
! 4
-
! 5
-
! 6
-
! 7
-
! 8
}
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.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.