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

Отображение 7 × 7 латинского квадрат, это витраж отличие Рональда Фишера , чей дизайн экспериментов обсуждали латинские квадраты.

В комбинаторике и опытно - конструкторских , А латинский квадрат является  п  ×  п массив заполняется  п различных символов, каждый из которых встречается ровно один раз в каждой строке и ровно один раз в каждом столбце. Пример латинского квадрата 3 × 3:

Название «Латинский квадрат» было вдохновлено математическими работами Леонарда Эйлера (1707–1783), который использовал латинские символы в качестве символов ^[1], но можно использовать любой набор символов: в приведенном выше примере буквенная последовательность A, B , C можно заменить целочисленной последовательностью 1, 2, 3. Эйлер начал общую теорию латинских квадратов.

История [ править ]

Корейский математик Чхве Сок Чжон был первым, кто опубликовал пример латинских квадратов девятого порядка, чтобы построить магический квадрат в 1700 году, опередив Леонарда Эйлера на 67 лет. ^[2]

Уменьшенная форма [ править ]

Латинский квадрат называется сокращенным (также нормализованным или в стандартной форме ), если и его первая строка, и его первый столбец находятся в своем естественном порядке. ^[3] Например, латинский квадрат выше не сокращается, потому что его первый столбец - это A, C, B, а не A, B, C.

Любой латинский квадрат можно уменьшить, переставив (то есть переупорядочив) строки и столбцы. Здесь переключение второй и третьей строк указанной выше матрицы дает следующий квадрат:

Этот латинский квадрат сокращен; и его первая строка, и его первый столбец расположены в алфавитном порядке A, B, C.

Свойства [ править ]

Представление ортогонального массива [ править ]

Если каждая запись латинского квадрата n × n записана как тройка ( r , c , s ), где r - строка, c - столбец, а s - символ, мы получим набор из n ² троек, называемый представление квадрата ортогональным массивом . Например, представление латинского квадрата ортогональным массивом

является

