Latinski kvadrat

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Latínski kvadrát je n × n tabela (kvadratna shema oziroma matrika), napolnjena z n različnimi znaki, tako da se vsak znak pojavi le enkrat v vsaki vrstici in le enkrat v vsakem stolpcu. Na primer latinska kvadrata reda 3 in 4:


\begin{bmatrix}
 1 & 2 & 3 \\
 2 & 3 & 1 \\
 3 & 1 & 2 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
 a & b & d & c \\
 b & c & a & d \\
 c & d & b & a \\
 d & a & c & b
\end{bmatrix}

Latinski kvadrati se pojavljajo kot množitvene tabele (Cayleyjeve tabele) kvazigrupe. Teorija latinskih kvadratov in teorija kvazigrup sta medsebojno povezani. Uporabljajo se pri (statističnem) načrtovanju (organizaciji) preskusov. Latinski kvadrati so poseben primer latinskih pravokotnikov.

Ime je med prvimi uporabljal Leonhard Euler, ki je za znake uporabljal latinične črke.

Latinski kvadrat je skrčen (reduciran, oziroma normaliziran ali v standardni obliki), če sta prva vrstica in prvi stolpec naravno urejena. Prvi latinski kvadrat zgoraj je skrčen, ker sta prva vrstica in stolpec urejena po vrsti 1, 2, 3. Vsak latinski kvadrat lahko s permutacijami prevedemo na skrčeno obliko.

Zapis v obliki pravokotne vrste[uredi | uredi kodo]

Če vsak element n × n latinskega kvadrata zapišemo kot trojico (r,c,s), kjer je r vrstica, c stolpec in s znak, dobimo množico n2 trojk, ki se imenuje zapis kvadrata v obliki pravokotne vrste. Takšen zapis zgornjega prvega latinskega kvadrata je

{ (1,1,1),(1,2,2),(1,3,3),(2,1,2),(2,2,3),(2,3,1),(3,1,3),(3,2,1),(3,3,2) },

kjer, na primer, trojka (2,3,1) pomeni, da se v 2. vsrtici in 3. stolpcu nahaja znak 1. Definicijo latinskega kvadrata lahko v takšnem zapisu potem zapišemo:

  • Obstaja n2 trojk oblike (r,c,s), kjer je 1 ≤ r, c, sn.
  • Različni so vsi pari (r,c), (r,s) kakor tudi (c,s).

Ortogonalnost latinskih kvadratov sta prva raziskovala Donald Knuth in Radž Čandra Bose.

Ekvivalenčni razredi latinskih kvadratov[uredi | uredi kodo]

Veliko operacij na latinskem kvadratu da nov latinski kvadrat. Ena izmed njih je, če ga obrnemo.

Če permutiramo vrstice, stolpce ali imena znakov nekega latinskega kvadrata, dobimo nov latinski kvadrat, ki je izotopičen prvemu. Izotopizem je ekvivalenčna relacija in je množica latinskih kvadratov razdeljena na podmnožice, ki se imenujejo izotopični razredi. Dva latinska kvadrata v istem razredu sta izotopična, v različnih razredih pa nista.

Drugo vrsto operacije lahko najlaže pojasnimo z zapisom v obliki pravokotne vrste. Če na novo sistematično in skladno razvrstimo tri elemente v vsaki trojki, dobimo novo pravokotno vrsto in z njo nov latinski kvadrat. Lahko na primer zamenjamo vsako trojko (r,c,s) s (c,r,s), ki odgovarja preslikavi prek glavne diagonale. Lahko tudi zamenjamo vsako trojko (r,c,s) s (c,s,r) kar je že bolj zapletena operacija. Vsega skupaj imamo 6 možnosti, med katere spada tudi prazna operacija in, ki da 6 latinskih kvadratov. Ti so konjugirani (tudi parastrofi) izvirnemu latinskemu kvadratu.

