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

Ю. Криворучко

Послідовно розвинено метод класифікації латинських квадратів. Виконано повний аналіз квадратів до 7 порядку включно. Розглянуто деякі супутні питання. Автор висловлює щиру подяку другу і однокурснику Сергію Негоді за моральну підтримку, цінні поради і за допомогу в складанні списку літератури. Без його підтримки ця робота не могла бути завершена.

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

Означення 1.

Латинським квадратом порядку n називають квадратну таблицю

, заповнену n різними числами так, що кожний рядок та кожний стовбчик містить всі числа.

Як правило, будемо використовувати натуральні числа від 1 до n.

Латинські квадрати мають багато цікавих властивостей. Ми розглядатимемо переважно ті властивості, які можуть бути корисними для класифікації.

Зрозуміло, що будь-яка перестановка рядків і/або стовбчиків латинського квадрату, а також повороти, центральна та осьові симетрії утворюють знову латинський квадрат.

Означення 2.

Латинські квадрати називають еквівалентними, якщо вони переходять один в одний деякою перестановкою рядків і стовбчиків.

Отже, наше найперше питання — скільки існує попарно не еквівалентних латинских квадратів порядку n? Відповісти на це питання в загальному випадку дуже важко. Розглянемо окремі приклади.

Для

існує лише один (тривіальний) латинський квадрат.

Для

існує 2 еквівалентних квадрати:

1	2		2	1
2	1		1	2

Вони мають по дві осьові (відносно діагоналей) та центральну симетрію.

Для

існує 12 латинських квадратів:

1 2 3 1 3 2 1 2 3 1 3 2 2 1 3 2 1 3

2 3 1 2 1 3 3 1 2 3 2 1 1 3 2 3 2 1

3 1 2 3 2 1 2 3 1 2 1 3 3 2 1 1 3 2

2 1 3 2 3 1 3 1 2 3 2 1 3 2 1 3 1 2

1 3 2 1 2 3 1 2 3 2 1 3 1 3 2 2 3 1

3 2 1 3 1 2 2 3 1 1 3 2 2 1 3 1 2 3

Покажемо, що всі вони еквівалентні. Справді, візьмемо довільний латинський квадрат

. Переставимо стовбчики так, що перший рядок містив числа 1,2,3 в порядку зростання. Потім переставимо рядки, щоб перший стовбчик містив числа 1,2,3 в порядку зростання. Інші клітинки заповнюються єдиним способом:

1 2 3

2 3 1

3 1 2

Отже, всі квадрати зводяться до одного варіанту. Цей квадрат має лише одну осьову симетрію по головній діагоналі.

Теорема 1.

Латинський квадрат розміром

при непарному n може мати не більше одної осьової симетрії. Центральну симетрію можуть мати лише квадрати парних розмірів.

Справді, припустимо, що квадрат має обидві осьові симетрії. Їх композиція утворює центральну симетрію. Розглянемо клітинку, що стоїть у середині першого рядка. Центрально-симетричною до неї буде клітинка в середині останнього рядка, тобто в тому самому стовпчику. Але за означенням, всі числа в стовбчику мають бути різними. Отже, такий квадрат не є латинським.

Теорему доведено.

Введемо ще одне

Означення 3.

Базовим латинським квадратом називатимемо такий квадрат, в якому перший рядок і перший стовбчик містять числа у порядку зростання.

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

Отже, кількість всіх латинських квадратів

разів більше, ніж базових.

Для

, як легко пересвідчитись, існує 4 базових латинських квадрати, або всього

варіантів.

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

1. 2 1 4 3 2. 2 1 4 3 3. 2 3 4 1 4. 2 4 1 3

3 4 1 2 3 4 2 1 3 4 1 2 3 1 4 2

4 3 2 1 4 3 1 2 4 1 2 3 4 3 2 1

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

Це спостереження дає нам ще декілька означень.

Означення 4.

Два латинських квадрати назвемо суміжними, якщо вони відрізняються лише клітинками, які самі утворюють латинський квадрат меншого порядку.

Означення 5.

Латинський квадрат назвемо первісним, якщо з нього не можна утворити квадрат меншого порядку (більшого 1), викресливши деякі рядки та стовбчики.

Квадрати порядку 2 і 3 є первісними. первісних квадратів порядку 4 не існує. Всі квадрати до 4-го порядку є однотипними. Різних квадратів розміру 4 (з точністю до еквівалентності) є всього 4.

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

Теорема 2.

Порядок підквадратів будь-якого латинського квадрату порядку n не перевищує

Доведення. Нехай даний квадрат має підквадрат порядку k. Викреслимо всі рядки, крім тих, що містять цей підквадрат, і всі стовчики, які його утворюють. Залишиться прямокутник розміром (n-k)*k. Кожний рядок цього прямокутника містить n-k різних чисел, яких нема у підквадраті. Якщо k> n:2 , то k> n-k . За принципом Діріхле кожен стовбчик прямокутника містить принаймні 2 однакових числа. Але тоді квадрат не є латинським. Теорему доведено.

Для 5x5 iснує 56 базових латинських квадратів. Ось вони:

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 1 4 5 3 2 1 4 5 3 2 1 5 3 4 2 1 5 3 4

1. 3 4 5 2 1 2. 3 4 5 1 2 3. 3 4 1 5 2 4. 3 4 2 5 1

4 5 1 3 2 4 5 2 3 1 4 5 2 1 3 4 5 1 2 3

5 3 2 1 4 5 3 1 2 4 5 3 4 2 1 5 3 4 1 2

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 1 4 5 3 2 1 4 5 3 2 1 5 3 4 2 1 5 3 4

5. 3 5 1 2 4 6. 3 5 2 1 4 7. 3 5 4 2 1 8. 3 5 4 1 2

4 3 5 1 2 4 3 5 2 1 4 3 1 5 2 4 3 2 5 1

5 4 2 3 1 5 4 1 3 2 5 4 2 1 3 5 4 1 2 3

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 3 4 5 1 2 3 4 5 1 2 3 5 1 4 2 3 5 1 4

9. 3 1 5 2 4 10. 3 1 5 2 4 11. 3 1 4 5 2 12. 3 1 4 5 2

4 5 1 3 2 4 5 2 1 3 4 5 1 2 3 4 5 2 3 1

5 4 2 1 3 5 4 1 3 2 5 4 2 3 1 5 4 1 2 3

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 3 1 5 4 2 3 1 5 4 2 3 4 5 1 2 3 5 1 4

13. 3 4 5 1 2 14. 3 4 5 2 1 15. 3 4 5 1 2 16. 3 4 1 5 2

4 5 2 3 1 4 5 2 1 3 4 5 1 2 3 4 5 2 3 1

5 1 4 2 3 5 1 4 3 2 5 1 2 3 4 5 1 4 2 3

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 3 5 1 4 2 3 5 1 4 2 3 1 5 4 2 3 1 5 4

