КОМБИНАТОРНЫЕ ЗАДАЧИ

Значение КОМБИНАТОРНЫЕ ЗАДАЧИ в математической энциклопедии:

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

Одной из классических К. з., фигурирующей еще в мифах Древнего Востока, является построение магического квадрата, т. е. расположение первых n² натуральных чисел в квадрате nxn так, чтобы все суммы по строкам, столбцам и диагоналям были равны одному и тому же числу. Напр.,

- магический квадрат при n=3. Известен ряд методов построения таких квадратов (см., напр., [1]). Определение числа магических квадратов порядка ппри n>4 представляет трудную еще нерешенную (1978) задачу. Ряд К. з. был рассмотрен Л. Эйлером (L. Euler). Одна из них - задача о 36 офицерах, состоящая в том, чтобы указанное число офицеров 6 различных воинских званий и из 6 различных полков так расположить в ячейках квадрата (каре), чтобы каждая колонна и каждая шеренга содержали одновременно одного и только одного офицера каждого ранга и каждого полка. Квадрат размером содержащий в ячейках элементы 1, 2, . . ., п, наз. латинским, если элементы в каждой строке и каждом столбце различны. Два латинских квадрата наз. ортогональными, если при их наложении все п ² пар элементов в ячейках различны. Задача о 36 офицерах эквивалентна задаче о существовании пары ортогональных латинских кнадратов порядка 6. Л. Эйлер высказал гипотезу о несуществовании ортогональных латинских квадратов порядка n=4k+2, k=l, 2, ... В 1900 Г. Тарри (G. Tarry) подтвердил эту гипотезу для п=6. и тем самым доказал, что задача о 36 офицерах не имеет решения. В 1959-60 была доказана теорема о существовании пары ортогональных латинских квадратов для каждого n=4k+2, k= 2,3, ... (см. [2]).

Другая задача, рассмотренная Л. Эйлером,- задача о кёнигсбергских мостах, формулируемая следующим образом. Имеется семь мостов, соединяющих берега реки, протекающей через город, и два острова, расположенные на ней. Спрашивается, можно ли обойти все мосты, проходя по каждому только один раз, и возвратиться в исходную точку. Полагая, что вершины соответствуют районам суши, а ребра - мостам, эту задачу можно сформулировать в виде вопроса о возможности последовательного обхода графа, изрбраженного на рис. 1, с условием однократного использования его ребер и возвращения в исходную точку (см. Графа обход). Если в графе такой обход возможен, то говорят, что он обладает эйлеровым циклом. Л. Эйлер установил, что такой цикл в графе существует тогда и только тогда, когда он связен, и число ребер, инцидентных каждой вершине, четно. Так как граф на рис. 1 не удовлетворяет этому требованию, то задача о кёнигсбергских мостах неразрешима. Она неразрешима и в том случае, если отбросить требование совпадения точек начала и конца обхода. В этом случае решается воцрос о существовании эйлеровой цепи в графе. Граф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин, инцидентных нечетному числу ребер, равно 0 или 2. Граф на рис. 1 не удовлетворяет и этому условию (см. [3]).

В 1859 У. Гамильтон (W. Hamilton) придумал игру "Кругосветное путешествие", состоящую в отыскании такого пути, проходящего через все вершины (города) графа, изображенного на рис. 2, чтобы посетить каждую вершину однократно и вернуться в исходную. Пути в графах, обладающие таким свойством, наз. гамильтоновыми циклам и. Необходимые и достаточные условия существования гамильтонова цикла в графе пока (1978) неизвестны (см. [3]).

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд приложений в исследовании операций, в частности при решении нек-рых транспортных проблем. Она состоит в следующем: имеется нек-рое количество городов, расстояния между к-рыми известны; нужно найти кратчайший путь, проходящий через все города и возвращающийся в исходный.

