Latinský čtverec

Barevně kódovaný latinský čtverec v okně na Cambridgeské univerzitě

Latinský čtverec je čtvercová tabulka o ${\displaystyle n\times n}$ polích, která je vyplněna ${\displaystyle 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

${\displaystyle {\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

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 ${\displaystyle [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

Počet latinských čtverců ${\displaystyle L(n)}$ velikosti ${\displaystyle n}$ nad symboly ${\displaystyle 1,2...n}$ stále není znám ani v asymptotickém odhadu. Posloupnosti vyčíslující ${\displaystyle L(n)}$ je vyhrazena sekvence č. A002860 na oeis.org,Posloupnost A002860 v databázi On-Line Encyclopedia of Integer Sequences hodnoty jsou však stále známy jen pro ${\displaystyle n=1..11}$, a sice ${\displaystyle L(n)=}$ 1, 2, 12, 576, 161280, 812851200, 61479419904000, 108776032459082956800, 5524751496156892842531225600, 9982437658213039871725064756920320000, 776966836171770144107444346734230682311065600000. Platí asymptotické dolní a horní meze:^[1]

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

Odkazy

Reference

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

1. KUČERA, Luděk; NEŠETŘIL, Jaroslav. Algebraické metody diskrétní matematiky. [s.l.]: [s.n.] ISBN 80-03-00107-2. 

Externí odkazy

• Obrázky, zvuky či videa k tématu latinský čtverec na Wikimedia Commons