§ 23. Латинские прямоугольники

Рассмотрим множество объектов, элементы которого обозначены через

Латинским прямоугольником называется прямоугольная таблица с строками и столбцами, где каждая строка и каждый столбец — размещения без повторений соответственно из объектов по и из объектов по На рис. 66 приведен латинский прямоугольник размера на множестве из восьми объектов. Пусть Тогда строки латинского прямоугольника — перестановки объектов. Такой латинский прямоугольник называется нормализованным, если элементы его первой строки записаны в естественном порядке (см., например, рис. 67).

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

Если через обозначить число латинских прямоугольников размера а через число нормализованных, то

Очевидно, что

где число беспорядков (см. (14.11)).

Рис. 66

Рис. 67.

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

равно числу в задаче о супружеских парах. Число всех латинских прямоугольников размера дает формула Риордана (см. [36]):

где наибольшее целое число, меньшее

Рис. 68

Пример. Вычислим

По формулам (14 11), (20 8) и из таблиц 14.1 и 22.1

Число латинских прямоугольников при неизвестно. Можно доказать (см. [35] и [36]), что

Латинский квадрат. При говорят о латинском квадрате. Примером латинского квадрата служит таблица умножения конечной группы. На рис. 68 изображен латинский квадрат размера . Если число латинских квадратов, в которых

элементы первой строки и первого столбца записаны в естественном порядке, то

а если в естественном порядке записаны только элементы первой строки, то

Известные значения приведены в таблице 23.1 (из [36]).

Таблица 23.1

На рис. 69 перечислены латинские квадраты размера 4X4.

Рис. 69.

Заметим, что квадраты б) и в) — таблицы умножений двух возможных групп порядка 4.

УПРАЖНЕНИЯ

(см. скан)