Rectangle latin

En mathématiques combinatoires , un rectangle latin est une matrice r × n (où r ≤ n ), utilisant n symboles, généralement les nombres 1, 2, 3, ..., n ou 0, 1, ..., n − 1 comme entrées, aucun nombre n'apparaissant plus d'une fois dans une ligne ou une colonne.

Un rectangle latin n × n est appelé un carré latin . Les rectangles latins et les carrés latins peuvent également être décrits comme les colorations optimales des graphes de Rook , ou comme les colorations optimales des arêtes des graphes bipartis complets .

Un exemple de rectangle latin 3 × 5 est :

Un rectangle latin est dit normalisé (ou réduit ) si sa première ligne est dans l'ordre naturel, tout comme sa première colonne.

L'exemple ci-dessus n'est pas normalisé.

Soit L ( k, n ) le nombre de rectangles latins normalisés k × n . Le nombre total de rectangles latins k × n est alors

Un rectangle latin 2 × n correspond à une permutation sans points fixes . De telles permutations ont été appelées permutations discordantes . Une énumération de permutations discordantes avec une permutation donnée est le célèbre problème des rencontres . L'énumération de permutations discordantes avec deux permutations, dont l'une est un simple décalage cyclique de l'autre, est connue sous le nom de problème réduit des ménages .

Le nombre de rectangles latins normalisés, L ( k , n ) , de petites tailles est donné par

Lorsque k = 1, c'est-à-dire qu'il n'y a qu'une seule ligne, puisque les rectangles latins sont normalisés, il n'y a pas de choix quant à ce que peut être cette ligne. Le tableau montre également que L ( n − 1, n ) = L ( n , n ) , ce qui s'ensuit puisque s'il manque une seule ligne, l'entrée manquante dans chaque colonne peut être déterminée à partir de la propriété du carré latin et le rectangle peut être étendu de manière unique à un carré latin.

La propriété de pouvoir étendre un rectangle latin manquant d'une ligne à un carré latin mentionnée ci-dessus peut être considérablement renforcée. En effet, si r < n , il est alors possible d'ajouter n − r lignes à un rectangle latin r × n pour former un carré latin, en utilisant le théorème de mariage de Hall .

Un carré semi-latin est un autre type de carré latin incomplet. Un carré semi-latin est un tableau n × n , L , dans lequel certaines positions sont inoccupées et d'autres positions sont occupées par l'un des entiers {0, 1, ..., n − 1 }, tel que, si un entier k apparaît dans L , alors il apparaît n fois et deux k n'appartiennent pas à la même ligne ou colonne. Si m entiers différents apparaissent dans L , alors L a l'indice m .

Par exemple, un carré semi-latin d'ordre 5 et d'indice 3 est :

Un carré semi-latin d'ordre n et d'indice m aura nm positions remplies. La question se pose alors : un carré semi-latin peut-il être complété en un carré latin ? De manière assez surprenante, la réponse est toujours.

Soit L un carré semi-latin d'ordre n et d'indice m , où m < n . Alors L peut être complété en un carré latin.

Une façon de le prouver est d'observer qu'un carré semi-latin d'ordre n et d'indice m est équivalent à un rectangle latin m × n . Soit L = || a _ij || un rectangle latin et S = || b _ij || un carré semi-latin, alors l'équivalence est donnée par

Par exemple, le rectangle latin 3×5

est équivalent à ce carré semi-latin d'ordre 5 et d'indice 3 :

puisque, par exemple, a ₁₀ = 3 dans le rectangle latin donc b ₃₀ = 1 dans le carré semi-latin.

En statistique , les rectangles latins ont des applications dans la conception d'expériences .