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

редактировать

Квадратный массив с символами, которые встречаются один раз в строке и столбце

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

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

A	B	C
C	A	B
B	C	A

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

Содержание

1 История
2 Уменьшенная форма
3 Свойства
- 3.1 Ортогональное представление массива
- 3.2 Классы эквивалентности латинских квадратов
- 3.3 Число
- 3.4 Примеры
4 Поперечные смещения и согласования радуги
5 Алгоритмы
6 Приложения
- 6.1 Статистика и математика
- 6.2 Коды исправления ошибок
- 6.3 Математические головоломки
- 6.4 Настольные игры
- 6.5 Агрономические исследования
7 Геральдика
8 Обобщения
9 См. Также
10 Примечания
11 Ссылки
12 Дополнительная литература
13 Внешние ссылки

История

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

Сокращенная форма

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

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

A	B	C
B	C	A
C	A	B

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

Свойства

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

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

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

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 упорядоченных пар (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 латинских квадратов, называемых конъюгатами (также парастрофами ) исходного квадрата.

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

Число

Не существует известной легко вычислимой формулы для числа L n латинских квадратов размера n × n с символами 1,2,..., n. Самые точные верхние и нижние границы, известные для больших n, далеко друг от друга. Классический результат:

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

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

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

$L n = n! ∑ A ∈ B N (- 1) σ 0 (A) (на ⁡ A n), {\ displaystyle L_ {n} = n! \ Sum _ {A \ in B_ {n}} ^ {} (- 1) ^ {\ sigma _ {0} (A)} {\ binom {\ operatorname {per} A} {n}},}$ ${\ displaystyle L_ {n} = n! \ Sum _ {A \ in B_ {n}} ^ {} (- 1) ^ {\ sigma _ {0} (A)} {\ binom { \ operatorname {per} A} {n}},}$

где B n - множество всех n × n { 0, 1} матриц, σ 0 (A) - количество нулевых элементов в матрице A, а per (A) - перманент матрицы A.

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

Числа латинских квадратов разного размера
n	уменьшенные латинские квадраты размера 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	535281401856	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
13	2,51 × 10
14	2,33 × 10
15	1,50 × 10

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

Классы эквивалентности латинских квадратов
n	основные классы (последовательность A003090 в OEIS )	изотопических классах (последовательность A040082 в OEIS )	структурно отличные квадраты (последовательность A264603 в OEIS )
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 <185,34155>284155>>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 ).

Примеры

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

[1] [1 2 2 1] [1 2 3 2 3 1 3 1 2] {\ 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 \ end {bmatrix}}}

{\ begin {bmatrix} 1 \ end {matrix}} \ end {bmatrix}} \ begin {bmatrix} 1 2 \\ 2 1 \ end {bmatrix}} \ quad {\ begin {bmatrix} 1 2 3 \\ 2 3 1 \\ 3 1 2 \ end {bmatrix}}

[1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1] [1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1] {\ 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 [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] [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] {\ 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 {\ b\ bmatrix}} \ quad {\ begin {\ b\ b\matrix} \\ 5 3 2 1 4 \ end {bmatrix}}}

{\ begin {bmatrix} 1 2 3 4 5 \\ 2 3 5 1 4 \\ 3 5 4 1 1 \\ 4 endmatrix } \ 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-элементная группа
$Z 2 {\ displaystyle \ mathbb { Z} _ {2}}$ $\ mathbb {Z} _ {2}$ - двоичная группа
$Z 3 {\ displaystyle \ mathbb {Z} _ {3}}$ $\ mathbb {Z } _ {3}$ – циклическая группа из порядок 3
$Z 2 × Z 2 {\ displaystyle \ mathbb {Z} _ {2} \ times \ mathbb {Z} _ {2}}$ $\ mathbb {Z} _ {2 } \ times \ mathbb {Z} _ {2}$ - четырехгруппа Клейна
$Z 4 {\ displaystyle \ mathbb {Z} _ {4}}$ $\ mathbb {Z} _ {4}$ - циклическая группа порядка 4
$Z 5 {\ displaystyle \ mathbb {Z} _ {5}}$ $\ mathbb {Z} _ {5}$ - циклическая группа порядка 5
последняя из них пример квазигруппы , или, скорее, цикла, который не является ассоциативным.

Поперечные и радужные соответствия

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

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

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

Немного латыни квадраты не имеют поперечника. Например, когда n четно, латинский квадрат размером n на n, в котором значение ячейки i, j равно (i + j) mod n, не имеет трансверсали. Вот два примера:

$[1 2 2 1] [1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3] {\ 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}}}$ ${\ 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 году H. Дж. Райзер предположил, что, когда n нечетно, каждый латинский квадрат размером n × n имеет трансверсаль.

В 1975 г. С.К. Стейн и Бруальди предположили, что, когда n четное, каждый латинский квадрат n × n имеет частичную трансверсаль размера n-1.

Более общая гипотеза Штейна состоит в том, что трансверсаль к Размер n-1 существует не только в латинских квадратах, но и в любом массиве n на n символов, если каждый символ встречается ровно n раз.

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

Каждый латинский квадрат размером n на n имеет частичную трансверсаль размера 2n / 3.
Каждый латинский квадрат размером n на n имеет частичную трансверсаль размера n - sqrt (n).
Каждый латинский квадрат размером n на n имеет частичное пересечение размером n - 11 log 2 (n).

Алгоритмы

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

Приложения

Статистика и математика

В схеме экспериментов латинские квадраты являются частным случаем планов столбцов для двух блокирующих факторов :

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

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

Наборы латинских квадратов, которые ортогональны друг другу. нашли применение как коды исправления ошибок в ситуациях, когда связь нарушается большим количеством типов шума, чем простой белый шум, например, при попытке передачи широкополосного Интернета по линиям электропередач.

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

ABCD [1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1] EFGH [1 3 4 2 2 4 3 1 3 1 2 4 4 2 1 3] IJKL [1 4 2 3 2 3 1 4 3 2 4 1 4 1 3 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}}}

{\ 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 будет взята как:

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

{\ begin {matrix} 12 и 12 и 123 и 124 \\\ end {matrix}}

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

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

{\ begin {matrix} 1 2 1234 4 \\\ end {matrix}}

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

Математические головоломки

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

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

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

Настольные игры

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

Агрономические исследования

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

Геральдика

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

Обобщения

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

См. также

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

Примечания

Ссылки

Bailey, RA (2008). «6 строк-столбцов и еще 9 о латинских квадратах». Дизайн сравнительных экспериментов. Издательство Кембриджского университета. ISBN 978-0-521-68357-9. MR 2422352.
Dénes, J.; Кидвелл, А. Д. (1974). Латинские квадраты и их приложения. Нью-Йорк-Лондон: Academic Press. п. 547. ISBN 0-12-209350-X. MR 0351850.
Shah, Kirti R.; Синха, Бикас К. (1989). «4-х строчные конструкции». Теория оптимальных дизайнов. Конспект лекций по статистике. 54. Springer-Verlag. С. 66–84. ISBN 0-387-96991-8. MR 1016151.
van Lint, J. H.; Уилсон Р.М. (1992). Курс комбинаторики. Издательство Кембриджского университета. п. 157. ISBN 0-521-42260-4.

Дополнительная литература

Dénes, J. H.; Кидвелл, А. Д. (1991). Латинские квадраты: новые разработки в теории и приложениях. Анналы дискретной математики. 46. Пол Эрдёш (предисловие). Амстердам: Academic Press. ISBN 0-444-88899-3. MR 1096296.
Хинкельманн, Клаус; Кемпторн, Оскар (2008). План и анализ экспериментов. I, II (Второе изд.). Вайли. ISBN 978-0-470-38551-7. MR 2363107.
- Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов, Том I: Введение в экспериментальный план (Второе изд.). Вайли. ISBN 978-0-471-72756-9. MR 2363107.
- Хинкельманн, Клаус; Кемпторн, Оскар (2005). Планирование и анализ экспериментов, Том 2: Расширенный экспериментальный план (Первое издание). Вайли. ISBN 978-0-471-55177-5. MR 2129060.
Кнут, Дональд (2011). Искусство программирования, Том 4A: Комбинаторные алгоритмы, часть 1. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 978-0-201-03804-0.
Лэйвайн, Чарльз Ф.; Маллен, Гэри Л. (1998). Дискретная математика с использованием латинских квадратов. Серия Wiley-Interscience по дискретной математике и оптимизации. Нью-Йорк: John Wiley Sons, Inc. ISBN 0-471-24064-8. MR 1644242.
Shah, K. R.; Синха, Бикас К. (1996). «Рядно-столбчатые конструкции». В S. Ghosh и C. Р. Рао (ред.). Планирование и анализ экспериментов. Справочник по статистике. 13 . Амстердам: Издательство Северной Голландии, стр. 903–937. ISBN 0-444-82061-2. MR 1492586.
Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные проблемы при планировании экспериментов (исправленная перепечатка изд. Wiley 1971 г.). Нью-Йорк: Дувр. ISBN 0-486-65685-3. MR 1102899.
Стрит, Энн Пенфолд ; Street, Deborah J. (1987). Комбинаторика экспериментального дизайна. Нью-Йорк: Издательство Оксфордского университета. ISBN 0-19-853256-3. MR 0908490.

Внешние ссылки