В комбинаторике и опытно - конструкторских , А латинский квадрат является п × п массив заполняется п различных символов, каждый из которых встречается ровно один раз в каждой строке и ровно один раз в каждом столбце. Пример латинского квадрата 3 × 3:
А | B | C |
C | А | B |
B | C | А |
Название «Латинский квадрат» было вдохновлено математическими работами Леонарда Эйлера (1707–1783), который использовал латинские символы в качестве символов [1], но можно использовать любой набор символов: в приведенном выше примере буквенная последовательность A, B , C можно заменить целочисленной последовательностью 1, 2, 3. Эйлер начал общую теорию латинских квадратов.
История
Корейский математик Чхве Сок Чжон был первым, кто опубликовал пример латинских квадратов девятого порядка, чтобы построить магический квадрат в 1700 году, опередив Леонарда Эйлера на 67 лет. [2]
Уменьшенная форма
Латинский квадрат называется сокращенным (также нормализованным или в стандартной форме ), если и его первая строка, и его первый столбец находятся в их естественном порядке. [3] Например, латинский квадрат выше не сокращается, потому что его первый столбец - это A, C, B, а не A, B, C.
Любой латинский квадрат можно уменьшить, переставив (то есть переупорядочив) строки и столбцы. Здесь переключение второй и третьей строк указанной выше матрицы дает следующий квадрат:
А | B | C |
B | C | А |
C | А | B |
Этот латинский квадрат уменьшен; и его первая строка, и его первый столбец расположены в алфавитном порядке A, B, C.
Характеристики
Ортогональное представление массива
Если каждый элемент латинского квадрата размера n × n записать как тройку ( r , c , s ), где r - строка, c - столбец, а s - символ, мы получим набор из n 2 троек, называемый представление квадрата ортогональным массивом . Например, представление латинского квадрата ортогональным массивом
1 | 2 | 3 |
2 | 3 | 1 |
3 | 1 | 2 |
является
- {(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)},
где, например, тройка (2, 3, 1) означает, что в строке 2 и столбце 3 есть символ 1. Ортогональные массивы обычно записываются в форме массива, где тройки являются строками, например:
р | 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 2 троек ( r , c , s ), где 1 ≤ r , c , s ≤ n , таких, что все упорядоченные пары ( r , c ) различны, все упорядоченные пары ( r , s ) различны, и все упорядоченные пары ( c , s ) различны.
Это означает, что n 2 упорядоченных пар ( r , c ) - это все пары ( i , j ) с 1 ≤ i , j ≤ n , по одному разу каждая. То же самое верно для упорядоченных пар ( r , s ) и упорядоченных пар ( c , s ).
Представление ортогонального массива показывает, что строки, столбцы и символы играют довольно похожие роли, как будет показано ниже.
Классы эквивалентности латинских квадратов
Многие операции с латинским квадратом приводят к созданию другого латинского квадрата (например, переворачивание его вверх ногами).
Если мы переставляем строки, переставляем столбцы и переставляем имена символов латинского квадрата, мы получаем новый латинский квадрат, который считается изотопным первому. Изотопизм - это отношение эквивалентности , поэтому множество всех латинских квадратов делится на подмножества, называемые изотопическими классами , так что два квадрата в одном классе изотопны, а два квадрата в разных классах не изотопны.
Другой тип операций проще всего объяснить, используя представление латинского квадрата ортогональным массивом. Если мы систематически и последовательно переупорядочиваем три элемента в каждой тройке (то есть переставляем три столбца в форме массива), получается другой ортогональный массив (и, таким образом, еще один латинский квадрат). Например, мы можем заменить каждую тройку ( r , c , s ) на ( c , r , s ), что соответствует транспонированию квадрата (отражающемуся относительно его главной диагонали), или мы можем заменить каждую тройку ( r , c , s ) на ( c , s , r ), что является более сложной операцией. Всего существует 6 возможностей, включая «ничего не делать», что дает нам 6 латинских квадратов, называемых конъюгатами (также парастрофами ) исходного квадрата. [4]
Наконец, мы можем объединить эти две операции эквивалентности: два латинских квадрата называются паратопическими , а также изотопными основного класса , если один из них изотопен сопряженному с другим. Это снова отношение эквивалентности, причем классы эквивалентности называются основными классами , видами или паратопическими классами . [4] Каждый основной класс содержит до шести изотопических классов.
Число
Не Там будет не известно , легко вычислимая формула для числа L п о п × п латинских квадратов с символами 1,2, ..., п . Самые точные верхние и нижние границы, известные для больших n , далеко друг от друга. Один классический результат [5] заключается в том, что
Простая и явная формула для количества латинских квадратов была опубликована в 1992 году, но ее все еще нелегко вычислить из-за экспоненциального увеличения количества членов. Эта формула для числа L п о п × п латинских квадратов
В таблице ниже приведены все известные точные значения. Видно, что цифры очень быстро растут. Для каждого n общее количество латинских квадратов (последовательность A002860 в OEIS ) равно n ! ( n - 1)! умноженное на количество сокращенных латинских квадратов (последовательность A000315 в OEIS ).
п | уменьшенные латинские квадраты размера n (последовательность A000315 в OEIS ) | все латинские квадраты размера n (последовательность A002860 в OEIS ) |
---|---|---|
1 | 1 | 1 |
2 | 1 | 2 |
3 | 1 | 12 |
4 | 4 | 576 |
5 | 56 | 161 280 |
6 | 9 408 | 812 851 200 |
7 | 16 942 080 | 61 479 419 904 000 |
8 | 535 281 401 856 | 108 776 032 459 082 956 800 |
9 | 377 597 570 964 258 816 | 5,524,751,496,156,892,842,531,225,600 |
10 | 7 580 721 483 160 132 811 489 280 | 9 982 437 658 213 039 871 725 064 756 920 320 000 |
11 | 5,363,937,773,277,371,298,119,673,540,771,840 | 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000 |
12 | 1,62 × 10 44 | |
13 | 2,51 × 10 56 | |
14 | 2,33 × 10 70 | |
15 | 1,50 × 10 86 |
Для каждого n каждый изотопический класс (последовательность A040082 в OEIS ) содержит до ( n !) 3 латинских квадратов (точное число варьируется), в то время как каждый основной класс (последовательность A003090 в OEIS ) содержит 1, 2, 3 или 6 изотопических классов.
п | основные классы | классы изотопии | структурно отличные квадраты |
---|---|---|---|
1 | 1 | 1 | 1 |
2 | 1 | 1 | 1 |
3 | 1 | 1 | 1 |
4 | 2 | 2 | 12 |
5 | 2 | 2 | 192 |
6 | 12 | 22 | 145 164 |
7 | 147 | 564 | 1 524 901 344 |
8 | 283 657 | 1,676,267 | |
9 | 19 270 853 541 | 115 618 721 533 | |
10 | 34 817 397 894 749 939 | 208 904 371 354 363 006 | |
11 | 2 036 029 552 582 883 134 196 099 | 12 216 177 315 369 229 261 482 540 |
Количество структурно различных латинских квадратов (т. Е. Квадраты нельзя сделать идентичными посредством вращения, отражения и / или перестановки символов) для n = от 1 до 7 составляет 1, 1, 1, 12, 192, 145164, 1524901344 соответственно (последовательность A264603 в OEIS ).
Примеры
Мы приводим по одному примеру латинского квадрата от каждого основного класса до пятого порядка.
Они представляют собой соответственно таблицы умножения следующих групп:
- {0} - тривиальная 1-элементная группа
- - бинарная группа
- - циклическая группа порядка 3
- - четырехгрупповая группа Клейна
- - циклическая группа порядка 4
- - циклическая группа 5-го порядка
- последний пример квазигруппы , а точнее петли , которая не ассоциативна.
Трансверсали и радужные соответствия
Трансверсально в латинском квадрате является выбор п клеток, где каждая строка содержит одну ячейку, каждый столбец содержит одну ячейку, и есть одна ячейка , содержащая каждый символ.
Латинский квадрат можно рассматривать как полный двудольный граф, в котором строки являются вершинами одной части, столбцы - вершинами другой части, каждая ячейка - ребром (между ее строкой и ее столбцом), а символы - цветами. Правила латинских квадратов подразумевают, что это правильная окраска краев . Согласно этому определению латинская трансверсаль - это совпадение, в котором каждое ребро имеет свой цвет; такое сопоставление называется сопоставлением радуги .
Поэтому многие результаты о латинских квадратах / прямоугольниках содержатся в статьях с термином «согласование радуги» в названии и наоборот. [7]
Некоторые латинские квадраты не имеют поперечного сечения. Например, когда п четно, п матрицу с размерностью п латинский квадрат , в котором значение ячейки я , J представляет собой ( я + J ) мод п не имеет трансверсалъ. Вот два примера:
В 1975 г. С. К. Штейн и Бруальди высказал предположение , что, когда п является даже , каждый п матрицу с размерностью п латинский квадрат имеет частичную трансверсалъ размера п -1. [9]
Более общая гипотеза Stein является то , что трансверсалий размером п -1 существует не только в латинских квадратах , но и в любом ˝n˝ матрицы с размерностью п массив п символов, до тех пор , как каждый символ появляется ровно п раз. [8]
Доказаны более слабые версии этих гипотез:
- Каждый латинский квадрат размером n x n имеет частичную трансверсаль размера 2 n / 3. [10]
- Каждая н матрицу с размерностью п латинский квадрат имеет парциальное трансверсаль размера п - SQRT ( п ). [11]
- Каждый латинский квадрат размером n x n имеет частичную трансверсаль размера n - 11 log2
2( п ). [12]
Алгоритмы
Для маленьких квадратов можно генерировать перестановки и проверять, соблюдается ли свойство латинского квадрата. Для больших квадратов алгоритм Якобсона и Мэтьюза позволяет производить выборку из равномерного распределения по пространству латинских квадратов n × n . [13]
Приложения
Статистика и математика
- При планировании экспериментов латинские квадраты являются частным случаем планов столбцов и строк для двух факторов блокировки : [14] [15]
- В алгебре латинские квадраты относятся к обобщениям групп ; в частности, латинские квадраты характеризуются как таблицы умножения ( таблицы Кэли ) квазигрупп . Бинарная операция, таблица значений которой образует латинский квадрат, подчиняется свойству латинского квадрата .
Коды исправления ошибок
Наборы латинских квадратов, которые ортогональны друг другу, нашли применение в качестве кодов для исправления ошибок в ситуациях, когда связь нарушается большим количеством типов шума, чем простой белый шум , например, при попытке передачи широкополосного Интернета по линиям электропередач. [16] [17] [18]
Во-первых, сообщение отправляется с использованием нескольких частот или каналов - распространенный метод, который делает сигнал менее уязвимым для шума на любой конкретной частоте. Письмо в отправляемом сообщении кодируется путем отправки серии сигналов на разных частотах через последовательные интервалы времени. В приведенном ниже примере буквы от A до L кодируются путем отправки сигналов на четырех разных частотах в четырех временных интервалах. Например, буква C кодируется путем отправки сначала с частотой 3, затем с частотой 4, 1 и 2.
Кодировка из двенадцати букв состоит из трех латинских квадратов, ортогональных друг другу. А теперь представьте, что в каналах 1 и 2 на протяжении всей передачи добавлен шум. Тогда буква A будет воспринята как:
Другими словами, в первом слоте мы получаем сигналы как с частоты 1, так и с частоты 2; в то время как третий слот имеет сигналы с частотами 1, 2 и 3. Из-за шума мы больше не можем сказать, были ли первые два слота 1,1 или 1,2 или 2,1 или 2,2. Но случай 1,2 - единственный, который дает последовательность, соответствующую букве в приведенной выше таблице, букве A. Точно так же мы можем представить всплеск статического электричества по всем частотам в третьем слоте:
Опять же, мы можем сделать вывод из таблицы кодировок, что должна была передаваться буква A. Количество ошибок, которые может обнаружить этот код, на единицу меньше количества временных интервалов. Также было доказано, что если количество частот представляет собой простое число или степень простого числа, ортогональные латинские квадраты создают коды обнаружения ошибок, которые являются максимально эффективными.
Математические головоломки
Задача определения того, можно ли заполнить частично заполненный квадрат для образования латинского квадрата, является NP-полной . [19]
Популярные головоломки судоку - это частный случай латинских квадратов; любое решение головоломки судоку - это латинский квадрат. Судоку накладывает дополнительное ограничение: девять конкретных смежных подквадратов 3 × 3 также должны содержать цифры 1–9 (в стандартной версии). См. Также « Математика судоку» .
Более поздние головоломки KenKen также являются примерами латинских квадратов.
Настольные игры
Латинские квадраты использовались в качестве основы для нескольких настольных игр, особенно популярной абстрактной стратегии Kamisado .
Агрономические исследования
Латинские квадраты используются при планировании агрономических исследовательских экспериментов для минимизации экспериментальных ошибок. [20]
Геральдика
Латинский квадрат также фигуры в гербе статистического общества Канады , [21] которые упомянуты в его гербе . Также он присутствует в логотипе Международного биометрического общества . [22]
Обобщения
- Латинский прямоугольник представляет собой обобщение латинского квадрата , в котором существует п столбцы и п возможных значений, но количество строк может быть меньше , чем п . Каждое значение по-прежнему появляется не более одного раза в каждой строке и столбце.
- Греко-латинский квадрат представляет собой пару из двух латинских квадратов таким образом, что, когда один укладывают поверх других, каждая упорядоченная пара символов появляется ровно один раз.
- Latin гиперкуба является обобщением латинского квадрата из двух измерений в нескольких измерениях.
Смотрите также
- Блочный дизайн
- Комбинаторный дизайн
- Пазл о восьми ферзях
- Футошики
- Магический квадрат
- Проблемы в латинских квадратах
- График ладьи , график , который имеет латинские квадраты , как его раскраски
- Площадь Сатор
- Ведический квадрат
- Слово квадрат
Заметки
- ^ Уоллис, WD; Джордж, JC (2011), Введение в комбинаторику , CRC Press, стр. 212, ISBN 978-1-4398-0623-4
- ^ Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2 ноября 2006 г.). Справочник комбинаторных конструкций (2-е изд.). CRC Press. п. 12. ISBN 9781420010541. Проверено 28 марта 2017 года .
- ^ Dénes & Keedwell 1974 , стр. 128
- ^ a b Денес и Кидвелл 1974 , стр. 126
- ↑ van Lint & Wilson 1992 , pp. 161-162
- ^ Цзя-ю Шао; Ван-ди Вэй (1992). «Формула числа латинских квадратов». Дискретная математика . 110 (1–3): 293–296. DOI : 10.1016 / 0012-365x (92) 90722-р .
- ^ Гьярфас, Андраш; Саркози, Габор Н. (2012). «Радужные совпадения и частичные пересечения латинских квадратов». arXiv : 1208.5670 [ CO math. CO ].
- ^ а б Ахарони, Рон; Бергер, Эли; Котлар, Дани; Зив, Ран (2017-01-04). «По догадке Штейна». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. DOI : 10.1007 / s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
- ^ Штейн, Шерман (1975-08-01). «Трансверсалии латинских квадратов и их обобщения» . Тихоокеанский математический журнал . 59 (2): 567–575. DOI : 10,2140 / pjm.1975.59.567 . ISSN 0030-8730 .
- ^ Коксма, Клаас К. (1969-07-01). «Нижняя оценка порядка частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . 7 (1): 94–95. DOI : 10.1016 / s0021-9800 (69) 80009-8 . ISSN 0021-9800 .
- ^ Вулбрайт, Дэвид Э (1978-03-01). «Латинский квадрат размера n × n имеет трансверсаль, содержащую не менее n − n различных символов». Журнал комбинаторной теории, Серия А . 24 (2): 235–237. DOI : 10.1016 / 0097-3165 (78) 90009-2 . ISSN 0097-3165 .
- ^ Хатами, Пуйя; Шор, Питер В. (2008-10-01). «Нижняя оценка длины частичной трансверсали в латинском квадрате». Журнал комбинаторной теории, Серия А . 115 (7): 1103–1113. DOI : 10.1016 / j.jcta.2008.01.002 . ISSN 0097-3165 .
- ^ Jacobson, MT; Мэтьюз, П. (1996). «Генерация равномерно распределенных случайных латинских квадратов». Журнал комбинаторных дизайнов . 4 (6): 405–437. DOI : 10.1002 / (sici) 1520-6610 (1996) 4: 6 <405 :: aid-jcd3> 3.0.co; 2-j .
- ^ Бейли, Р.А. (2008), «Планы из 6 строк и столбцов и еще 9 о латинских квадратах» , Дизайн сравнительных экспериментов , Cambridge University Press, ISBN 978-0-521-68357-9, Руководство по ремонту 2422352
- ^ Shah, Kirti R .; Синха, Бикас К. (1989), "4-х строчные конструкции", Теория оптимальных схем , Лекционные заметки по статистике , 54 , Springer-Verlag, стр. 66–84, ISBN 0-387-96991-8, MR 1016151
- ^ Колборн, CJ ; Kløve, T .; Линг, ACH (2004). «Массивы перестановок для связи по линиям электропередач». IEEE Trans. Инф. Теория . 50 : 1289–1291. DOI : 10,1109 / tit.2004.828150 . S2CID 15920471 .
- ^ Революция Эйлера , New Scientist, 24 марта 2007, стр 48-51
- ^ Huczynska, Софи (2006). «Связь по Powerline и проблема 36 офицеров». Философские труды Королевского общества А . 364 (1849): 3199–3214. DOI : 10,1098 / rsta.2006.1885 . PMID 17090455 . S2CID 17662664 .
- ^ К. Колборн (1984). «Сложность заполнения частичных латинских квадратов». Дискретная прикладная математика . 8 : 25–30. DOI : 10.1016 / 0166-218X (84) 90075-1 .
- ^ Применение латинского квадрата в агрономических исследованиях
- ^ «Патентные письма на оружие SSC» . ssc.ca . Архивировано из оригинала на 2013-05-21.
- ↑ Международное биометрическое общество. Архивировано 7 мая 2005 г. в Wayback Machine.
Рекомендации
- Бейли, РА (2008). «6 рядов-столбцов и еще 9 о латинских квадратах» . Дизайн сравнительных экспериментов . Издательство Кембриджского университета. ISBN 978-0-521-68357-9. Руководство по ремонту 2422352 .
- Dénes, J .; Кидвелл, AD (1974). Латинские квадраты и их приложения . Нью-Йорк-Лондон: Academic Press. п. 547. ISBN 0-12-209350-X. Руководство по ремонту 0351850 .
- Shah, Kirti R .; Синха, Бикас К. (1989). «4-х строчные конструкции». Теория оптимальных дизайнов . Конспект лекций по статистике . 54 . Springer-Verlag. С. 66–84. ISBN 0-387-96991-8. Руководство по ремонту 1016151 .
- ван Линт, JH; Уилсон, Р.М. (1992). Курс комбинаторики . Издательство Кембриджского университета. п. 157 . ISBN 0-521-42260-4.
дальнейшее чтение
- Dénes, JH; Кидвелл, AD (1991). Латинские квадраты: новые разработки в теории и приложениях . Анналы дискретной математики. 46 . Пол Эрдёш (предисловие). Амстердам: Academic Press. ISBN 0-444-88899-3. Руководство по ремонту 1096296 .
- Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов . I, II (Второе изд.). Вайли. ISBN 978-0-470-38551-7. Руководство по ремонту 2363107 .
- Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов, Том I: Введение в экспериментальный дизайн (второе изд.). Вайли. ISBN 978-0-471-72756-9. Руководство по ремонту 2363107 .
- Хинкельманн, Клаус; Кемпторн, Оскар (2005). Планирование и анализ экспериментов, Том 2: Расширенный экспериментальный дизайн (Первое изд.). Вайли. ISBN 978-0-471-55177-5. Руководство по ремонту 2129060 .
- Кнут, Дональд (2011). Искусство программирования, Том 4A: Комбинаторные алгоритмы, Часть 1 . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-03804-0.
- Laywine, Charles F .; Маллен, Гэри Л. (1998). Дискретная математика с использованием латинских квадратов . Серия Wiley-Interscience по дискретной математике и оптимизации. Нью-Йорк: ISBN John Wiley & Sons, Inc. 0-471-24064-8. Руководство по ремонту 1644242 .
- Шах, КР; Синха, Бикас К. (1996). «Рядно-столбчатые конструкции». В С. Гош и CR Рао (ред.). Планирование и анализ экспериментов . Справочник по статистике. 13 . Амстердам: Издательство Северной Голландии, стр. 903–937. ISBN 0-444-82061-2. Руководство по ремонту 1492586 .
- Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные проблемы в дизайне экспериментов (исправленная перепечатка изд. Wiley 1971 г.). Нью-Йорк: Дувр. ISBN 0-486-65685-3. Руководство по ремонту 1102899 .
- Улица, Энн Пенфолд ; Улица, Дебора Дж. (1987). Комбинаторика экспериментального дизайна . Нью-Йорк: Издательство Оксфордского университета. ISBN 0-19-853256-3. Руководство по ремонту 0908490 .
- Бергер, Пол Д .; Маурер, Роберт Э .; Челли, Джована Б. (28 ноября 2017 г.). Экспериментальный дизайн с приложениями в менеджменте, инженерии и науках (2-е издание (28 ноября 2017 г.) изд.). Springer. С. 267–282.
Внешние ссылки
- Вайсштейн, Эрик В. «Латинский квадрат» . MathWorld .
- Латинские квадраты в математической энциклопедии
- Латинские квадраты в онлайн-энциклопедии целочисленных последовательностей