Латинський квадрат

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Латинським квадратом в математиці називається таблиця розміру n × n заповнена n різними елементами так, що в кожному стовпці і кожному рядку всі елементи зустрічаються по одному разу. Прикладом латинського квадрата може бути:


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

Будь-який латинський квадрат є таблицею множення квазігрупи. Якщо в першому рядку і в першому стовпці елементи йдуть у зростаючому порядку (як у поданому вище прикладі), то такий квадрат називається нормалізованим. Очевидно, що будь-який квадрат можна звести до нормалізованого за допомогою перестановки рядків і стовпців.

Ортогональне представлення[ред.ред. код]

Кожен латинський квадрат розмірності n може бути записаний за допомогою трійок (r,c,s), де r -номер рядка, c -номер стовпця,s - елемент. Для поданого вище латинського квадрата маємо представлення: { (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) } За допомогою ортогонального представлення можна дати визначення латинського квадрата:

  • Латинський квадрат це система n2 трійок (r,c,s), де 1 ≤ r, c, s ≤ n.
  • Всі пари (r,c) є відмінні, всі пари (r,s) є відмінні, всі пари (c,s) є відмінні.

Класи еквівалентності[ред.ред. код]

Якщо один латинський квадрат одержується з іншого перестановкою рядків стовпців і перепозначенням елементів то такі квадрати називаються ізотопними. Відношення ізотопності є відношенням еквівалентності і розбиває множину латинських квадратів на класи ізотопності. Якщо в ортогональному запису до всіх трійок застосувати одну перестановку то одержимо інший квадрат який називають спряженим до попереднього. Поєднавши відношення ізотопності і спряженості одержимо відношення паратопності, класи розбиття якого також називають головними

Кількість латинських квадратів[ред.ред. код]

Зараз невідома точна формула для визначення кількості різних латинських квадратів певного порядку. Однією з формул, що обчислює межі для можливої кількості є формула Ван Лінта - Вілсона:

 \prod_{k=1}^n \left(k!\right)^{n/k}\geq L(n)\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}

У наступній формулі подані відомі тепер[Коли?] результати щодо кількості латинських квадратів:

Кількість латинських квадратів
n нормалізовані латинські квадрати всі латинські квадрати 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
Класи еквівалентності латинських квадратів
n головні класи класи ізотопії
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

Ортогональні латинські квадрати[ред.ред. код]

Два латинських квадрати називаються ортогональними, якщо всі пари символів (a,b), де a — символ в деякій клітинці першого квадрата, а b — символ в тій же клітинці другого квадрата є всі різні. Прикладом ортогональних квадратів є:


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

Неважко переконатись, що всі пари відповідних елементів є різні:

\begin{bmatrix}
11 & 22 & 33\\
23 & 31 & 12\\
32 & 13 & 21\\
\end{bmatrix}

Ортогональні латинські квадрати існують для всіх n крім 2 і 6. Якщо в кожній діагоналі латинського квадрата всі елементи різні, такий латинський квадрат називаеться діагональним. Пари ортогональних діагональних латинських квадратів існують для всіх n, крім 2, 3 і 6. Прикладом ортогональних діагональних латинських квадратів може бути:


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

Квадрат із пар елементів двох ортогональних латинських квадратів називається греко-латинським квадратом.

Застосування в статистиці[ред.ред. код]

Латинські квадрати мають широке застосування в області планування експериментів. Нехай потрібно провести декілька експериментів, що залежать від трьох параметрів 1≤a,b,cn, так щоб для кожної пари були випробувані всі n² варіантів. Тоді необхідно взяти деякий латинський квадрат порядку n і провести n² експериментців з параметрами a = номер рядка, b = номер стовпця, c = значення у відповідній клітині латинського квадрата.

Література[ред.ред. код]

  • J.H. van Lint, R.M. Wilson: A Course in Combinatorics. Cambridge University Press 1992,ISBN 0-521-42260-4
  • C.F.Laywine,G.L.Mullen: Discrete MathematicsUsing Latin Squares. Wiley & sons inc. 1998, ISBN 0-471-24064-8