17. 3 4 2 5 1 18. 3 4 2 5 1 19. 3 5 4 1 2 20. 3 5 4 2 1

4 5 1 2 3 4 5 1 3 2 4 1 5 2 3 4 1 5 3 2

5 1 4 3 2 5 1 4 2 3 5 4 2 3 1 5 4 2 1 3

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 5 1 4

21. 3 5 1 2 4 22. 3 5 2 1 4 23. 3 5 2 1 4 24. 3 5 4 2 1

4 1 5 3 2 4 1 5 2 3 4 1 5 3 2 4 1 2 5 3

5 4 2 1 3 5 4 1 3 2 5 4 1 2 3 5 4 1 3 2

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 4 1 5 3 2 4 5 1 3 2 4 5 3 1 2 4 5 3 1

25. 3 1 5 2 4 26. 3 1 2 5 4 27. 3 1 2 5 4 28. 3 1 4 5 2

4 5 2 3 1 4 5 1 3 2 4 5 1 2 3 4 5 1 2 3

5 3 4 1 2 5 3 4 2 1 5 3 4 1 2 5 3 2 1 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 4 5 1 3 2 4 5 3 1 2 4 1 5 3 2 4 1 5 3

29. 3 1 4 5 2 30. 3 1 4 5 2 31. 3 5 2 1 4 32. 3 5 4 2 1

4 5 2 3 1 4 5 2 1 3 4 1 5 3 2 4 1 5 3 2

5 3 1 2 4 5 3 1 2 4 5 3 4 2 1 5 3 2 1 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 4 5 3 1 2 4 5 3 1 2 4 1 5 3 2 4 1 5 3

33. 3 5 1 2 4 34. 3 5 4 1 2 35. 3 5 2 1 4 36. 3 5 4 1 2

4 1 2 5 3 4 1 2 5 3 4 3 5 2 1 4 3 5 2 1

5 3 4 1 2 5 3 1 2 4 5 1 4 3 2 5 1 2 3 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 4 1 5 3 2 4 5 1 3 2 4 5 3 1 2 4 5 1 3

37. 3 5 4 2 1 38. 3 5 1 2 4 39. 3 5 2 1 4 40. 3 5 4 2 1

4 3 5 1 2 4 3 2 5 1 4 3 1 5 2 4 3 1 5 2

5 1 2 3 4 5 1 4 3 2 5 1 4 2 3 5 1 2 3 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 5 1 3 4 2 5 4 1 3 2 5 4 3 1 2 5 4 1 3

41. 3 1 4 5 2 42. 3 1 2 5 4 43. 3 1 2 5 4 44. 3 1 5 2 4

4 3 5 2 1 4 3 5 2 1 4 3 5 1 2 4 3 1 5 2

5 4 2 1 3 5 4 1 3 2 5 4 1 2 3 5 4 2 3 1

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 5 4 3 1 2 5 4 1 3 2 5 1 3 4 2 5 1 3 4

45. 3 1 5 2 4 46. 3 1 5 2 4 47. 3 4 2 5 1 48. 3 4 5 1 2

4 3 1 5 2 4 3 2 5 1 4 1 5 2 3 4 1 2 5 3

5 4 2 1 3 5 4 1 3 2 5 3 4 1 2 5 3 4 2 1

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 5 1 3 4 2 5 4 3 1 2 5 4 1 3 2 5 4 3 1

49. 3 4 5 2 1 50. 3 4 1 5 2 51. 3 4 2 5 1 52. 3 4 5 1 2

4 1 2 5 3 4 1 5 2 3 4 1 5 3 2 4 1 2 5 3

5 3 4 1 2 5 3 2 1 4 5 3 1 2 4 5 3 1 2 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 5 1 3 4 2 5 1 3 4 2 5 4 1 3 2 5 4 1 3

53. 3 4 2 5 1 54. 3 4 5 1 2 55. 3 4 1 5 2 56. 3 4 5 2 1

4 3 5 1 2 4 3 2 5 1 4 3 5 2 1 4 3 1 5 2

5 1 4 2 3 5 1 4 2 3 5 1 2 3 4 5 1 2 3 4

Дослідження (яке легко провести на комп’ютері) показує, що серед цих квадратів є 6 первісних, які між собою не еквівалентні, а інші 50 мають по 4 підквадрати порядку 2, і діляться на 10 класів еквівалентності. Отже, існує всього 16 латинських квадратів порядку 5 з точністю до еквівалентності. Всього серед квадратів 5x5 існує 56*5!*4! = 161280 латинських квадратів.

Множина перестановок, які переводять даний квадрат сам у себе, утворює групу, яка є підгрупою S_n². Цю групу називатимемо групою симетрій латинського квадрата.

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

Теорема 3.

Група симетрій латинського квадрата порядку n містить не більше n елементів.

Доведення. Групи симетрій еквівалентних квадратів співпадають, кожен квадрат еквівалентний базовому, тому достатньо розглянути базові квадрати.

Будь-яка симетрія базового квадрату, очевидно, переводить його знову в базовий. Покажемо, що кількість перестановок, що переводять даний квадрат знову в базовий, не більше n. Справді, квадрат містить рівно n одиниць; Нехай деяка перестановка переводить одну з них в верхній лівий кут. Ті перестановки, що залишають верхній лівий кут на місці, не зачіпають першого рядка та першого стовбчика. Отже, такими перестановками можна лише єдиним способом розмістити числа у першому рядку та першому стовбчику у порядку зростання. Тому кількість перестановок, що переводять даний квадрат у базовий, дорівнює n. Отже, теорема доведена.

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

Групи симетрій квадратів порядку 4 мають по 4 елементи; для квадратів №№ 1,2,4 це група C₄², а для квадрату № 3 — група C₄.

Більшість квадратів порядку 5 не мають симетрії, а решта мають групу симетрій C₄.

В латинських квадратах можна переставляти не лише рядки й стовбчики, а й значення.

Означення 6.

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

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

Теорема 4.

Множина ізоморфізмів, які переводять даний латинський квадрат в еквівалентний, утвоює групу, яка є підгрупою всіх перестановок S_n. Таку групу називаємо групою ізоморфізмів латинського квадрату.

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

Базовий квадрат № 1 четвертого порядку утворює групу ізоморфізмів S₄, яка складається з 24 елементів. Інші три базові квадрати 4-го порядку утворюють групу ізоморфізмів D₄ симетрій квадрата, яка складається з 8 елементів.

Квадрати 5-го порядку також утворюють дві різні групи ізоморфізмів: симетричні — групу з 20 елементів, структура якої показана у таблиці, всі інші — знакозмінну групу A₄, яка містить 12 елементів.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

1 1 3 0 2 8 11 9 10 16 18 17 19 4 5 7 6 12 14 15 13

2 2 0 3 1 12 13 15 14 4 6 7 5 16 19 17 18 8 10 9 11

3 3 2 1 0 16 19 18 17 12 15 14 13 8 11 10 9 4 7 6 5

4 4 7 6 5 0 3 2 1 17 16 19 18 13 12 15 14 9 8 11 10

5 5 6 7 4 9 10 11 8 13 14 15 12 17 18 19 16 0 1 2 3

6 6 4 5 7 13 12 14 15 0 2 1 3 9 10 8 11 17 19 16 18

7 7 5 4 6 17 18 16 19 9 11 8 10 0 3 1 2 13 15 14 12

8 8 10 9 11 1 2 0 3 14 12 13 15 5 4 6 7 18 16 19 17

9 9 8 11 10 5 4 7 6 1 0 3 2 18 17 16 19 14 13 12 15

10 10 11 8 9 14 15 12 13 18 19 16 17 1 2 3 0 5 6 7 4

11 11 9 10 8 18 17 19 16 5 7 6 4 14 15 13 12 1 3 0 2

12 12 14 15 13 2 1 3 0 10 8 11 9 19 16 18 17 6 4 5 7

13 13 15 14 12 6 7 5 4 19 17 18 16 10 9 11 8 2 0 3 1

14 14 13 12 15 10 9 8 11 6 5 4 7 2 1 0 3 19 18 17 16

15 15 12 13 14 19 16 17 18 2 3 0 1 6 7 4 5 10 11 8 9

16 16 17 18 19 3 0 1 2 7 4 5 6 11 8 9 10 15 12 13 14

17 17 19 16 18 7 6 4 5 15 13 12 14 3 0 2 1 11 9 10 8

18 18 16 19 17 11 8 10 9 3 1 2 0 15 14 12 13 7 5 4 6

19 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Тут варто пригадати ще одне питання з теорії латинських квадратів, яке, щоправда, не має прямого відношення до їх класифікації, але тісно пов’язане з тими поняттями, які ми щойно ввели.

Означення 7.

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

Наведемо для прикладу ортогональні пари порядку 3 і 4.

1 2 3 3 2 1 1 2 3 4 3 2 4 1

2 3 1 1 3 2 2 1 4 3 1 4 2 3

3 1 2 2 1 3 3 4 1 2 2 3 1 4

4 3 2 1 4 1 3 2

Питанням існування ортогональних пар різних порядків займався ще Л. Ейлер. Так, він безуспішно намагався знайти ортогональну пару 6-го порядку. У ХХ ст. за допомогою комп’ютера було показано, що таких пар не існує; однак для інших порядків, більших 2 ортогональні пари існують.

Теорема 6.

Якщо в ортогональній парі замінити кожний з квадратів на ізоморфний до нього, утвориться знову ортогональна пара.

Доведення.

Заміна квадрата на ізоморфний означає застосування деякої перестановки до всіх елементів. Перестановка є бієктивним відбраженням, тобто однакові елементи переходять в однакові, різні — в різні. Звідси одразу випливає, що кількість різних пар відповідних елементів після заміни залишиться тою самою, тобто n². Саме це й потрібно було довести.

Перш ніж переходити до наступного порядку, зробимо таку побудову. Кожен рядок латинського квадрату є перестановкою n елементів. Запишемо навпроти кожного рядка знак «+», якщо відповідна перестановка парна, і «–», якщо вона непарна. Те саме зробимо зі стовбчиками. Нехай кількість плюсів у рядках дорівнює p, а у стовбчиках — q.

Означення 8.

Пару чисел (|n-2p|; |n-2g|) назвемо сигнатурою латинського квадрату.

Сигнатуру позначатимемо парою чисел без дужок через двокрапку: 5:5 або 2:4.

Зрозуміло, що парність сигнатури визначається парністю n.

Теорема 7.

Еквівалентні квадрати мають однакову сигнатуру. Тобто, сигнатура є інваріантом щодо перестановок.

Доведення. Будь-яка перестановка є суперпозицією з транспозицій сусідніх елементів. Отже, достатньо показати, що сигнатура не зміниться, якщо переставити два сусідніх рядки (або стовбчики). Справді, транспозиція є непарною перестановкою, тому перестановка двох рядків змінить парність всіх стовчиків на протилежну. Отже, кількість знаків «+» у стовбчиках стане n-g . Кількість знаків «+» у рядках не зміниться, оскільки ми рядки залишаємо без змін, лише міняємо їх місцями. Але |n-2(n-g)| = |n-2g|= | 2g-n| . Отже сигнатура не змінилася.

Теорему доведено.

Розберемо питання, як пов’язані між собою сигнатури суміжних квадратів. Якщо два латинських квадрати суміжні відносно підквадрату другого порядку, то рядки та стовбчики, які проходять через цей підквадрат, мають в них різну парність, а всі інші — однакову. Якщо при цьому в одному з квадратів два рядки, що проходять через підквадрат мають різну парність, то так само буде і в другому, і навпаки. Тому різниця кількості парних і непарних рядків суміжних квадратів або співпадає, або відрізняється на 2. Звідси, вираз під модулем в означенні означенні сигнатури або залишається незмінним, або змінюється на 4 в той чи інший бік. Причому перше можливо лише тоді, коли сигнатура відмінна від максимальної.

Так, наприклад, квадрат порядку 6 з сигнатурою 6:6 має суміжні квадрати лише з сигнатурою 2:2, а останні можуть мати крім того суміжні квадрати з сигнатурою 2:2 або 6:2. Квадрати 6-го порядку з сигнатурою 4 або 0 мають також сигнатуру 4 або 0. Квадрати 5-го порядку з сигнатурою 5:5 можуть мати суміжні лише з сигнатурою 1:1, але таких насправді не існує. Тому всі квадрати 5-го порядку з такою сигнатурою первісні.

Знайдемо сигнатури всіх розглянутих вище квадратів. Квадрат порядку 2 має сигнатуру 2:2. Квадрат порядку 3 має сигнатуру 3:3. Квадрати порядку 4 мають сигнатури: №1 — 4:4; №2 — 0:0; №3 — 0:0; №4 — 0:0; №4 — 0:0. Як бачимо, обчисливши сигнатури, ми можемо одразу зрозуміти, що квадрат №1 не еквівалентний до інших.

Квадрати порядку 5 мають сигнатуру 5:5, якщо вони симетричні, або 3:3, якщо вони не мають симетрії. Як бачимо, для квадратів порядку не більше 5 обидві цифри сигнатури однакові. Для більших порядків це вже не так. Але таких квадратів занадто багато, щоб наводити їх у цій статті; ми наведемо лише загальну статистику, зведену до таблиці.

Таблиця 1. Класифікація латинських квадратів порядку 6.

№ п/п Порядок симетрії Кількість підквадратів Сигнатура Група ізоморфізмів Базових варіантів, шт.

пор. 2 пор. 3

1 4 0 0:0 H₄ 1080

1 5 0 0:2 H₄ 1080

1 5 0 2:0 H₄ 1080

1 5 0 2:2 H₄ 1080

1 7 0 2:2 D₄ 540

1 7 0 2:4 D₄ 540

1 7 0 4:2 D₄ 540

1 9 4 0:6 пор. 36 120

1 9 4 6:0 пор. 36 120

1 11 0 4:4 H₄ 1080

1 15 0 0:4 D₆ 360

1 15 0 4:0 D₆ 360

1 15 0 4:6 пор. 120 36

1 15 0 6:4 пор. 120 36

1 15 0 6:6 пор. 120 36

2 9 0 0:0 D₆ 180

2 15 0 0:0 S₃ 360

2 19 0 0:0 H₄ 540

3 0 4 0:0 пор. 36 40

3 9 4 6:6 D₆ 120

6 9 4 0:0 D₆ 60

6 27 4 0:0 пор. 36 20

Всього 9408

Отже, всього існує 8088 несиметричних квадратів, 1080 квадратів із симетрією другого порядку, 160 квадратів із симетрією третього порядку, і 80 квадратів із симетрією 6-го порядку. Всьoго маємо з точністю до еквівалентності 1868= 8088:6 + 1080:3+160:2+80

квадратів. Всього різних квадратів існує 9408*6!*5! = 812851200.

Наведемо по одному прикладу для кожного типу.

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

2 1 4 6 3 5 2 1 4 3 6 5 2 1 4 5 6 3 2 1 4 5 6 3

1. 3 4 2 5 6 1 2. 3 4 5 6 2 1 3. 3 4 5 6 2 1 4. 3 4 2 6 1 5

4 5 6 2 1 3 4 5 6 1 3 2 4 3 6 2 1 5 4 5 6 2 3 1

5 6 1 3 2 4 5 6 1 2 4 3 5 6 1 3 4 2 5 6 1 3 4 2

6 3 5 1 4 2 6 3 2 5 1 4 6 5 2 1 3 4 6 3 5 1 2 4

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

2 1 4 5 6 3 2 1 5 6 4 3 2 1 4 6 3 5 2 1 4 3 6 5

5. 3 4 1 6 2 5 6. 3 4 1 5 6 2 7. 3 4 5 2 6 1 8. 3 4 5 6 1 2

4 5 6 1 3 2 4 3 6 1 2 5 4 5 6 1 2 3 4 5 6 1 2 3

5 6 2 3 4 1 5 6 4 2 3 1 5 6 2 3 1 4 5 6 1 2 3 4

6 3 5 2 1 4 6 5 2 3 1 4 6 3 1 5 4 2 6 3 2 5 4 1

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

2 1 4 5 6 3 2 1 5 6 3 4 2 1 5 6 4 3 2 1 5 6 3 4

9. 3 4 5 6 1 2 10. 3 4 1 5 6 2 11. 3 4 1 2 6 5 12. 3 4 1 2 6 5

4 3 6 1 2 5 4 3 6 1 2 5 4 3 6 5 2 1 4 3 6 5 2 1

5 6 1 2 3 4 5 6 4 2 1 3 5 6 2 3 1 4 5 6 4 3 1 2

6 5 2 3 4 1 6 5 2 3 4 1 6 5 4 1 3 2 6 5 2 1 4 3

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

2 1 5 6 3 4 2 1 5 6 4 3 2 1 4 5 6 3 2 1 4 3 6 5

13. 3 4 1 2 6 5 14. 3 4 1 5 6 2 15. 3 4 1 6 2 5 16. 3 4 5 6 1 2

4 5 6 1 2 3 4 3 6 1 2 5 4 5 6 1 3 2 4 3 6 5 2 1

5 6 4 3 1 2 5 6 2 3 1 4 5 6 2 3 1 4 5 6 1 2 4 3

6 3 2 5 4 1 6 5 4 2 3 1 6 3 5 2 4 1 6 5 2 1 3 4

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

2 1 5 6 3 4 2 1 5 6 3 4 2 3 1 6 4 5 2 1 4 5 6 3

17. 3 4 1 5 6 2 18. 3 4 1 2 6 5 19. 3 1 2 5 6 4 20. 3 4 5 6 1 2

4 3 6 2 1 5 4 3 6 5 2 1 4 5 6 2 3 1 4 5 6 3 2 1

5 6 4 1 2 3 5 6 2 1 4 3 5 6 4 1 2 3 5 6 1 2 3 4

6 5 2 3 4 1 6 5 4 3 1 2 6 4 5 3 1 2 6 3 2 1 4 5

1 2 3 4 5 6 1 2 3 4 5 6

2 1 4 3 6 5 2 1 5 6 3 4

21. 3 4 5 6 1 2 22. 3 4 1 2 6 5

4 3 6 5 2 1 4 3 6 5 1 2

5 6 1 2 3 4 5 6 2 1 4 3

6 5 2 1 4 3 6 5 4 3 2 1

Таблиця 2. Класифікація латинських квадратів порядку 7.

№ п/п Порядок симетрії Кількість підквадратів Група ізоморфізмів Сигнатура Базових варіантів, шт.

пор. 2 пор. 3

1 0 0 S₃ 5:5 5880

1 0 0 S₃ 7:5 i 5:7 11760

1 1 0 C₅ 5:5 14112

1 2 0 O 1:1 35280

1 2 0 C₂ 3:1 i 1:3 35280

1 2 0 C₂ 7:1 i 1:7 35280

1 2 0 C₂ 7:3 i 3:7 35280

1 3 0 O 3:3 70560

1 4 0 O 1:1 105840

1 4 0 C₂ 3:3 17640

1 4 0 C₂ 5:3 i 3:5 35280

1 4 0 O 5:5 35280

1 5 0 O 1:1 282240

1 5 0 O 3:1 i 1:3 352800

1 5 0 O 3:3 70560

1 5 0 O 5:1 i 1:5 70560

1 5 0 O 5:3 i 3:5 70560

1 6 0 O 1:1 70560

1 6 0 C₂ 1:1 17640

1 6 0 C₃ 1:1 11760

1 6 0 O 3:1 i 1:3 211680

1 6 0 C₂ 3:1 i 1:3 35280

1 6 0 O 3:3 35280

1 6 0 C₂ 3:3 35280

1 6 0 O 5:1 i 1:5 70560

1 6 0 C₂ 5:1 i 1:5 35280

1 6 0 O 5:3 i 3:5 141120

1 6 0 C₂ 7:1 i 1:7 35280

1 6 0 C₃ 7:1 i 1:7 23520

1 6 0 C₂ 7:3 i 3:7 105840

1 6 3 S₄ 5:5 1470

1 7 0 O 1:1 211680

1 7 0 O 3:1 i 1:3 493920

1 7 0 O 3:3 282240

1 7 0 O 5:1 i 1:5 211680

1 7 0 O 5:3 i 3:5 70560

1 8 0 O 1:1 458640

1 8 0 O 3:1 i 1:3 423360

1 8 0 C₂ 3:1 i 1:3 176400

1 8 0 O 3:3 70560

1 8 0 C₂ 3:3 70560

1 8 0 O 5:1 i 1:5 352800

1 8 0 C₂ 5:1 i 1:5 70560

1 8 0 O 5:3 i 3:5 141120

1 8 0 C₂ 5:3 i 3:5 35280

1 8 0 O 5:5 70560

1 8 0 C₂ 7:1 i 1:7 35280

1 8 0 C₂ 7:5 i 5:7 35280

1 9 0 O 1:1 317520

1 9 0 O 3:1 i 1:3 211680

1 9 0 O 3:3 105840

1 9 0 O 5:1 i 1:5 211680

1 9 0 O 5:5 35280

1 9 1 O 1:1 35280

1 10 0 O 1:1 1058400

1 10 0 C₂ 1:1 52920

1 10 0 O 3:1 i 1:3 1199520

1 10 0 C₂ 3:1 i 1:3 105840

1 10 0 O 3:3 141200

1 10 0 C₂ 3:3 88200

1 10 0 O 5:1 i 1:5 564480

1 10 0 C₂ 5:3 i 3:5 70560

1 10 0 O 5:5 70560

1 10 0 C₂ 7:3 i 3:7 70560

1 10 1 C₂ 1:1 17640

1 10 1 C₂ 3:1 i 1:3 35280

1 10 1 C₄ 3:3 8820

1 10 1 C₄ 5:3 i 3:5 17640

1 11 0 O 1:1 388080

1 11 0 O 3:1 i 1:3 211680

1 11 0 O 3:3 105840

1 12 0 O 1:1 670320

1 12 0 C₂ 1:1 17640

1 12 0 O 3:1 i 1:3 846720

1 12 0 C₂ 3:1 i 1:3 105840

1 12 0 O 3:3 388080

1 12 0 C₂ 3:3 35280

1 12 0 O 5:1 i 1:5 352800

1 12 0 C₂ 5:1 i 1:5 35280

1 12 0 O 5:3 i 3:5 70560

1 12 0 C₂ 7:1 i 1:7 35280

1 12 0 C₂ 7:3 i 3:7 35280

1 13 0 O 1:1 70560

1 14 0 O 1:1 705600

1 14 0 O 3:1 i 1:3 352800

1 14 0 C₂ 3:1 i 1:3 115840

1 14 0 O 3:3 70560

1 14 0 C₂ 3:3 52920

1 14 0 C₂ 5:1 i 1:5 35280

1 14 0 O 5:3 i 3:5 141120

1 14 0 C₂ 5:3 i 3:5 70560

1 14 0 O 5:5 35280

1 14 1 O 1:1 35280

1 14 1 C₂ 1:1 35280

1 14 1 O 5:1 i 1:5 70560

1 14 1 C₂ 5:1 i 1:5 35280

1 14 1 C₂ 7:1 i 1:7 35280

1 15 0 O 3:1 i 1:3 70560

1 15 0 O 3:3 35280

1 15 1 O 1:1 35280

1 16 0 O 1:1 317520

1 16 0 O 3:1 i 1:3 141120

1 16 0 O 5:1 i 1:5 211680

1 16 0 O 5:5 35280

1 16 0 C₅ 5:5 21168

1 16 1 O 1:1 105840

1 16 1 O 3:1 i 1:3 211680

1 18 0 O 1:1 70560

1 18 0 C₃ 1:1 11760

1 18 0 O 3:1 i 3:1 70560

1 18 0 O 5:1 i 1:5 141120

1 18 0 C₃ 5:1 i 1:5 23520

1 18 0 O 5:3 i 3:5 70560

1 18 0 C₃ 5:5 11760

1 18 1 O 1:1 35280

1 18 1 C₂ 1:1 52920

1 18 1 C₂ 3:3 52920

1 18 1 C₄ 5:5 8820

1 18 1 A₄ 7:7 2940

1 18 3 H₄ 1:1 8820

1 20 0 O 3:1 i 1:3 70560

1 20 0 O 3:3 35280

1 22 1 O 1:1 35280

1 22 1 O 3:1 i 1:3 70560

1 22 1 C₂ 3:3 17640

1 22 1 C₂ 5:3 i 3:5 35380

1 22 3 D₄ 3:3 4410

1 22 3 D₄ 5:3 i 3:5 8820

1 26 3 D₄ 1:1 4410

1 26 3 D₄ 7:1 i 1:7 8820

1 30 3 H₄ 3:3 8820

1 42 7 пор. 168 7:7 210

7 0 0 пор. 42 7:7 120

Всього 16942080

Як бачимо, лише 120 квадратів порядку 7 мають симетрію; всі вони первісні, і всі мають однакову сигнатуру 7:7. Всього маємо різних квадратів 16942080*7!*6! =61479419904000.

З точністю до еквівалентності маємо 16941960:7 + 120 = 2420400 шт.

В таблицях використано такі позначення груп:

О — тривіальна група з одного елемента; C_n — циклічна група n-го порядку; S_n — група перестановок n елементів; A_n — знакозмінна група; D_n — група симетрій правильного n-кутника; H₄ — група симетрій ромба. Для тих груп, які не належать до жодного з названих класів, вказаний лише порядок (кількість елементів).

Уважно розгянувши останню таблицю, можна помітити, що найбільша кількість квадратів кожного типу має тривіальну групу ізоморфізмів, причому ця кількість завжди кратна 7*7! = 35280. Для нетривіальних груп ізоморфізмів це вже не виконується. Пояснення цього явища дає наступна

Теорема 8.

Для кожного допустимого набору інваріантів з порядком симетрії p та групою ізоморфізмів порядку s кількість базових латинських квадратів порядку n кратна (n*n!)/(s*p).

Справді, візьмемо будь-який квадрат, що задовольняє умові теореми. Множина квадратів, ізоморфних даному має потужність n!, за умовою серед них s квадратів еквівалентні даному. Отже, цю множину можна розбити на n/s класів еквівалентності. Виберемо з кожного класу по одному квадрату. Ми знаємо, що для будь-якого квадрату існує рівно n еквівалентних перетворень, що утворюють базові квадрати. Оскільки за умовою ці квадрати мають порядок симетрії p, кожний варіант утворюється s різними перетвореннями. Отже, всього утворюється n/p еквівалентних базових квадратів з кожного класу еквівалентності. Таким чином, ми утворили (n*n!)/(s*p) базових квадратів з однаковим набором інваріантів; при чому з побудови випливає, що буть-який з цих квадратів утворює ту саму множину.

Теорема доведена.

Наведемо приклади.

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 3 4 7 1 5 6 2 3 4 5 6 7 1 2 1 4 5 6 7 3

3 1 5 2 6 7 4 3 1 5 2 7 4 6 3 4 5 7 2 1 6

1. 4 5 6 3 7 2 1 2. 4 5 6 7 3 1 2 3. 4 5 7 6 3 2 1

5 6 7 1 4 3 2 5 6 7 1 2 3 4 5 6 1 3 7 4 2

6 7 1 5 2 4 3 6 7 1 3 4 2 5 6 7 2 1 4 3 5

7 4 2 6 3 1 5 7 4 2 6 1 5 3 7 3 6 2 1 5 4

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 6 7 5 3 2 1 4 5 7 3 6 2 1 4 5 6 7 3

3 4 2 1 6 7 5 3 4 5 6 1 7 2 3 4 5 6 7 2 1

4. 4 5 1 7 2 3 6 5. 4 5 6 7 3 2 1 6. 4 3 6 7 2 1 5

5 6 7 2 3 1 4 5 6 7 3 2 1 4 5 6 7 1 4 3 2

6 7 5 3 4 2 1 6 7 2 1 4 5 3 6 7 1 2 3 5 4

7 3 6 5 1 4 2 7 3 1 2 6 4 5 7 5 2 3 1 4 6

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 6 3 7 5 2 1 4 6 3 7 5

3 4 5 6 2 7 1 3 4 5 7 6 1 2 3 4 2 1 7 5 6

7. 4 3 6 7 1 2 5 8. 4 5 1 3 7 2 6 9. 4 5 1 7 6 2 3

5 6 7 1 3 4 2 5 6 7 2 4 3 1 5 6 7 2 4 3 1

6 7 1 2 4 5 3 6 7 2 5 1 4 3 6 7 5 3 1 4 2

7 5 2 3 6 1 4 7 3 6 1 2 5 4 7 3 6 5 2 1 4

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 6 7 3 2 1 4 7 3 5 6 2 1 5 6 4 7 3

3 4 2 6 7 5 1 3 4 5 1 6 7 2 3 4 2 1 7 5 6

10. 4 5 1 7 3 2 6 11. 4 3 6 5 7 2 1 12. 4 3 6 7 1 2 5

5 6 7 3 4 1 2 5 6 7 3 2 1 4 5 6 7 2 3 4 1

6 7 5 2 1 3 4 6 7 1 2 4 3 5 6 7 1 5 2 3 4

7 3 6 1 2 4 5 7 5 2 6 1 4 3 7 5 4 3 6 1 2

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 7 6 3 5 2 1 4 5 6 7 3

3 4 2 6 1 7 5 3 4 5 1 7 2 6 3 4 5 1 7 2 6

13. 4 3 5 7 6 2 1 14. 4 3 6 5 1 7 2 15. 4 3 6 7 2 5 1

5 6 7 3 2 1 4 5 6 7 2 3 4 1 5 6 7 3 4 1 2

6 7 1 2 4 5 3 6 7 1 3 2 5 4 6 7 1 2 3 4 5

7 5 6 1 3 4 2 7 5 2 6 4 1 3 7 5 2 6 1 3 4

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 7 6 5 3 2 1 4 5 7 3 6

3 4 5 1 6 7 2 3 4 5 1 2 7 6 3 4 5 6 2 7 1

16. 4 3 6 7 1 2 5 17. 4 3 6 5 7 1 2 18. 4 3 6 7 1 2 5

5 6 7 3 2 4 1 5 6 7 2 3 4 1 5 6 7 3 4 1 2

6 7 1 2 4 5 3 6 7 1 3 4 2 5 6 7 1 2 3 5 4

7 5 2 6 3 1 4 7 5 2 6 1 3 4 7 5 2 1 6 4 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 7 3 5 6 2 1 4 6 7 5 3 2 1 4 5 3 7 6

3 4 2 6 7 1 5 3 4 2 5 1 7 6 3 4 5 7 6 2 1

19. 4 5 6 3 1 7 2 20. 4 5 1 7 6 3 2 21. 4 3 6 1 7 5 2

5 6 7 2 4 3 1 5 6 7 3 2 4 1 5 6 7 3 2 1 4

6 7 1 5 2 4 3 6 7 5 1 3 2 4 6 7 1 2 4 3 5

7 3 5 1 6 2 4 7 3 6 2 4 1 5 7 5 2 6 1 4 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 7 6 3 5 2 1 4 5 7 3 6 2 1 5 6 7 3 4

3 4 5 1 7 2 6 3 4 2 7 6 5 1 3 4 1 5 6 7 2

22. 4 3 6 5 1 7 2 23. 4 3 5 6 1 7 2 24. 4 3 6 7 2 1 5

5 6 7 3 2 4 1 5 6 7 1 3 2 4 5 6 7 2 3 4 1

6 7 1 2 3 5 4 6 7 1 3 2 4 5 6 7 2 1 4 5 3

7 5 2 6 4 1 3 7 5 6 2 4 1 3 7 5 4 3 1 2 6

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 5 7 3 6 2 1 4 5 3 7 6

3 4 2 6 1 7 5 3 4 5 1 6 7 2 3 4 2 7 6 1 5

25. 4 3 5 7 6 2 1 26. 4 3 6 7 2 5 1 27. 4 3 5 6 7 2 1

5 6 7 1 2 4 3 5 6 7 2 3 1 4 5 6 7 1 2 3 4

6 7 1 2 3 5 4 6 7 1 3 4 2 5 6 7 1 2 4 5 3

7 5 6 3 4 1 2 7 5 2 6 1 4 3 7 5 6 3 1 4 2

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 6 7 3 2 1 4 5 7 3 6 2 1 4 6 7 3 5

3 4 2 6 7 5 1 3 4 2 7 6 5 1 3 4 2 7 1 5 6

28. 4 3 5 7 2 1 6 29. 4 3 5 6 1 7 2 30. 4 3 5 2 6 7 1

5 6 7 1 4 3 2 5 6 7 1 2 4 3 5 6 7 3 2 1 4

6 7 1 2 3 4 5 6 7 1 3 4 2 5 6 7 1 5 3 4 2

7 5 6 3 1 2 4 7 5 6 2 3 1 4 7 5 6 1 4 2 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 3 7 6 2 1 4 5 7 3 6 2 1 4 5 6 7 3

3 4 2 7 6 1 5 3 4 5 7 6 2 1 3 4 2 6 7 1 5

31. 4 3 1 6 7 5 2 32. 4 3 6 1 2 7 5 33. 4 3 5 7 1 2 6

5 6 7 1 2 3 4 5 6 7 3 1 4 2 5 6 7 1 4 3 2

6 7 5 3 4 2 1 6 7 1 2 4 5 3 6 7 1 2 3 5 4

7 5 6 2 1 4 3 7 5 2 6 3 1 4 7 5 6 3 2 4 1

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 6 7 3 2 1 4 5 6 7 3 2 1 4 7 6 3 5

3 4 2 6 7 5 1 3 4 2 7 1 5 6 3 4 5 1 2 7 6

