Латинський квадрат
Латинським квадратом в математиці називається таблиця розміру n × n заповнена n різними елементами так, що в кожному стовпці і кожному рядку всі елементи зустрічаються по одному разу. Прикладом латинського квадрата може бути:
Будь-який латинський квадрат є таблицею множення квазігрупи. Якщо в першому рядку і в першому стовпці елементи йдуть у зростаючому порядку (як у поданому вище прикладі), то такий квадрат називається нормалізованим. Очевидно, що будь-який квадрат можна звести до нормалізованого за допомогою перестановки рядків і стовпців.
Ортогональне представлення[ред. | ред. код]
Кожен латинський квадрат розмірності 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) є відмінні.
Класи еквівалентності[ред. | ред. код]
Якщо один латинський квадрат одержується з іншого перестановкою рядків стовпців і перепозначенням елементів то такі квадрати називаються ізотопними. Відношення ізотопності є відношенням еквівалентності і розбиває множину латинських квадратів на класи ізотопності. Якщо в ортогональному запису до всіх трійок застосувати одну перестановку то одержимо інший квадрат який називають спряженим до попереднього. Поєднавши відношення ізотопності і спряженості одержимо відношення паратопності, класи розбиття якого також називають головними
Кількість латинських квадратів[ред. | ред. код]
Зараз невідома точна формула для визначення кількості всіх нормалізованих латинських квадратів порядку n. Щоб визначити загальну кількість латинських квадратів порядку n, треба кількість всіх нормалізованих латинських квадратів помножених на n!(n-1)!. Однією з формул, що обчислює межі для можливої кількості є формула Ван Лінта - Вілсона:
У наступній формулі подані відомі тепер[коли?] результати щодо кількості латинських квадратів:
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 — символ в тій же клітинці другого квадрата є всі різні. Прикладом ортогональних квадратів є:
Неважко переконатись, що всі пари відповідних елементів є різні:
Ортогональні латинські квадрати існують для всіх n крім 2 і 6. Якщо в кожній діагоналі латинського квадрата всі елементи різні, такий латинський квадрат називається діагональним. Пари ортогональних діагональних латинських квадратів існують для всіх n, крім 2, 3 і 6. Прикладом ортогональних діагональних латинських квадратів може бути:
Квадрат із пар елементів двох ортогональних латинських квадратів називається греко-латинським квадратом.
Застосування в статистиці[ред. | ред. код]
Латинські квадрати мають широке застосування в області планування експериментів. Нехай потрібно провести декілька експериментів, що залежать від трьох параметрів 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,ISBN 0-521-42260-4
- C.F.Laywine,G.L.Mullen: Discrete MathematicsUsing Latin Squares. Wiley & sons inc. 1998, ISBN 0-471-24064-8
- Denes J., Keedwell A.D. Latin squares and their applications. Budapest: Academiai Kiado, 1974. 547p.
- Маркова Е. Д. Руководство по применению латинских планов при планировании эксперимента с качественнями факторами. Челябинск:Южно-Урал. кн. изд--во, 1971. 156с.
- Белоусов В.Д. Элементы теории квазигрупп. Кишинев 1981
|
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |