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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Лати́нский квадра́т n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:


\begin{bmatrix}
A & B & C \\
C & A & B \\
B & C & A \\
\end{bmatrix}
который может быть представлен в виде {(1,1,A),(1,2,B),(1,3,C),(2,1,C),(2,2,A),(2,3,B),(3,1,B),(3,2,C),(3,3,A)}, где первый и второй элемент - позиция элемента в матрице, а третий - значение.

В настоящее время в качестве множества M обычно берётся множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.[1]

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли аддитивной группы кольца \mathbb{Z}_n: l_{ij}= (i+j-1) mod n.

История исследований латинских квадратов[править | править вики-текст]

Окно в честь Фишера с латинским квадратом 7-го порядка. Кембридж

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

Пары ортогональных латинских квадратов впервые были упомянуты Жаком Озанамом в 1725 году.[2] В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6192 решения (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера[1]. Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечётных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

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

В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).[3]

В 1900 году гипотеза Эйлера для n = 6 была подтверждена G. Tarry.[4] Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов.[5] В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 году Fisher предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.[6]

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.[7]

Число латинских квадратов[править | править вики-текст]

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) дает формула

 \prod_{k=1}^n \left(k!\right)^{n/k}\geq L(n)\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}[8]

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:


\begin{bmatrix}
A & B & C \\
B & C & A \\
C & A & B \\
\end{bmatrix}

Число R(n) нормализованных латинских квадратов n-го порядка (последовательность A000315 в OEIS) в n!(n-1)! раз меньше, чем L(n) (последовательность A002860 в OEIS).

Точные значения величины L(n) известны для n от 1 до 11:[9]

Число латинских квадратов
n R(n) L(n) Автор и год
1 1 1
2 1 2
3 1 12
4 4 576
5 56 161280 Euler (1782)
6 9408 812851200 Frolov (1890)
7 16942080 61479419904000 Sade (1948)
8 535281401856 108776032459082956800 Wells (1967)
9 377597570964258816 5524751496156892842531225600 Bammel и Rothstein (1975)
10 7580721483160132811489280 9982437658213039871725064756920320000 McKay и Rogoyski (1995)
11 5363937773277371298119673540771840 776966836171770144107444346734230682311065600000 McKay и Wanless (2005)

Отношения эквивалентности на множестве латинских квадратов[править | править вики-текст]

Два латинских квадрата называют изотопными, если один из них может быть получен из другого в результате изотопии — композиции из перестановки строк, перестановки столбцов и замены элементов множества M по подстановке из симметрической группы S(M).

Изотопия является отношением эквивалентности, поэтому множество латинских квадратов n-го порядка разбивается на непересекающиеся изотопические классы. Из одного латинского квадрата можно получить с помощью изотопии (n!)3 эквивалентных, но некоторые из них при этом могут совпасть с исходным, это называется автопаратопией. Доля латинских квадратов с нетривиальной группой автопаратопий стремится к нулю с ростом n.[9]

Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.

Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.[10]

Число классов эквивалентности
n Число главных классов Число изотопических классов
1 1 1
2 1 1
3 1 1
4 2 2
5 2 2
6 12 22
7 147 564
8 283657 1676267
9 19270853541 115618721533
10 34817397894749939 208904371354363006
11 2036029552582883134196099 12216177315369229261482540

Ортогональные латинские квадраты[править | править вики-текст]

Два латинских квадрата L=(lij) и K=(kij) n-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:


\begin{bmatrix}
1 & 2 & 3 \\
2 & 3 & 1 \\
3 & 1 & 2 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
1 & 2 & 3 \\
3 & 1 & 2 \\
2 & 3 & 1 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
(1,1) & (2,2) & (3,3)\\
(2,3) & (3,1) & (1,2)\\
(3,2) & (1,3) & (2,1)\\
\end{bmatrix}

Эйлер называл такие квадраты «полными». В его честь в научной литературе их раньше называли «эйлеровыми» или «греко-латинскими» (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.

Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n-го порядка. Максимально возможная мощность N(n) такого множества равна n-1, в этом случае множество называется полным.

При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.

Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида f_a(x, y)=ax+y при ненулевом a над полем \mathrm{GF}(n).[11] Пример построения полного множества попарно ортогональных латинских квадратов 4-го порядка (d — корень примитивного многочлена x^2+x+1 над \mathrm{GF}(2)):


\begin{bmatrix}
0 & 1 & d & d+1\\
1 & 0 & d+1 & d\\
d & d+1 & 0 & 1\\
d+1 & d & 1 & 0\\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
0 & 1 & d & d+1\\
d & d+1 & 0 & 1\\
d+1 & d & 1 & 0\\
1 & 0 & d+1 & d\\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
0 & 1 & d & d+1\\
d+1 & d & 1 & 0\\
1 & 0 & d+1 & d\\
d & d+1 & 0 & 1\\
\end{bmatrix}

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Нижние оценки числа N(n)
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
N(n)≥ 2 3 4 6 7 8 2 10 5 12 3 4 15 16 3 18 4 5 3 22 6 24 4 26 5 28 4 30 31

Построение ортогональных квадратов — сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырех ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.[12]

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

Частичные квадраты[править | править вики-текст]

Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.

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

Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причем никакое его подмножество условию однозначности не удовлетворяет.[13] Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:

Мощность критического множества
n 1 2 3 4 5 6
С(n) 0 1 3 7 11 18

Нерешенные задачи[править | править вики-текст]

Помимо задачи нахождения формулы для величины L(n), имеется большое количество нерешенных задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops’03:

  • Оценка максимального числа трансверсалей в латинском квадрате n-го порядка
  • Характеризация латинских подквадратов в таблице умножения луп Муфанг
  • Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна
  • Вычисление максимального t(n), при котором 2t(n) делит величину L(n)

Применение[править | править вики-текст]

Пример использования латинского квадрата в филателии

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.

Применение в криптографии. Протокол с нулевым разглашением[править | править вики-текст]

В настоящее время латинские квадраты активно применяются для реализации протоколов с нулевым разглашением. В частности для генерации MAC.
Пусть q={1,2,…,n}. Для данного латинского квадрата

LS=
\begin{bmatrix}
l_{1,1} & ... & l_{1,q} \\
. & ... & . \\
l_{q,1} & ... & l_{q,q} \\
\end{bmatrix}

b = q/2 варианты LS изотопные друг другу.

Предположим, пользователи (u_1, u_2, ..., u_k) образуют сеть. u_i имеет публичный ключ L_ui и L'_ui (обозначим два изотопных Латинских квадрата порядка n) и секретный ключ I_ui (обозначим изотопизм L_ui над L'_ui). u_i хочет доказать подлинность u_j, но он не хочет раскрывать секретный ключ (Доказательство с нулевым разглашением).

1. u_i случайным образом переставляет L_ui и получает другой латинский квадрат Н
2. u_i отправляет Н к u_j
3. u_j просит u_i либо:
— доказать что Н и L'_ui изотопны
— доказать что Н и L_ui изотопны
4. u_i выполняет просьбу. Он или
— доказывает что Н и L'_ui изотопны
— доказывает что Н и L_ui изотопны
5. u_i и u_j повторяют шаги 1-4 n раз

Ниже приведен псевдокод для посчета Хеш-функции

for k from 1 to q do
    begin
        d_k=1;
    end
for i from 1 to q do
    begin
    for j from 1 to q do
        begin
        for k from 1 to b do
            begin
                 d_l_ji=m_ij*d_l_ji;
            end
        end
    end

Хеш-сумма получится в векторе D=[d_1,...,d_n]
Пример использования:
Пусть q=8, b=4

LS=
\begin{bmatrix}
1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\
2 & 5 & 4 & 6 & 7 & 8 & 3 & 1\\
3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\
4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\
7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\
8 & 3 & 7 & 1 & 2 & 4 & 6 & 5\\
5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\
6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\
\end{bmatrix}


LS^1=
\begin{bmatrix}
7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\
5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\
1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\
3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\
8 & 3 & 7 & 1 & 4 & 4 & 6 & 5\\
6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\
2 & 5 & 4 & 6 & 7 & 8 & 3 & 1\\
4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\
\end{bmatrix}
LS^2=
\begin{bmatrix}
8 & 3 & 7 & 1 & 2 & 4 & 6 & 5\\
4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\
5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\
1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\
7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\
3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\
6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\
2 & 5 & 4 & 6 & 3 & 8 & 3 & 1\\
\end{bmatrix}


и

LS^3=
\begin{bmatrix}
1&7&3&8&5&6&4&2\\
3&8&1&7&6&5&2&4\\
7&1&8&3&4&2&5&6\\
5&2&6&4&3&1&7&8\\
2&5&4&6&7&8&3&1\\
4&6&2&5&8&7&1&3\\
8&3&7&1&2&4&6&5\\
6&4&5&2&1&3&8&7\\
\end{bmatrix}
LS^4=
\begin{bmatrix}
4&6&2&5&8&7&1&3\\
2&5&4&6&7&8&3&1\\
6&4&5&2&1&3&8&7\\
8&3&7&1&2&4&6&5\\
3&8&1&7&6&5&2&4\\
1&7&3&8&5&6&4&2\\
5&2&6&4&3&1&7&8\\
7&1&8&3&4&2&5&6\\
\end{bmatrix}


Предположим что передается следущее сообщение:

M=
\begin{bmatrix}
3 & 2 & 5 & 4 & 1 & 2 & 1 & 6\\
7 & 8 & 4 & 5 & 2 & 3 & 3 & 1\\
4 & 8 & 6 & 7 & 5 & 4 & 3 & 2\\
1 & 4 & 5 & 7 & 8 & 6 & 6 & 6\\
7 & 1 & 2 & 8 & 7 & 3 & 4 & 5\\
7 & 8 & 1 & 1 & 8 & 2 & 6 & 5\\
3 & 4 & 8 & 1 & 2 & 3 & 7 & 6\\
2 & 4 & 5 & 3 & 3 & 6 & 8 & 7\\
\end{bmatrix}


Перемещения строк для получения матриц с LS^1 до LS^4
 RP^1=
\begin{bmatrix}
5 & 7 & 1 & 3 & 6 & 8 & 2 & 4\\
\end{bmatrix}
 RP^2=
\begin{bmatrix}
6 & 4 & 7 & 1 & 5 & 3 & 8 & 2\\
\end{bmatrix}
 RP^3=
\begin{bmatrix}
1 & 3 & 5 & 7 & 2 & 4 & 6 & 8\\
\end{bmatrix}
 RP^4=
\begin{bmatrix}
4 & 2 & 8 & 6 & 3 & 1 & 7 & 5\\
\end{bmatrix}

Зададим вектор  D=
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{bmatrix}
И будем считать хэш по алгоритму приведенному выше:
Получим  D=
\begin{bmatrix}
1 & 7 & 5 & 4 & 4 & 5 & 8 & 1\\
\end{bmatrix}

Применение в криптографии. Схема разделения секрета[править | править вики-текст]

Схема с разделением секрета, в которой ключом является латинский квадрат L порядка n. Латинский квадрат держится в секрете. Между тем порядок латинского квадрата публикуется для всех. Разделение секрета основано на частичных латинских квадратах S={A_{i} | A_{i}} критические множества L}. Объединение может быть составлено из всех возможных критических множеств L или из множества критических множеств. Количество критических множеств зависит от порядка латинского квадрата и числа участников, участвующих в схеме.
Протокол:
Выбирается латинский квадрат L. Порядок n разглашается, но сам латинский квадрат остается в секрете и используется как ключ.
Множество S объединение критических множеств L.
Каждый участник получает долю (i, j,k) .
Когда участники собираются вместе они могут соединить свои части вместе и восстановить квадрат L.
Пример:
Выделим три частичных квадрата: C_{1}, C_{2}, C_{3}


\begin{bmatrix}
0 & . & . \\
. & 2 & . \\
. & . & . \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
.  & .  & . \\
.  & 2  & . \\
.  & .  & 1 \\
\end{bmatrix}
\quad\quad
\begin{bmatrix}
0 & . & .  \\
. & . & .  \\
. & . & 1  \\
\end{bmatrix}

И целый квадрат L

0 1 2
1 2 0
2 0 1