34. 4 3 5 7 2 1 6 35. 4 3 5 6 7 1 2 36. 4 3 6 5 7 2 1

5 6 7 1 3 2 4 5 6 7 3 2 4 1 5 6 7 2 3 1 4

6 7 1 2 4 3 5 6 7 1 2 4 3 5 6 7 1 3 4 5 2

7 5 6 3 1 4 2 7 5 6 1 3 2 4 7 5 2 6 1 4 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 6 7 3 2 1 4 3 7 5 6 2 1 4 7 6 3 5

3 4 1 6 7 2 5 3 4 1 6 2 7 5 3 4 5 1 7 2 6

37. 4 3 5 7 2 1 6 38. 4 3 5 7 6 2 1 39. 4 3 6 5 2 7 1

5 6 7 2 4 3 1 5 6 7 1 4 3 2 5 6 7 3 4 1 2

6 7 2 1 3 5 4 6 7 2 5 3 1 4 6 7 1 2 3 5 4

7 5 6 3 1 4 2 7 5 6 2 1 4 3 7 5 2 6 1 4 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 3 6 7 5 2 1 4 7 6 3 5 2 1 4 3 7 5 6

3 4 1 6 7 5 2 3 4 5 1 2 7 6 3 4 2 6 1 7 5

40. 4 3 5 7 1 2 6 41. 4 3 6 5 7 1 2 42. 4 3 5 7 6 2 1

5 6 7 1 2 3 4 5 6 7 3 4 2 1 5 6 7 1 2 3 4

6 7 2 5 3 4 1 6 7 1 2 3 5 4 6 7 1 5 3 4 2

7 5 6 2 4 1 3 7 5 2 6 1 4 3 7 5 6 2 4 1 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 3 6 7 5 2 1 4 5 6 7 3

3 4 5 2 6 7 1 3 4 2 6 7 5 1 3 4 5 7 1 2 6

43. 4 3 6 7 1 2 5 44. 4 3 5 7 2 1 6 45. 4 3 6 1 7 5 2

5 6 7 1 3 4 2 5 6 7 1 4 3 2 5 6 7 2 4 3 1

6 7 1 3 2 5 4 6 7 1 5 3 2 4 6 7 1 3 2 4 5

7 5 2 6 4 1 3 7 5 6 2 1 4 3 7 5 2 6 3 1 4

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 6 7 3 5 2 1 4 5 6 7 3 2 1 4 6 7 3 5

3 4 2 5 6 7 1 3 4 2 6 7 5 1 3 4 2 5 6 7 1

46. 4 3 5 7 1 2 6 47. 4 3 5 7 1 2 6 48. 4 3 5 7 1 2 6

5 6 7 3 2 1 4 5 6 7 1 3 4 2 5 6 7 1 3 4 2

6 7 1 2 4 5 3 6 7 1 2 4 3 5 6 7 1 3 2 5 4

7 5 6 1 3 4 2 7 5 6 3 2 1 4 7 5 6 2 4 1 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 6 7 3 2 1 4 5 7 3 6 2 1 4 5 7 3 6

3 4 2 7 1 5 6 3 4 2 6 1 7 5 3 4 2 7 6 1 5

49. 4 3 5 6 7 1 2 50. 4 3 5 7 6 2 1 51. 4 3 5 6 1 7 2

5 6 7 1 3 2 4 5 6 7 1 3 4 2 5 6 7 2 3 4 1

6 7 1 2 4 3 5 6 7 1 3 2 5 4 6 7 1 3 2 5 4

7 5 6 3 2 4 1 7 5 6 2 4 1 3 7 5 6 1 4 2 3

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 7 3 6 2 1 4 3 7 5 6 2 1 4 5 6 7 3

3 4 2 6 1 7 5 3 4 5 6 2 7 1 3 4 2 6 7 1 5

52. 4 3 5 7 6 2 1 53. 4 3 6 7 1 2 5 54. 4 3 1 7 2 5 6

5 6 7 1 3 4 2 5 6 7 2 3 1 4 5 6 7 1 3 2 4

6 7 1 2 4 5 3 6 7 1 5 4 3 2 6 7 5 2 4 3 1

7 5 6 3 2 1 4 7 5 2 1 6 4 3 7 5 6 3 1 4 2

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

2 1 4 5 3 7 6 2 1 4 5 6 7 3 2 1 4 5 6 7 3

3 4 1 6 7 5 2 3 4 2 7 1 5 6 3 4 1 6 7 5 2

55. 4 3 5 7 6 2 1 56. 4 3 5 6 7 2 1 57. 4 3 5 7 1 2 6

5 6 7 1 2 3 4 5 6 7 1 3 4 2 5 6 7 2 4 3 1

6 7 2 3 1 4 5 6 7 1 2 4 3 5 6 7 2 1 3 4 5

7 5 6 2 4 1 3 7 5 6 3 2 1 4 7 5 6 3 2 1 4

Доведемо ще одне твердження.

Теорема 9.

Якщо n — просте число, то всі латинські квадрати, що мають симетрію, є первісними. Їх сигнатури, за винятком квадратів порядку 2, є n:n.

Доведення. З попереднього випливає, що порядок симетрії латинського квадрату є дільником n. Оскільки n просте, він дорівнює або 1, або n. У першому випадку симетрій немає; в другому симетрії є циклічними перестановками рядків та стовбчиків. Переставимо рядки симетричного квадрату таким чином, щоб деяка його симетрія переводила 1-й рядок в 2-й, 2‑й — в 3-й, і т.д., останній — в перший. Тоді перестановка стовбчиків цієї симетрії буде переводити також 1-й рядок в 2-й, і т.д. Звідси випливає, що всі рядки утворюються n-кратним застосуванням одної перестановки до першого рядка. Отже, відношення довільних двох рядків є циклом порядку n. Але це означає, що квадрат є первісним, тому що відношення рідків, що містять підквадрат повинно мати цикли в межах цього підквадрату, тобто порядку не більше n/2. Перша частина теореми доведена.

Друга частина випливає з того, що для непарних n цикли порядку n є парними перестановками, тому всі рядки симетричного квадрату мають однакову парність.

Інверсії

Кожний рядок латинського квадрату можна розглядати як перестановку чисел від 1 до n. Якщо кожну таку перестановку замінити на обернену, вийде інший квадрат, який ми називатимемо інвертованим по рядках. Так само визначається квадрат, інвертований по стовбчиках. Покажемо, що ці квадрати справді є латинськими. Дійсно, припустимо, що це не так. Тоді в інветованому (по рядках) квадраті існує стовбчик k, який містить два однакових числа l. Але це означає, що у початковому квадраті стовбчик l містить у відповідних рядках число k. А це неможливо, бо за умовою початковий квадрат латинський.