{(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. Ортогональные массивы обычно записываются в форме массива, где тройки являются строками, например:

Определение латинского квадрата можно записать в терминах ортогональных массивов:

• Латинский квадрат - это набор из n ² троек ( r , c , s ), где 1 ≤ r , c , s ≤ n , таких, что все упорядоченные пары ( r , c ) различны, все упорядоченные пары ( r , s ) различны, и все упорядоченные пары ( c , s ) различны.

Это означает, что n ² упорядоченных пар ( 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] заключается в том, что

${\ displaystyle \ prod _ {k = 1} ^ {n} \ left (k! \ right) ^ {n / k} \ geq L_ {n} \ geq {\ frac {\ left (n! \ right) ^ {2n}} {n ^ {n ^ {2}}}}.}$

Простая и явная формула для количества латинских квадратов была опубликована в 1992 году, но ее все еще нелегко вычислить из-за экспоненциального увеличения количества членов. Эта формула для числа L _п о п × п латинских квадратов

${\ displaystyle L_ {n} = n! \ sum _ {A \ in B_ {n}} ^ {} (- 1) ^ {\ sigma _ {0} (A)} {\ binom {\ operatorname {per} A} {n}},}$

где В _п есть множество все п × п {0, 1} матрицы, σ ₀ ( ) является число нулевых элементов в матрице А , и в ( А ) является постоянной матрицей A . ^[6]

В таблице ниже приведены все известные точные значения. Видно, что цифры очень быстро растут. Для каждого n общее количество латинских квадратов (последовательность A002860 в OEIS ) равно n ! ( п -1)! умноженное на количество сокращенных латинских квадратов (последовательность A000315 в OEIS ).

Для каждого n каждый изотопический класс (последовательность A040082 в OEIS ) содержит до ( n !) ³ латинских квадратов (точное число варьируется), в то время как каждый основной класс (последовательность A003090 в OEIS ) содержит 1, 2, 3 или 6 изотопических классов.

Количество структурно различных латинских квадратов (т. Е. Квадраты не могут быть идентичными посредством вращения, отражения и / или перестановки символов) для n = от 1 до 7 составляет 1, 1, 1, 12, 192, 145164, 1524901344 соответственно (последовательность A264603 в OEIS ).

Примеры [ править ]

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

${\ displaystyle {\ begin {bmatrix} 1 \ end {bmatrix}} \ quad {\ begin {bmatrix} 1 & 2 \\ 2 & 1 \ end {bmatrix}} \ quad {\ begin {bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \ конец {bmatrix}}}$

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

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

Они представляют собой соответственно таблицы умножения следующих групп:

• {0} - тривиальная 1-элементная группа
• ${\displaystyle \mathbb {Z} _{2}}$- бинарная группа
• ${\displaystyle \mathbb {Z} _{3}}$- циклическая группа порядка 3
• ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$- четырехгруппа Кляйна
• ${\displaystyle \mathbb {Z} _{4}}$ - циклическая группа порядка 4
• ${\displaystyle \mathbb {Z} _{5}}$ - циклическая группа 5-го порядка
• последний пример квазигруппы , а точнее петли , которая не ассоциативна.

Трансверсали и радужные соответствия [ править ]

Трансверсально в латинском квадрате является выбор п клеток, где каждая строка содержит одну ячейку, каждый столбец содержит одну ячейку, и есть одна ячейка , содержащая каждый символ.

Латинский квадрат можно рассматривать как полный двудольный граф, в котором строки являются вершинами одной части, столбцы - вершинами другой части, каждая ячейка - ребром (между ее строкой и ее столбцом), а символы - цветами. Правила латинских квадратов подразумевают, что это правильная окраска краев . Согласно этому определению латинская трансверсаль - это совпадение, в котором каждое ребро имеет свой цвет; такое сопоставление называется сопоставлением радуги .

Поэтому многие результаты о латинских квадратах / прямоугольниках содержатся в статьях с термином «согласование радуги» в названии и наоборот. ^[7]

Некоторые латинские квадраты не имеют поперечного сечения. Например, когда п четно, п матрицу с размерностью п латинский квадрат , в котором значение ячейки I, J представляет собой ( я + J ) мод п не имеет трансверсалъ. Вот два примера:

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

В 1967 году, HJ Райзер высказал предположение , что, когда п является нечетным , каждый п матрицу с размерностью п латинский квадрат имеет трансверсалъ. ^[8]

В 1975 г. С. К. Штейн и Бруальди высказал предположение , что, когда п является даже , каждый п матрицу с размерностью п латинский квадрат имеет частичную трансверсалъ размера п -1. ^[9]

Более общая гипотеза Stein является то , что трансверсалий размером п -1 существует не только в латинских квадратах , но и в любом ˝n˝ матрицы с размерностью п массив п символов, до тех пор , как каждый символ появляется ровно п раз. ^[8]

Доказаны более слабые версии этих гипотез:

• Каждый латинский квадрат размером n x n имеет частичную трансверсаль размера 2 n / 3. ^[10]
• Каждая н матрицу с размерностью п латинский квадрат имеет парциальное трансверсаль размера п - SQRT ( п ). ^[11]
• Каждой н матрицы с размерностью п латинского квадрат имеет парциальное трансверсалъ размера п - 11 журнала _- ² ( п ). ^[12]

Алгоритмы [ править ]

Для маленьких квадратов можно генерировать перестановки и проверять, соблюдается ли свойство латинского квадрата. Для больших квадратов алгоритм Якобсона и Мэтьюза позволяет производить выборку из равномерного распределения по пространству латинских квадратов n  ×  n . ^[13]

Приложения [ править ]

Статистика и математика [ править ]

• При планировании экспериментов латинские квадраты являются частным случаем планов столбцов и строк для двух факторов блокировки : ^{[14] [15]}

• В алгебре латинские квадраты относятся к обобщениям групп ; в частности, латинские квадраты характеризуются как таблицы умножения ( таблицы Кэли ) квазигрупп . Бинарная операция, таблица значений которой образует латинский квадрат, подчиняется свойству латинского квадрата .

Коды исправления ошибок [ править ]

Наборы латинских квадратов, которые ортогональны друг другу, нашли применение в качестве кодов для исправления ошибок в ситуациях, когда связь нарушается большим количеством типов шума, чем простой белый шум , например, при попытке передачи широкополосного Интернета по линиям электропередач. ^{[16] [17] [18]}

Во-первых, сообщение отправляется с использованием нескольких частот или каналов - распространенный метод, который делает сигнал менее уязвимым для шума на любой конкретной частоте. Письмо в отправляемом сообщении кодируется путем отправки серии сигналов на разных частотах через последовательные интервалы времени. В приведенном ниже примере буквы от A до L кодируются путем отправки сигналов на четырех разных частотах в четырех временных интервалах. Например, буква C кодируется путем отправки сначала с частотой 3, затем с частотой 4, 1 и 2.

${\displaystyle {\begin{matrix}A\\B\\C\\D\\\end{matrix}}{\begin{bmatrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\\end{bmatrix}}\quad {\begin{matrix}E\\F\\G\\H\\\end{matrix}}{\begin{bmatrix}1&3&4&2\\2&4&3&1\\3&1&2&4\\4&2&1&3\\\end{bmatrix}}\quad {\begin{matrix}I\\J\\K\\L\\\end{matrix}}{\begin{bmatrix}1&4&2&3\\2&3&1&4\\3&2&4&1\\4&1&3&2\\\end{bmatrix}}}$

Кодировка из двенадцати букв состоит из трех латинских квадратов, ортогональных друг другу. А теперь представьте, что в каналах 1 и 2 на протяжении всей передачи добавлен шум. Тогда буква A будет воспринята как:

${\displaystyle {\begin{matrix}12&12&123&124\\\end{matrix}}}$

Другими словами, в первом слоте мы получаем сигналы как с частоты 1, так и с частоты 2; в то время как третий слот имеет сигналы с частот 1, 2 и 3. Из-за шума мы больше не можем сказать, были ли первые два слота 1,1 или 1,2 или 2,1 или 2,2. Но случай 1,2 - единственный, который дает последовательность, соответствующую букве в приведенной выше таблице, букве A. Точно так же мы можем представить всплеск статического электричества по всем частотам в третьем слоте:

${\displaystyle {\begin{matrix}1&2&1234&4\\\end{matrix}}}$

Опять же, мы можем сделать вывод из таблицы кодировок, что должна была передаваться буква A. Количество ошибок, которые может обнаружить этот код, на единицу меньше количества временных интервалов. Также было доказано, что если количество частот представляет собой простое число или степень простого числа, ортогональные латинские квадраты создают коды обнаружения ошибок, которые являются максимально эффективными.

Математические головоломки [ править ]

Задача определения того, можно ли заполнить частично заполненный квадрат для образования латинского квадрата, является NP-полной . ^[19]

Популярные головоломки судоку - это частный случай латинских квадратов; любое решение головоломки судоку - это латинский квадрат. Судоку накладывает дополнительное ограничение: девять конкретных смежных подквадратов 3 × 3 также должны содержать цифры 1–9 (в стандартной версии). См. Также « Математика судоку» .

Более поздние головоломки KenKen также являются примерами латинских квадратов.

Настольные игры [ править ]

Латинские квадраты использовались в качестве основы для нескольких настольных игр, особенно популярной абстрактной стратегии Kamisado .

Агрономические исследования [ править ]

Латинские квадраты используются при планировании агрономических исследовательских экспериментов для минимизации экспериментальных ошибок. ^[20]

Геральдика [ править ]

Латинский квадрат также фигуры в гербе статистического общества Канады , ^[21] которые упомянуты в его гербе . Также он присутствует в логотипе Международного биометрического общества . ^[22]

Обобщения [ править ]

• Латинский прямоугольник представляет собой обобщение латинского квадрата , в котором существует п столбцы и п возможных значений, но количество строк может быть меньше , чем п . Каждое значение по-прежнему появляется не более одного раза в каждой строке и столбце.
• Греко-латинский квадрат представляет собой пару из двух латинских квадратов таким образом, что, когда один укладывают поверх других, каждая упорядоченная пара символов появляется ровно один раз.
• Latin гиперкуба является обобщением латинского квадрата из двух измерений в нескольких измерениях.

См. Также [ править ]

• Блочный дизайн
• Комбинаторный дизайн
• Пазл о восьми ферзях
• Футошики
• Магический квадрат
• Проблемы в латинских квадратах
• График ладьи , график , который имеет латинские квадраты , как его раскраски
• Площадь Сатор
• Ведический квадрат
• Слово квадрат

Заметки [ править ]

Ссылки [ править ]

• Бейли, РА (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 .
• Латинские квадраты в математической энциклопедии
• Латинские квадраты в онлайн-энциклопедии целочисленных последовательностей