Мы можем легко убедиться, что все частные латинские квадраты C_{1}, C_{2}, C_{3} являются критическими множествами. Они могут быть однозначно расширены до полного латинского квадрата L. Это уникальное свойство теряется если любой элемент любого частичного латинского квадрата C_{1}, C_{2}, C_{3} удаляется.
Пусть S объединение трех критических наборов C_{1}, C_{2}, C_{3} . Тогда S =  {(1, 1, 1), (2, 2, 3), (3, 3, 2)}.
Мы распространяем трем участникам части S. Любые два участника могут восстановить полный латинский квадрат.
Полученный выше простой пример может быть расширен до общего случая.
В 1979 латинский квадрат был предложен в качестве хорошего кандидата для использования в секретных схемах распределения. Однако, Есть определенные ограничения для его применения, как описано ниже.
1) Сразу после распределения частей критического множества, частичная информация будет доступна любой несанкционированной группе. Это означает, что есть высокий шанс для любой несанкционированной группе, чтобы выяснить остальные части методом проб и ошибок. Таким образом, предложенная схема не идеальна.
2) Схема не является гибкой. В данном случае это просто схема расщепления секрета.
Хеширование
Если мы хотим, использовать хэш-сумму для хранения фиксированного секретного квадрата, например, латинского квадрата порядка 10, мы должны хранить 81 номер (последнюю строку и столбец хранить не обязательно). Четыре бита могут быть использованы для хранения ряда, так что нам понадобится 324 бит. В этом случае, мы можем выбрать SHA-384 или SHA-512. Если нам нужно использовать SHA-256, мы можем проступить следующим образом. 10 бит будем использовать для представления 3-го номера. Таким образом, мы сначала использовали 250 бит для представления 75 чисел, а затем следующие 4 бита для представления одного номера. В общей сложности, мы можем хранить 76 номеров. Зафиксируем частичный латинский квадрат в следующем формате. Выберем латинский квадрат порядка 10, который можно восстановить однозначно, удалив записи, как показано в таблице. Компромиссом здесь является то, что небольшой процент латинских квадратов порядка 10, не могут быть восстановлены однозначно и, следовательно, не могут быть выбран в качестве секрета.

x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x x .
x x x x x x x x . .
x x x x x x x x . .
x x x x x x x x . .
x x x x x x x x . .
x x x x x x x x . .
. . . . . . . . . .

Игры и головоломки с латинскими квадратами[править | править вики-текст]

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9.

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Euler L. Recherches sur une nouvelle espèce de quarrés magiques. — Middelburg, 1782.
  2. Ozanam J. Récréations mathématiques et physiques. — Paris, 1725.
  3. Cayley A. On Latin Squares // Messenger of mathematics. — 1890. — Т. XIX. — С. 135–137.
  4. Tarry G. Le problème des 36 officiers // Comptes Rendus Assoc. France Av. Sci.. — 1900. — Т. 29, part 2. — С. 170–203.
  5. MacNeish, Harris F. Euler Squares // Annals of Mathematics. — 1922. — Т. 23. — С. 221–227.
  6. Fisher R. A. Statistical methods for research workers. — Edinburg, London: Oliver & Boyd, 1925.
  7. Bose R. C.; Shrikhande S. S. On the falsity of Euler’s conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2 // Proc. Nat. Acad. Sci. U.S.A.. — 1959. — Т. 45. — С. 734–737.
  8. van Lint J. H., Wilson R. M. A Course in Combinatorics. — Cambridge University Press, 1992.
  9. 1 2 McKay B. D., Wanless I. M. On the number of Latin Squares // Ann. Combin.. — 2005. — Т. 9. — С. 335-344.
  10. Черемушкин А. В. Почти все латинские квадраты имеют тривиальную группу автострофий // Прикладная дискретная математика. — 2009. — Т. 3(5). — С. 29–32.
  11. Bose R.S. On the applications of the properties of Galois fields to the problems of construction of Hyper-Graeco-Latin squares // Indian J. Stat.. — 1938. — Т. № 3. Part. 4. — С. 323–338.
  12. Dulmage A. L., Johnson D., Mendelsohn N. S. Orthomorphisms of groups and orthogonal Latin squares I // Canad. J. Math.. — 1961. — Т. 13. — С. 356–372.
  13. Nelder J. Critical sets in latin squares // CSIRO Division of Math. and Stats. — 1977. — Т. Newsletter, 38.

Литература[править | править вики-текст]