Нажаль, інверсія не інваріантна щодо еквівалентності, тобто інверсія еквівалентних квадратів утворює квадрати, які не обов’язково є еквівалентними. Також воне не інваріантна щодо ізоморфізму. Єдине, що можна стверджувати — якщо квадрати переходять один в одний перестановкою стовбчиків, то їх інверсія по рядках утворить ізоморфні квадрати, а інверсія по стовбчиках, очевидно, утворить квадрати, які також переходять один в одний перестановкою стовбчиків. Перше твердження випливає з рівності (ab)^-1 = a^-1 b^-1 , яка справедлива для всіх перестановок. Тому інверсію не можна вписати в класифікацію, яку ми щойно розробили. Натомість інверсія дає можливіть класифікувати латинські квадрати зовсім іншим способом.

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

Теорема 10.

Інверсний порядок латинського квадрата може набувати лише таких значень: 1, 2, 3 або 6.

Доведення. Будемо розглядати латинський квадрат як таблицю Клейна деякої бінарної операції над числами від 1 до n. Побудуємо графік цієї операції, відкладаючи по вісі Ox номер стовбчика, по вісі Oy — номер рядка, а по вісі Oz — результат, тобто число у відповідній клітині. Такий графік являє собою множину з n² цілих точок всередині куба із стороною n таких, що кожна пряма, паралельна одній з координатних ліній містить лише одну точку. Зрозуміло, що подібна множина однозначно визначає латинський квадрат. Інверсія квадрата по рядках рівносильна дзеркальному відображенню графіка відносно площини

, а по стобчиках — відносно площини

. Ці два відображення породжують групу симетрій куба, при яких початок координат залишається на місці. Це група S₃, вона складається з 6 елементів. Якщо графік має власні симетрії з цієї групи, ланцюжок інверсій замкнеться, коли ми дістанемось до відповідної симетрії, якщо ні — утвориться 6 квадратів. Отже, інверсний порядок завжди є дільником числа 6.

Теорема доведена.

Ми підрахували кількість квадратів розміром від 3 до 6 кожного інверсного порядку.

Результат наводимо в таблиці.

Порядок Інверсний порядок

1 2 3 6

3 3 0 3 6

4 16 2 80 478

5 30 90 690 160470

6 480 2400 327840 812520480

Висновок

Нами створено метод, який дозволяє проводити класифікацію дискретних бінарних відображень (латинських квадратів), розділяючи їх на багато різних типів. Це дає можливість глибше зрозуміти природу таких відображень і відкрити в них невідомі раніше властивості. Ми розглянули далеко не всі можливі інваріанти; так, наприклад, крім кількості підквадратів інваріантними є деякі особливості їх розташування; також можна будувати інваріанти принципово іншим способом. Ми також не розглядали квадрати порядку більше 7. Усе це може бути темою наступних досліджень.

Література

1. J.H. van Lint, R.M. Wilson: A Course in Combinatorics. Cambridge University Press 1992, ISBN 0-521-42260-4

2. C.F.Laywine,G.L.Mullen: Discrete MathematicsUsing Latin Squares. Wiley & sons inc. 1998, ISBN 0-471-24064-8

3. Холл М. Комбинаторика, пер. с англ. М. 1970.

4. Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest. 1974.

5. Сачков В. Н. Комбинаторные методы дискретной математики. М. 1977.

6. Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.

7. Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York. 1998.

8. Малых А. Е., Данилова В. И. Об историческом процессе развития теории латинских квадратов и некоторых их приложениях // Вестник Пермского Университета. 2010. Вып. 4(4). С. 95-104.

9. Тужилин М. Э. Об истории исследований латинских квадратов // Обозрение прикладной и промышленной математики. 2012. Том 19, выпуск 2. С. 226—227.

10. B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM Journal on Discrete Mathematics,

11. Bailey, R.A. (2008). "6 Row-Column designs and 9 More about Latin squares". Design of Comparative Experiments. Cambridge University Press. ISBN 978-0-521-68357-9. MR 2422352. Pre-publication chapters are available on-line.

12. Hinkelmann, Klaus and Kempthorne, Oscar (2008). Design and Analysis of Experiments. I and II (Second ed.). Wiley. ISBN 978-0-470-38551-7.

13. Hinkelmann, Klaus and Kempthorne, Oscar (2008). Design and Analysis of Experiments, Volume I: Introduction to Experimental Design (Second ed.). Wiley. ISBN 978-0-471-72756-9.

14. Hinkelmann, Klaus and Kempthorne, Oscar (2005). Design and Analysis of Experiments, Volume 2: Advanced Experimental Design (First ed.). Wiley. ISBN 978-0-471-55177-5.

15. Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). New York: Dover. ISBN 0-486-65685-3.

16. Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific. ISBN 981-256-360-1.

17. Shah, Kirti R.; Sinha, Bikas K. (1989). "4 Row-Column Designs". Theory of Optimal Designs. Lecture Notes in Statistics 54. Springer-Verlag. pp. 66–84. ISBN 0-387-96991-8. MR 1016151.

18. Shah, K. R.; Sinha, Bikas K. (1996). "Row-column designs". In S. Ghosh and C. R. Rao. Design and analysis of experiments. Handbook of Statistics 13. Amsterdam: North-Holland Publishing Co. pp. 903–937. ISBN 0-444-82061-2. MR 1492586.

19. Street, Anne Penfold and Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0-19-853256-3.

20. C.J. Colbourn, T. Kløve, and A.C.H. Ling, Permutation arrays for powerline communication, IEEE Trans. Inform. Theory, vol. 50, pp. 1289–1291, 2004.

21.Euler's revolution, New Scientist, 24th of March 2007, pp 48–51

22. Sophie Huczynska, Powerline communication and the 36 officers problem, Philosophical Transactions of the Royal Society A, vol 364, p 3199.

23. C. Colbourn (1984). "The complexity of completing partial latin squares". Discrete Applied Mathematics 8: 25–30. doi:10.1016/0166-218X(84)90075-1.

24. Letters Patent Confering the SSC Arms

25. Bailey, R.A. (2008). "6 Row-Column designs and 9 More about Latin squares". Design of Comparative Experiments. Cambridge University Press. ISBN 978-0-521-68357-9. MR 2422352. Pre-publication chapters are available on-line.

26. Dénes, J.; Keedwell, A. D. (1974). Latin squares and their applications. New York-London: Academic Press. p. 547. ISBN 0-12-209350-X. MR 351850.

27. Dénes, J. H.; Keedwell, A. D. (1991). Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics 46. Amsterdam: Academic Press. pp. xiv+454. ISBN 0-444-88899-3. MR 1096296.

28. Hinkelmann, Klaus; Kempthorne, Oscar (2008). Design and Analysis of Experiments. I , II (Second ed.). Wiley. ISBN 978-0-470-38551-7. MR 2363107.

ТЕОРІЯ ЧИСЕЛ ДЛЯ ШКОЛЯРІВ

пʼятниця, 3 лютого 2017 р.