В 1847 Р. Киркман (R. Th. Kirkman) поставил и решил задачу о 15 школьницах. Они должны были гулять ежедневно пятью группами по три в каждой группе. При этом необходимо было так составить расписание для их прогулок, чтобы каждая школьница в течение семи дней смогла точно один раз попасть в одну группу с каждой из остальных. Эта задача связана с задачей построения системы троек, поставленной Я. Штеинером (J. Steiner, 1853). Системой троек Штейнера порядка vназ. такой набор троек из множества, содержащего vэлементов, что каждая пара элементов входит точно в одну тройку. Системы троек Штейнера описаны для v<15. Оказывается, что для v-3,7, 9 системы троек единственны, с точностью до эквивалентности (подстановка vэлементов, перестановка троек); для v=13 существуют две неэквивалентные системы троек; при v=15 таких троек 80. Для v>15 число различных систем троек Штейнера пока (1978) неизвестно. При v>3 система троек Штейнера является частным случаем неполной частично уравновешенной блок-схемы.

Классическая задача о встречах состоит в следующем. Имеются две одинаковые колоды из празличных карт каждая. Необходимо определить D_nrr=0, 1, ... , и,- число расположений карт во второй колоде таких, что при сравнении соответствующих карт первой и второй колоды число совпадений равно r, r=0, 1, ... , n. Частный случай этой задачи при r=0 впервые был сформулирован П. Монмором (P. Montmort, 1708). Л. Эйлер рассматривал задачу отыскания числа членов определителя, не имеющих общих элементов с главной диагональю, эквивалентную определению D_no.

Задача о встречах была исходным пунктом для возникновения раздела комбинаторного анализа, связанного с иссдедованнем перестановок с ограниченными позициями. На совокупности S_n подстановок степени п, действующих на множестве X, можно ввести расстояние р, полагая

Тогда

причем

В терминах расстояний между подстановками можно сформулировать и другую классическую К. з., называемую обычно задачей о супружеских парах. Она состоит в определении числа М _п рассаживаний псупружеских пар на 2n местах за круглым столом так, чтобы ни один муж не сидел рядом со своей женой. Тогда

М _п =2n!U_n, U_n=|{s:r(s,e) = n,r(s, c) = n,}|,

где е- единичная подстановка, а с=(1, 2, ... , п). Получена формула:

Если

то величина U_n(s₁, s₂ )зависит только от цикловой структуры и может быть выражена в виде формулы

с использованием Чебышева многочленов (см. [4]).

Тесную связь с приведенными задачами имеет проблема определения числа L_kn латинских прямоугольников и числа L_n латинских квадратов. Латинский прямоугольник может рассматриваться как упорядоченный набор подстановок s₁, s₂, .. ., s_k степени п таких, что p(s_i, s_j)=n.Показано, что

Установлено, что при k<п ^1/3-^e, е>0,

где при Число латинских квадратов порядка п известно до n=9 включительно.

Задача о числе разбиений натурального числа n на слагаемые впервые появилась в письме Г. Лейбница (G. Leibniz) к Я. Бернулли (J. Bernoulli) в 1669. Однако разработка методов решения целого класса задач такого типа была осуществлена Л. Эйлером, к-рый эффективно использовал для этой цели производящие функции, задаваемые в виде бесконечных произведений. Он, в частности, установил, что число разбиений m+n на пслагаемых равно числу разбиений тна не более чем пслагаемых, равно числу разбиений тна слагаемые, не превосходящие п, и равно числу разбиений на празличных слагаемых.

Классическая задача размещения состоит в определении числа С _пт(r)способов размещения тразличных предметов в празличных ячейках с заданным числом rпустых ячеек. Получено, что

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

Лит.:[1] Постников М. М., Магические квадраты, М., 1964; [2] Холл М., Комбинаторика, пер. с англ., М., 1970; [3] Оре О., Теория графов, пер. с англ., М., 1968; [4] Риордан Д ж., Введение в комбинаторный анализ, пер. с англ., М., 1963; [5] Харари Ф., Теория графов, пер. с англ., М., 1973.

В. Я. Сачков.