Latinský čtverec

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Barevně kódovaný latinský čtverec v okně na Cambridgeské univerzitě

Latinský čtverec je čtvercová tabulka o n\times n polích, která je vyplněna n různými symboly tak, že v každém řádku i v každém sloupci se každý symbol nachází právě jednou. Například tabulka


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

je latinským čtvercem.

Jméno latinský čtverec bylo zavedeno Leonhardem Eulerem. Jediným důvodem bylo, že jako symboly používal písmena latinky.

Na latinské čtverce lze nahlížet jako na multiplikační tabulky kvazigrup. Latinské čtverce se používají při konstrukci samoopravných kódů a také jsou základem matematických hádanek (například sudoku).

Ortogonální latinské čtverce[editovat | editovat zdroj]

Dvojice latinských čtverců (stejně velkých, nad stejnými symboly) jsou vzájemně ortogonálními latinskými čtverci, pokud

  • Každý z nich je sám o sobě latinským čtvercem

a

  • Pro každou dvojici symbolů A, B existuje právě jedna souřadnice  [i,j]:, i,j \in {1..n} taková, že v prvním čtverci je na místě [i,j] symbol A a ve druhém na tomtéž místě B. Názorněji řečeno, překryjeme-li jeden čtverec druhým k němu ortogonálním, bude právě na jednom místě "A překryté A-čkem", na jediném místě "A překryté B-čkem" atd.

Počet latinských čtverců velikosti n[editovat | editovat zdroj]

Počet latinských čtverců  L(n) velikosti  n nad symboly  1,2...n stále není znám ani v asymptotickém odhadu. Posloupnosti vyčíslující  L(n) je vyhrazena sekvence č. A002860 na oesis.org, hodnoty jsou však stále známy jen pro  n=1..11 , a sice  L(n)= 1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800, 5524751496156892842531225600, 9982437658213039871725064756920320000, 776966836171770144107444346734230682311065600000 Platí asymptotické odhady


 \left(\frac{n}{e^{2}}\right)^{n^{2}}\leq L(n)\leq e\left(\frac{n!}{e}\right)^{n}

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Latin square na anglické Wikipedii.

Externí reference[editovat | editovat zdroj]