Практическая часть
Пусть заданы два
латинских квадрата
,
где
подстановки степени n,
удовлетворяющие условиям
Латинские квадраты Ln и L’n называются ортогональными, если для любых упорядоченных различных пар (i, j) ≠ (k, l) выполнено условие
Если Ln и L’n ортогональны, то этот факт записывается следующим образом: Ln ⊥ L’n. Таблицу (si(j)), i, j=1,2, …, n, латинского квадрата Ln будем обозначать той же самой буквой Ln. Обозначим через (Ln L’n) таблицу, полученную наложением таблицы L’n на таблицу Ln , т.е. размещением в положении с координатами (i, j) пар (si(j), s’i(j)). Тогда условие (3.2) означает, что все пары, входящие в (Ln L’n), различны.
Определим операцию умножения латинского квадрата Ln = [s1, s2, …, sn] слева на подстановку s с помощью равенства sLn = [ss1, ss2, …, ssn]. Если Ln = [s1, s2, …, sn], L’n = [s’1, s’2, …, s’n] и Ln ⊥ L’n, то для любых подстановок s и ŝ имеем sLn ⊥ ŝL’n. В самом деле, для любых пар (i, j) ≠ (k, l) выполнено условие
В противном случае из равенств ssi(j) = ssk(l), ŝs’i(j) = ŝs’r(l), следовало бы si(j) = sr(l), s’i(j) = s’r(l), что противоречит условию (3.2). Полагая s=s1-1, ŝ = (s1’)-1, из пары ортогональных латинских квадратов Ĺn = s1-1Ln и Ĺ’n =(s1’)-1L’n, таблицы которых имеют одинаковые первые строки вида 1, 2, …, n. Такие латинские квадраты называются полунормализованными.
Пусть {Ln(1), Ln(2), …, Ln(r)} – множество латинских квадратов, таких, что
Покажем, что
Обозначим через Ĺn(i) полунормализованный латинский квадрат, соответствующий Ln(i), 1≤ i ≤r. Тогда Ĺn(i) ⊥ Ĺn(i), i ≠ j, 1≤ I, j ≤ r. Наложим таблицы r полунормализованных латинских квадратов. Ячейка со входами (1, j) содержит r элементов j. В ячейке со входами (2, j) все элементы различны. Действительно, пусть в ячейке (2, j) два элемента равны l, 1≤ l ≤n. Тогда в ячейке (1, l) уже имеется пара элементов, равных l, принадлежащих паре латинских квадратов; получаем противоречие с условием их ортогональности. Ни один из различных элементов в ячейке (2, 1) не может совпадать с элементами ячейки (1, 1). Отсюда следует неравенство (3.4).
Если r = n – 1, то множество попарно ортогональных латинских квадратов Ln(1), Ln(2), …, Ln(n-1) называется полным.
Заключение
Целью данной курсовой работы является исследование построения ортогональных латинских квадратов. Проведя все необходимые научные изучения, необходимо четко усвоить метод построения ортогональных квадратов, формулы которых будут представлены ниже.
Полученные знания статут существенным подспорьем в понимании раздела математики, структурной единицей которого является комбинаторика. Для достижения поставленной задачи необходимо обозначить итоговые формулы, которые послужат “путеводной звездой” в изучении данного вопроса:
Список литературы
1. Энциклопедический словарь юного математика/ сост. А.П. Савин-3-е изд. М., Педагогика-Пресс, 1999-360 с.
2. Латинские квадраты: Метод. указ. и задачи по факультативному курсу / Гонина Е.Е. Пермь, 1991.
3. Математика. школьная энциклопедия /гл. ред. С.М. Никольский-М.: Большая российская энциклопедия; Дофа, 1997-527 с.
4. Комбинаторика/ М. Холл, издательство “Мир”, 1970-266 с.