Končno lahko združimo ti dve ekvivalenčni operaciji: dva latinska kvadrata sta paratopična, oziroma izotopična glede na glavni razred, če je eden od njiju izotopičen konjugiranemu drugemu. To je spet ekvivalenčna relacija z ekvivalenčnimi razredi, ki se imenujejo glavni razredi, oziroma paratopični razredi. Vsak glavni razred vsebuje do 6 izotopičnih razredov.

Število latinskih kvadratov[uredi | uredi kodo]

Ne obstaja lahko izračunljiva enačba za število n × n latinskih kvadratov z znaki 1,2,...,n. Tudi najboljše ocene za velike n so zelo grobe. Tu so podane vse znane natančne vrednosti. Število narašča zelo hitro.

Za vsak n je število vseh latinskih kvadratov (OEIS A002860) enako n! (n-1)! krat število skrčenih latinskih kvadratov (OEIS A000315).

Število latinskih kvadratov različnih velikosti
n skrčeni latinski kvadrati reda n vsi latinski kvadrati reda n
1 1 1
2 1 2
3 1 12
4 4 576
5 56 161280
6 9408 812851200
7 16942080 61479419904000
8 535281401856 108776032459082956800
9 377597570964258816 5524751496156892842531225600
10 7580721483160132811489280 9982437658213039871725064756920320000
11 5363937773277371298119673540771840 776966836171770144107444346734230682311065600000

Za vsak n vsak izotopičen razred (OEIS A040082) vsebuje do (n!)3 latinskih kvadratov (natančno število se spreminja), vsak glavni razred (OEIS A003090) vsebuje 1, 2, 3 ali 6 izotopskih razredov.

Ekvivalenčni razredi latinskih kvadratov
n glavni razredi izotopski razredi
1 1 1
2 1 1
3 1 1
4 2 2
5 2 2
6 12 22
7 147 564
8 283657 1676267
9 19270853541 115618721533
10 34817397894749939 208904371354363006

Primeri[uredi | uredi kodo]

Primeri latinskih kvadratov vsakega glavnega razreda do reda 5.


\begin{bmatrix}
 1
\end{bmatrix}
\quad
\begin{bmatrix}
 1 & 2 \\
 2 & 1
\end{bmatrix}
\quad
\begin{bmatrix}
 1 & 2 & 3 \\
 2 & 3 & 1 \\
 3 & 1 & 2
\end{bmatrix}



\begin{bmatrix}
 1 & 2 & 3 & 4 \\
 2 & 1 & 4 & 3 \\
 3 & 4 & 1 & 2 \\
 4 & 3 & 2 & 1 
\end{bmatrix}
\quad
\begin{bmatrix}
 1 & 2 & 3 & 4 \\
 2 & 4 & 1 & 3 \\
 3 & 1 & 4 & 2 \\
 4 & 3 & 2 & 1 
\end{bmatrix}



\begin{bmatrix}
 1 & 2 & 3 & 4 & 5 \\
 2 & 3 & 5 & 1 & 4 \\
 3 & 5 & 4 & 2 & 1 \\
 4 & 1 & 2 & 5 & 3 \\
 5 & 4 & 1 & 3 & 2 
\end{bmatrix}
\quad
\begin{bmatrix}
 1 & 2 & 3 & 4 & 5 \\
 2 & 4 & 1 & 5 & 3 \\
 3 & 5 & 4 & 2 & 1 \\
 4 & 1 & 5 & 3 & 2 \\
 5 & 3 & 2 & 1 & 4
\end{bmatrix}

Latinski kvadrati in matematične uganke[uredi | uredi kodo]

Priljubljena logična uganka sudoku je poseben primer latinskih kvadratov. Vsaka rešitev uganke sudoku je latinski kvadrat. V uganki Sudoku je še dodatna omejitev: manjši 3 × 3 kvadrati morajo spet vsebovati števke 1–9 (v običajni različici).

Vsak magični kvadrat je tudi latinski kvadrat, obratno pa ne velja.

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]