Carré latin
En combinatoire, un carré latin d'ordre est un tableau carré de lignes (donc de colonnes) remplies de éléments distincts dont chaque ligne et chaque colonne ne contient qu'un seul exemplaire.
On obtient facilement un carré latin en permutant circulairement successivement les lignes en partant de la première, comme par exemple :
A | B | C | D |
B | C | D | A |
C | D | A | B |
D | A | B | C |
mais par exemple, le carré latin :
A | B | C | D |
B | A | D | C |
C | D | A | B |
D | C | B | A |
ne peut être obtenu en permutant des lignes ou des colonnes à partir du précédent.
Histoire
Le carré SATOR figuré ci-contre, datant de l'antiquité, d'ordre 5 mais faisant intervenir plus de 5 caractères, n'est pas un carré latin au sens ci-dessus.
Le mathématicien coréen Choi Seok-jeong fut le premier en 1700 à publier un exemple de carré latin d'ordre neuf, afin de construire un carré magique[1].
67 ans plus tard, le mathématicien suisse Leonhard Euler (1707 - 1783) a débuté l'étude des carrés latins, qu'il a ainsi nommés car il utilisait des caractères latins pour les écrire[2],[3],[4].
Aujourd'hui, le carré latin est très populaire sous la forme du Sudoku[3].
En mathématiques
En permutant deux lignes ou deux colonnes d'un carré latin, on obtient encore un carré latin.
À une bijection près sur les n éléments, et à des permutations près sur les lignes et les colonnes, il n'existe qu'un seul carré latin d'ordre 3
Carré latin correspondant au groupe cyclique (Z/3Z; +) |
|
En revanche il existe deux carrés latins d'ordre 4 (si l'on ne tient pas compte des permutations ou des éventuelles bijections sur les n éléments) :
Carré latin correspondant au groupe cyclique (Z/4Z; +) |
|
Carré latin correspondant au groupe de Klein |
|
Les carrés latins sont les tables de Cayley de quasigroupes finis et ont un lien étroit avec les carrés magiques.
En littérature
L'écrivain Georges Perec a utilisé le carré latin comme ossature de deux de ses œuvres : La Vie mode d'emploi (ordre 10) et Lieux (ordre 12).
Héraldique
Un carré latin d'ordre 3 apparaît dans le blason de la Société statistique du Canada[5] ainsi que dans le logo de la Société biométrique internationale[6].
Références
- (en) Colbourn, Charles J.; Dinitz, Jeffrey H., Handbook of Combinatorial Designs, CRC Press., , p. 12
- L. Euler, Recherches sur une nouvelle espèce de quarrés magiques, E530, présenté à l'Académie de Saint-Pétersbourg le 8 mars 1779. Fait remarquable, cet article d'Euler est écrit en français, et est le seul publié dans un journal néerlandais (en 1782).
- Sudoku Anleitung
- (en) Wallis, W. D.; George, J. C., Introduction to Combinatorics, CRC Press, (ISBN 978-1-4398-0623-4), p. 212
- Société statistique du Canada
- The International Biometric Society
Voir aussi
Articles connexes
- Carré magique
- Carré gréco-latin - la combinaison de deux carrés latins orthogonaux
- Échantillonnage par hypercube latin
- Matrice (mathématiques)
- Sudoku (jeu qui s'inspire des carrés latins)
Lien externe
- Carrés latins et gréco-latins, un début vers les carrés magiques, sur villemin.gerard.free.fr