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

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

${\displaystyle {\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) } За допомогою ортогонального представлення можна дати визначення латинського квадрата:

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

Класи еквівалентності

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

Кількість латинських квадратів

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

${\displaystyle \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 — символ в тій же клітинці другого квадрата є всі різні. Прикладом ортогональних квадратів є:

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

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

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

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

${\displaystyle {\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,c≤n, так щоб для кожної пари були випробувані всі n² варіантів. Тоді необхідно взяти деякий латинський квадрат порядку n і провести n² експериментців з параметрами a = номер рядка, b = номер стовпця, c = значення у відповідній клітині латинського квадрата.

Література

• J.H. van Lint, R.M. Wilson: A Course in Combinatorics. Cambridge University Press 1992,
• C.F.Laywine,G.L.Mullen: Discrete MathematicsUsing Latin Squares. Wiley & sons inc. 1998,
• Denes J., Keedwell A.D. Latin squares and their applications. Budapest: Academiai Kiado, 1974. 547p.
• Маркова Е. Д. Руководство по применению латинских планов при планировании эксперимента с качественнями факторами. Челябинск:Южно-Урал. кн. изд--во, 1971. 156с.
• Белоусов В.Д. Элементы теории квазигрупп. Кишинев 1981