Латинский прямоугольник

В комбинаторной математике латинский прямоугольник представляет собой $размера r \times n$ матрицу (где $r \leq n$ ), использующую $n$ символов, обычно числа $1, 2, 3, ..., n$ или $0, 1, ..., n - 1.$ в качестве его записей, при этом ни одно число не встречается более одного раза в любой строке или столбце. ^[1]

Латинский прямоугольник $размера n \times n$ называется латинским квадратом . Латинские прямоугольники и латинские квадраты также можно описать как оптимальные раскраски ладейных графов или как оптимальные раскраски ребер полных двудольных графов . ^[2]

Пример латинского прямоугольника 3×5: ^[3]

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

Нормализация

Латинский прямоугольник называется нормализованным (или уменьшенным ), если его первая строка и первый столбец расположены в естественном порядке. ^[4]^[5]

Приведенный выше пример не нормализован.

Перечисление

Обозначим через $L$ ( $k, n$ ) количество нормализованных $латинских прямоугольников размера k$ × $n$ . Тогда общее количество $k$ × $n равно$ латинских прямоугольников ^[6]

{\frac {n!(n-1)!L(k,n)}{(n-k)!}}.

Латинский прямоугольник 2 × $n$ соответствует перестановке без неподвижных точек . Такие перестановки получили название несогласованных перестановок . ^[4] Перечисление перестановок, несогласных с данной перестановкой, представляет собой знаменитую проблему встреч . Перечисление перестановок, несогласных с двумя перестановками, одна из которых представляет собой простой циклический сдвиг другой, известно как редуцированная задача о менажах . ^[4]

Количество нормализованных латинских прямоугольников $L (k, n)$ малых размеров определяется выражением ^[6]

k\n	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2		1	1	3	11	53	309	2119
3			1	4	46	1064	35792	1673792
4				4	56	6552	1293216	420909504
5					56	9408	11270400	27206658048
6						9408	16942080	335390189568
7							16942080	535281401856
8								535281401856

Когда $k$ = 1, то есть строка только одна, поскольку латинские прямоугольники нормализованы, выбора, какой может быть эта строка, нет. Таблица также показывает, что $L (n - 1, n) = L (n, n)$ , что следует из того, что если отсутствует только одна строка, недостающая запись в каждом столбце может быть определена на основе свойства латинского квадрата , а прямоугольник может быть однозначно распространяется на латинский квадрат.

Расширяемость

Свойство возможности продлить латинский прямоугольник без одной строки до упомянутого выше латинского квадрата можно значительно усилить. А именно, если $r < n$ , то можно добавить $n - r$ строк к $латинскому прямоугольнику размера r \times n$ , чтобы сформировать латинский квадрат, используя теорему Холла о браке . ^[7]

Полулатинские квадраты

Полулатинский квадрат — еще один тип неполного латинского квадрата. Полулатинский квадрат — это $размером n$ × $n$ массив $L$ , в котором некоторые позиции незаняты, а другие позиции заняты одним из целых чисел ${0, 1, ..., n - 1$ }, так что, если целое число $k$ встречается в $L$ , то оно встречается $n$ раз, и никакие два $k$ не принадлежат одной и той же строке или столбцу. Если $встречаются m$ разных целых чисел $в L$ , то $L$ имеет индекс $m$ . ^[8]

Например, полулатинский квадрат порядка 5 и индекса 3: ^[8]

1		0		2
	2	1		0
0	1		2
2	0		1
		2	0	1

Полулатинский квадрат порядка $n$ и индекса $m$ будет иметь $заполненные позиции на нм$ . Возникает вопрос, можно ли полулатинский квадрат дополнить до латинского квадрата? Несколько удивительно, но ответ всегда.

Пусть $L$ — полулатинский квадрат порядка $n$ и индекса $m$ , где $m < n$ . Тогда $L$ можно дополнить до латинского квадрата. ^[8]

Один из способов доказать это — заметить, что полулатинский квадрат порядка $n$ и индекса $m$ эквивалентен $латинскому прямоугольнику размера m$ × $n$ . Пусть $L = || а ij ||$ — латинский прямоугольник и $S = || б ij ||$ — полулатинский квадрат, то эквивалентность определяется формулой ^[9]

b_{ij}=k{\text{  if and only if  }}a_{kj}=i.

Например, латинский прямоугольник 3×5.

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

эквивалентен этому полулатинскому квадрату порядка 5 и индекса 3: ^[9]

0	2		1
2	0	1
		0	2	1
1			0	2
	1	2		0

так как, например, $a$ ₁₀ = 3 в латинском прямоугольнике, то $b$ ₃₀ = 1 в полулатинском квадрате.

Приложения

В статистике латинские прямоугольники находят применение при планировании экспериментов . ^{[ как? ]}

См. также

Примечания

^ Колборн и Диниц 2007 , с. 141.
^ Камни 2010 .
^ Бруальди 2010 , с. 385
^ Jump up to: ^а ^б ^с Денес и Кидуэлл 1974 , с. 150
^ Некоторые авторы, в частности Дж. Риордан, не требуют, чтобы первый столбец был в порядке, и это повлияет на достоверность некоторых формул, упомянутых ниже.
^ Jump up to: ^а ^б Колборн и Диниц 2007 , с. 142
^ Бруальди 2010 , с. 386
^ Jump up to: ^а ^б ^с Бруальди 2010 , с. 387
^ Jump up to: ^а ^б Бруальди 2010 , с. 388

Ссылки

Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис Холл, ISBN 978-0-13-602040-0
Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным планам (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 978-1-58488-506-1
Денес, Ж.; Кидуэлл, А.Д. (1974), Латинские квадраты и их приложения , Нью-Йорк-Лондон: Academic Press, стр. 547, ISBN 0-12-209350-Х , МР 0351850
Стоунз, Дуглас С. (2010), «Многие формулы для числа латинских прямоугольников» , Электронный журнал комбинаторики , 17 (1): Статья 1, 46, doi : 10.37236/487 , MR 2661404

Дальнейшее чтение

Мирский, Л. (1971), Трансверсальная теория: описание некоторых аспектов комбинаторной математики , Academic Press, ISBN 0-12-498550-5 , OCLC 816921720
Риордан, Джон (2002) [1958], Введение в комбинаторный анализ , Дувр, ISBN 978-0-486-42536-8

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

Вайсштейн, Эрик В., «Латинский прямоугольник» , mathworld.wolfram.com , получено 12 июля 2020 г.

[FOOTNOTEColbournDinitz2007p._141-1] Колборн и Диниц 2007 , с. 141.

[FOOTNOTEStones2010-2] Камни 2010 .

[3] Бруальди 2010 , с. 385

[DK150-4] Jump up to: ^а ^б ^с Денес и Кидуэлл 1974 , с. 150

[5] Некоторые авторы, в частности Дж. Риордан, не требуют, чтобы первый столбец был в порядке, и это повлияет на достоверность некоторых формул, упомянутых ниже.

[CD142-6] Jump up to: ^а ^б Колборн и Диниц 2007 , с. 142

[7] Бруальди 2010 , с. 386

[Bru387-8] Jump up to: ^а ^б ^с Бруальди 2010 , с. 387

[Bru388-9] Jump up to: ^а ^б Бруальди 2010 , с. 388

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]