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

прямоугольная матрица размера [img: http://localhost:8080/file/031304-115.jpg] каждая строка к-рой является перестановкой (без повторений) элементов множества S, состоящего из га элементов, причем в столбцах каждый элемент встречается не более одного раза. При m = n Л. п. является латинским квадратом порядка п. Обычно S= {1, 2,..., п}, и о Л. п. говорят, что он построен на множестве S. Л. п. существует при любых натуральных т, п, [img: http://localhost:8080/file/031304-116.jpg] Примером Л. п. может служить матрица, первая строка к-рой есть (1, 2,..., га), а все последующие получаются из предыдущей циклич. сдвигом на один шаг. Л. п. размера [img: http://localhost:8080/file/031304-117.jpg] всегда может быть дополнен до латинского квадрата порядка птак, что первые m строк латинского квадрата будут совпадать со строками Л. п. Для числа L (m, n) Л. п. размера [img: http://localhost:8080/file/031304-118.jpg] верна следующая оценка снизу: [img: http://localhost:8080/file/031304-119.jpg] Л. п. наз. нормализованным, если его первая строка есть (1, 2,..., п). Число К(т, п).нормализованных Л. п. связано с L(m, п).соотношением: [img: http://localhost:8080/file/031304-120.jpg] Подсчет L(m, п).при m = 2,3 связан с классич. комбинаторными задачами:с задачей о числе беспорядков (см. Инверсия).и с задачей о супружеских парах. Так, число беспорядков Dn=K(2, п), а число размещений Un в задаче о супружеских парах есть число Л. п. размера [img: http://localhost:8080/file/031304-121.jpg] первые две строки к-рых суть: [img: http://localhost:8080/file/031304-122.jpg] Для Un верны формулы: [img: http://localhost:8080/file/031304-123.jpg] Число К(3, п).выражается через Dk и Ui: [img: http://localhost:8080/file/031304-124.jpg] где [img: http://localhost:8080/file/031304-125.jpg] Верна также следующая асимптотика: [img: http://localhost:8080/file/031304-126.jpg] где [img: http://localhost:8080/file/031304-127.jpg] - Эрмита многочлен. Известно также, что [img: http://localhost:8080/file/031304-128.jpg] Задача о перечислении Л. п., имеющих более трех строк, не решена (1982). При [img: http://localhost:8080/file/031304-129.jpg] [img: http://localhost:8080/file/031304-130.jpg] так, что [img: http://localhost:8080/file/031304-131.jpg] получена асимптотика: [img: http://localhost:8080/file/031304-132.jpg] На Л. п. распространяются нек-рые понятия и теоремы, связанные с латинскими квадратами. Так, два Л. п. [img: http://localhost:8080/file/031304-133.jpg] размера [img: http://localhost:8080/file/031304-134.jpg] наз. ортогональными, если все пары вида [img: http://localhost:8080/file/031304-135.jpg] различны. Множество Л. п., в к-ром любые два Л. п. ортогональны, имеет не более т-1 Л. п. Часто под Л. п. понимают следующее обобщение Л. п.: латинским прямоугольником размера [img: http://localhost:8080/file/031304-136.jpg] построенным на множестве 5, состоящем из пэлементов, наз. матрица размера [img: http://localhost:8080/file/031304-137.jpg] с элементами из S, встречающимися в каждой строке и каждом столбце не более одного раза. Л. п. размера [img: http://localhost:8080/file/031304-138.jpg] построенный на псимволах, может быть расширен до латинского квадрата порядка птогда и только тогда, когда каждый символ встречается в Л. п. не менее r+s-п раз.