АРРЫЁЭ МАТНЁМАТ1С§
IV: 50МЕ А5РЕСТ5 ОР АЫАЬУ515 АЫБ РКОВАВ1ИТУ
А ЗЩУЕУ ОР СОМВШАТОК1АЬ АЫАЬУ515
ВУ
МАЦ8НАЫ НАЫ,
(ТНе ОЫо 8Ше
уокк
ИБ 5ОЫ5, ШС.
1958

ЁЙБЛИОТЕКА СБОРНИКА «МАТЕМАТИКА»
м. холл
КОМБИНАТОРНЫЙ
АНАЛИЗ
Перевод с английского
К. А, Р ЫБНИКОВА
ИЗДАТЕЛЬСТВО
ИНОСТРАННОЙ ЛИТЕРАТУРЫ
Москва 1 963

В комбинаторном анализе исходят из рассмотрения
множеств дискретных элементов, к которым применяются
комбинаторные операции упорядочения и выбора. Фор-
Формирование общей теории комбинаторного анализа, спо-
собной охватить огромное количество задач, которые
решаются в различных отделах математики применением
комбинаторных суждений, еще не завершено. Литературы
на русском языке по комбинаторному анализу еще нет.
Настоящая книга Маршалла Холла младшего — аме-
американского математика, известного советскому читателю
по переводу его книги „Теория групп",— является обзо-
обзором современного состояния теории комбинаторного ана-
анализа в области теорем перечисления и выбора, а также
построения различных схем. Автор отметил задачи и на-
направления, наиболее перспективные с его точки зрения.
В тексте рассматриваются задачи из теории чисел, теории
конечных групп, геометрии и топологии.
Книга представляет интерес для широкого круга ма-
математиков-специалистов, в особенности для тех, кто за-
занимается прикладными вопросами и желает применить
комбинаторный аппарат современной математики.
Редакция литературы по математическим наукам

ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ
Комбинаторный анализ — новая математическая дисцип-
дисциплина. Он вырастает из совокупности приложений методов
комбинаторного характера в различных областях матема-
математики: теории вероятностей, геометрии, теории чисел, вычи-
вычислительной математики и др. Исходной позицией комбина-
комбинаторного анализа является рассмотрение множеств дискрет-
дискретных элементов, относительно которых введены комбинатор-
комбинаторные операции упорядочения и выбора. Многочисленность
и разнообразие задач, для решения которых в наше время
применяется комбинаторный анализ, придают этому раз-
разделу математики многоплановость.
Роль комбинаторного анализа в математике быстро
возрастает. Она определяется теоретической и практической
значимостью, которую комбинаторные методы приобрели
как часть так называемой конечной математики.
Строго говоря, называть комбинаторный анализ новым
отделом математики можно только условно. Издавна изве-
известные приемы элементарной комбинаторики к концу
XVII века преобразовались в математический аппарат ло-
логических суждений (Г. В. Лейбниц) и теории вероятностей
(Я. Бернулли). Примерно через сто лет, в конце XVIII —
начале XIX века, в германских государствах Европы была
предпринята попытка создать комбинаторный анализ как
единую математическую науку. Этому отдали много сил
немецкие математики (К. Ф. Гинденбург, Я- Штейнер,
Эшенбах, Роте и др.). Несоответствие, обнаружившееся ме-
между громоздким символическим аппаратом и слабыми еще
оперативно-вычислительными возможностями, приостановило
развитие этой науки. Комбинаторная школа к середине
XIX века распалась, и само название „комбинаторный анализ"
постепенно было забыто.

Предисловие к русскому изданию
Предлагаемый советскому читателю обзор 1}, составлен-
составленный американским математиком Маршаллом Холлом, при-
приоткрывает возможности возрождаемого комбинаторного ана-
анализа и указывает направления, в которых, по мнению
автора, наиболее важен и вероятен успех. В этом основное
значение настоящего издания.
Обзор неполон. В нем не нашли отражения комбинатор-
комбинаторный аппарат теории вероятностей, теории программирования
и многие другие вопросы. Сведения о состоянии работ в об-
области современного комбинаторного анализа отрывочны.
Однако необходимо учитывать, что комбинаторный анализ
находится в стадии формирования, что этот процесс проте-
протекает бурно и что в направлении консолидации его структуры
предстоит еще большая работа.
По нашему мнению, неудачно написана гл. I, являющаяся
по характеру изложения скорее заключительной, нежели
вводной. Однако мы сохранили ее текст, чтобы советские
читатели могли познакомиться с мыслями автора и со
структурой комбинаторного анализа т з!а1и пазсепсН.
К- А. Рыбников
*) Обзор опубликован в IV томе серии Зигуеуз ш аррНес1 та!Ье-
таИсз, вышедшем под названием «Зоте а$рес!з о\ апа1у$1$ апс! рго-
ЬаЫШу».

ГЛАВА I
ВВЕДЕНИЕ И РЕЗЮМЕ
1. Введение
Содержание комбинаторного анализа нелегко определить
Его можно сравнить с теорией чисел в том отношении,
что он возник из совокупности разнообразных задач, ко-
которые даже в наше время не охватываются никакой еди-
единой теорией или методом. Делая попытку дать определение,
будем говорить, что в комбинаторном анализе рассматри-
рассматриваются задачи о расположениях элементов в соответствии
с точно определенными правилами и выясняется, сколькими
путями такие расположения могут быть осуществлены.
Настоящая работа состоит из трех основных разделов:
а) методы перечисления; б) теоремы выбора; в) существова-
существование и построение схем.
В комбинаторной задаче, указывая правила, согласно ко-
которым строятся расположения, логически мы обязаны по-
поставить вопрос, можно ли такие расположения вообще
осуществить; если можно, то как перейти к построению
расположений, и, наконец, сколько существует различных
решений. Если задача состоит в том, чтобы записать по-
положительное целое число в виде суммы трех целых поло-
положительных чисел, то как вопрос о существовании решений,
так и метод нахождения их являются по существу три-
тривиальными. Таким образом, основной задачей является
нахождение числа решений. При этом мы должны усло-
условиться о том, какие решения считать различными; так,
в примере, который мы рассматриваем, должно быть точно
указано, будем ли мы различать суммы трех целых чисел,
отличающиеся лишь порядком слагаемых.
Большинство задач о перечислении таковы, что для них
вопрос о существовании и построении решений по суще-
существу тривиален. Однако следует оговориться, что три-
тривиальные методы построений могут оказаться чересчур

8 Гл. I. Введение и резюме
трудоемкими. Как и следует ожидать, для отыскания менее
громоздких методов необходимы дополнительная теория и
значительное мастерство. Именно в этом состоит трудность
задачи о коммивояжере. В этой задаче дана таблица рас-
расстояний между всеми парами из п городов. Требуется
отыскать такой циклический маршрут, пересекающий все
города и возвращающийся в начальную точку, который
был бы минимальным по общему расстоянию. Тривиальный
метод состоит в испробовании всех (п — 1)! маршрутов и
выборе кратчайшего. Но проблема нахождения решения
с помощью меньшего числа испытаний не решена.
Теоремы выбора являются по своей природе теоремами
существования. Дано множество объектов и требуется
выбрать подмножество с некоторыми твердо установленными
свойствами. В упомянутых теоремах рассматриваются
необходимые и достаточные условия того, чтобы этот вы-
выбор был возможным.
Так, в теореме о различных представителях, доказан-
доказанной Филиппом Холлом, утверждается, что если даны п
множеств 5Х, 52, ...,5Л некоторых объектов, то будут су-
существовать различные представители а19 а2, ..., ап этих мно-
множеств, где а1 — элемент 5; и а1^ф^у если 1=^=]\ при соб-
соблюдении, очевидно, необходимого условия, что среди всех
элементов любых к множеств A ^к^п) найдутся по
меньшей мере к различных.
Эти теоремы интересны сами по себе, а также важны
для построения расположений. Гофман недавно показал,
что многие из этих теорем вытекают из теоремы двойст-
двойственности в линейном программировании.
В задачах о существовании и построении схем мы имеем
дело по большей части с тактическими конфигурациями.
В тактической конфигурации мы хотим построить из о
объектов Ь блоков, каждый из которых состоит из к объек-
объектов, таких, что всякая комбинация объектов будет встре-
встречаться одинаково часто в каждом блоке. Эти схемы могут
быть охарактеризованы определенными параметрами; отно-
относительно параметров существует несколько необходимых
условий, обычно легко находимых. В некоторых случаях
необходимые условия являются также достаточными, а
ъ других — заведомо нет. В случае уравновешенной непол-
неполной блок-схемы требуется расположить V объектов в Ь бло-

1. Введение
ках по к объектов в каждом, так что каждый объект
будет встречаться в г блоках, а каждая пара объектов
будет попадаться всего % раз. Здесь необходимые усло-
вия Ьк = V^ и г (к—1) = Л, (с;—1) легко находятся.
Первое — подсчетом всего количества появлений объектов
в схеме (учитывая, с одной стороны, что Ь блоков содер-
содержат по к объектов каждый, а с другой стороны, что
объектов всего V и каждый из них встречается г раз).
Чтобы найти второе условие, заметим, что отдельный
объект встречается в г блоках с к — 1 другими объек-
объектами; с другой стороны, требуется, чтобы он встречался
X раз с V — 1 оставшимися объектами, отсюда г (к;— 1) = % X
( — 0- Например, в случае систем троек Штейнера
— 3, к=1, и мы имеем ЗЬ = V^, 2г — V — 1.
Здесь г = ^ — \)\2, Ь = ю(ю — \)\Ъ.
Следовательно, V должно быть вида 6^ —[— 1 или6^-|-3.
Справедливо и обратное: для каждого числа V вида 6/ -]- 1
или Ы-\-3 существует система троек Штейнера. С дру-
другой стороны, для конечных проективных плоскостей поряд-
порядка п мы имеем А, = 1; к — г — п-\-1; у = Ъ = п2 -\-п-\-\.
Здесь возможен не всякий порядок п. Если п — простое
число или степень простого, то существует по меньшей
мере одно решение; до настоящего времени неизвестны
решения для чисел п другого вида. Установлено, что
существует бесконечно много порядков, которые невоз-
невозможны, начиная с п — 6, 14, 21, 22.... Это целые
числа, сравнимые с 1 или 2 по модулю 4 и не имеющие
вида п = х2-\-у2, при целых х и у. Первый неопределенный
случай — это п=10; вплоть до настоящего временной
остался неразрешимым даже с помощью быстродействую-
быстродействующих вычислительных машин.
Следует заметить, хотя это и будет очевидным для
читателя, что настоящий обзор не является исчерпывающим.
Материал подобран с таким расчетом, чтобы проиллюстри-
проиллюстрировать задачи и методы рассматриваемой области матема-
математики. Наибольшее внимание уделено недавним исследо-
исследованиям, которые, по-видимому, обещают дать далеко
идущие результаты.

10 Гл. I. Введение а резюме
\
2. Общие направления и итоги
Комбинаторный анализ является относительно новой
ветвью математики, и справедливо было бы утверждать!
что только в последние десять лет были развиты достав
точно общие и эффективные методы. Некоторые из ранее!;
существовавших задач предлагались как курьезы, например!
задача о 36 офицерах, поставленная Эйлером в 1779 г.;
Интерес к системам троек вырос из проблем алгебраиче-;
ской геометрии, восходящих к Штейнеру. Позже блок-
схемы были использованы для статистического исследова-
исследования контрольных испытаний. Исследования по основаниям
геометрии привели к изучению конечных геометрических
систем, которые сами являются комбинаторными схемами.
Многие проблемы теории групп, в частности исследование
мультипликативных транзитивных групп, по своей природе
являются комбинаторными.
В последние годы были подвергнуты активному иссле-
исследованию комбинаторные задачи весьма практического ха-
характера. Так, в Университете Дж. Вашингтона были изу-
изучены транспортные задачи, в частности составление
расписания движения судов. «Дженерал электрик ком-
пани» использует быстродействующие вычислительные
машины для составления плана распределения своей про-
продукции. Была решена задача о распределении должностей,
что явилось шагом к решению задачи о коммивояжере,
которая интенсивно изучалась в «Рэнд корпорейшен».
К этим задачам были применены методы теории игр и ли-
линейного программирования.
Первые работы по применению быстродействующих вы-
вычислительных машин ^отдельным задачам были выполнены
Лемерсом и Томпкинсом. Для проектного задания, предло-
предложенного летом 1955 г. Национальным научным фондом,
автору удалось использовать машину СВАК 1} в Калифор-
Калифорнийском университете (Лос-Анжелес), чтобы построить
большое число новых комбинаторных схем.
На первом этапе развития комбинаторного анализа ком-
1) 5\УАС — Ма1юпа1 Выгеаи о[ 51зш1аг1$, \Уез{егп
Сотри1ег. — Прим. перев.

2. Общие направления и итоги 11
бинаторные методы включали тождества для биномиаль-
биномиальных коэффициентов, весьма ограниченные технические
приемы и рекуррентные методы. Для этой части теории
наилучшим источником является книга Нетто [7]. В конце
XIX века школа английских математиков, в которой наибо-
наиболее выдающейся фигурой был Мак-Магон старший, добилась
существенного продвижения, используя производящие функ-
функции и операторы для получения формальных алгебраиче-
алгебраических и аналитических выражений комбинаторных величин.
Хотя этот подход был весьма общим, он не мог рассмат-
рассматриваться как эффективный, за исключением некоторых спе-
специальных случаев. Если производящая функция оказы-
оказывается элементарной или, как в случае функции распре-
распределения, принадлежит к хорошо известному классу транс-
трансцендентных функций, то может быть сделано многое. Но
в большинстве случаев непосредственная погоня за
построением формального аппарата более утомительна,
нежели простое перечисление.
Школа индийских статистиков с 1935 г. проделала
большую работу в области блок-схем. Их методы были
весьма искусными и эффективными. С тех пор как Бозе
перешел в Университет Северной Каролины, многие из его
американских учеников, в особенности Коннор, добились
значительных успехов.
Число американских математиков, которые начали в те-
течение последних нескольких лет заниматься комбинаторным
анализом, возрастает. Некоторые из них, включая Брука,
Ризера и автора, пришли к этому кругу вопросов, исходя
из исследований по основаниям геометрии и соответствую-
соответствующих задач в неассоциативных алгебрах. Лемерса привела
к этим проблемам теория чисел. Другие, в особенности
Томпкинс, Флуд, Кун и Гофман, встретились с комбина-
комбинаторным анализом, изучая логику, линейное программиро-
программирование и теорию игр.
Интерес русских к комбинаторному анализу, по-види-
по-видимому, невелик, насколько об этом можно судить по
опубликованным работам. Хотя Л. А. Скорняков и другие
были весьма активны в исследованиях по основаниям
геометрии, они мало сделали в области финитной геомет-
геометрии, которая имеет истинно комбинаторный характер.
П. К. Ращевский выполнил одну работу по конфигурациям

12 Гл. I. Введение и резюме
Фано элементарной природы. Наиболее обширная работа
комбинаторного характера — это работа М. А. Гаврилова
о релейно-контактных схемах. Он написал большое число
статей и собрал их в книгу „Теория релейно-контактных
схем", опубликованную Издательством Академии наук
в Москве в 1950 г. В этой книге много места уделено
декодированию цепей и применениям булевой алгебры
к анализу цепей.

ГЛАВА II
МЕТОДЫ ПЕРЕЧИСЛЕНИЯ
1. Общие замечания
Главными средствами для подсчета числа решений
комбинаторных задач являются: 1) перестановки и со-
сочетания; 2) производящие функции; 3) рекуррентные ме-
методы и 4) графические методы. В задачах, решения ко-
которых легко построить, могут тем не менее возникнуть
большие трудности при подсчете числа решений в связи
с различным определением эквивалентности решений. Так,
задача представления целого числа п в виде суммы неотри-
неотрицательных целых чисел
A)
как нетрудно показать, имеет 2п~г решений, если целые
числа а19 а2, ...,аг рассматриваются как упорядоченное
множество. Но, если они берутся в виде неупорядоченного
множества, то число представлений р(п) является гораздо
более сложной функцией. По-видимому, имеет место общее
правило, по которому упорядоченные решения задачи
легче перечислить, нежели неупорядоченные. Наконец,
в задачах перечисления всегда возникает вопрос о том,
какие из ответов являются подходящими. Для функции
р(п) существуют рекуррентные формулы, хорошо приспо-
приспособленные для вычисления ее последовательных значений,
а также бесконечные ряды. Рекуррентные формулы наибо-
наиболее полезны для составления таблиц значений р(п)9 тогда
как ряды дают информацию о порядке величины р(я),
а также удобны для вычисления отдельных значений.
2. Перестановки и сочетания
Упорядоченное множество г объектов а19 ..., аг, выбран-
выбранных из множества п объектов, называется перестановкой п
элементов, взятых по г. Если все выбранные объекты раз-

14 Гл. II. Методы перечисления
.
личны, число перестановок будет
= п (п — 1) (п — 2)... (п — г + 1).
Если допускаются повторения, то этим числом будет пг.
Так, число перестановок из 5 букв аЪсйе, взятых по три,
есть 5-4-3 = 60, если буквы выбираются различными,
и 53= 125, если допускаются повторения. Неупорядоченное
множество г объектов, выбранных из множества п объек-
объектов, называется сочетанием из п элементов по г. Если мы
отыскиваем число сочетаний различных объектов, то, по
скольку каждое сочетание встречается г! раз в переста.
новке, число их будет равно
п(п— 1)...(п —г + 1) п\ / п
г(г — 1) ... 1 г1(п — г)\~\ г
т. е. биномиальному коэффициенту. Но если допускаются
повторения, мы не можем найти это число, деля пг на
соответствующие делители, так как перестановки приводят
к сочетаниям различной кратности. Так, в сочетаниях из
5 букв по 3 сочетание ааа возникает из единственной пере-
перестановки, ааЬ — из 3 перестановок и аЬс — из 6 переста-
перестановок. Чтобы найти это число, мы вынуждены прибегнуть
к некоторому искусственному приему. Присоединим все
множество к каждому сочетанию и перепишем полученное
множество в порядке следования букв. Так, исходя из
сочетания ЬЬс, выбранного из множества аЬсйе, мы полу-
получаем запись аЪЪЪсске. Эта запись полностью определяется
помещением в п-\-г — 1 интервалов между буквами п — 1
отметок, разделяющих различные буквы таким образом:
а\ЪЪЪ\сс\й\е. Число способов, которыми можно это про-
проделать, будет равно
C)
и это есть, следовательно, число сочетаний из п по г с
допущением повторений. Эта задача может также рас-
рассматриваться, как задача о разбиении, так как если до-
доесть число, показывающее, сколько раз берется /-й эле-
элемент, то требуется определить число решений уравнения

2. Перестановки и сочетания 15
в неотрицательных целых х1 (порядок следования чи-
чисел х существен). Если мы добавим единицу к каждому
х и положим У/= *,+ !, то задача будет состоять в том,
чтобы найти число решений уравнения
в положительных целых у19 ..., уп. Если мы возьмем
п-\-г точек и сделаем п — 1 отметок в п-\-г—1 интерва-
интервалах между ними, то мы можем рассматривать ух как число
точек первого множества, у —второго и т. д., снова
/Л-1-г_Г
получая число ( ^ |
Тот же способ мы можем применить к задаче нахож-
нахождения г-сочетаний чисел 1,2, ..., /г, не содержащих двух
последовательных чисел. Поставим отметки после каждого
выбранного числа. Если перед первой отметкой находится
хх чисел, между первой и второй отметкой — х2 чисел и,
наконец, после последней отметки — хг+1 чисел, то мы
имеем
где хх целое число, не меньшее единицы, х2...хг_г
суть по меньшей мере два, а хг+1 — неотрицательное число.
Соответственно
г г G)
что является представлением числа п — г-\-2 в виде суммы
г-{-1 положительных целых чисел, а число таких пред-
представлений равно (п г~т~ V Если мы рассматриваем 1,
2, ..., п как цикл, то чтобы получить число выборок г
элементов, не содержащих двух последовательных, мы
должны исключить из вышеуказанного числа выборок те,
которые включают единицу и п. Это—решения для слу-
случая у1==1 ц уг+1 = \у и МЬ1 получаем уравнение п — г =
, которое имеет [П^_^ ) решений в
натуральных числах. Таким образом, в циклическом слу-
случае возможны ± (п ~_^7"!) выбоРок-

16 Гл. II. Методы перечисления
Итак, многие перечисления могут быть найдены по
средством подсчета сочетаний, соответствующих прямс
или косвенно данной задаче. Они приводят к биномиаль-1
ным или полиномиальным коэффициентам. Многие задачи
могут быть разбиты на несколько отдельных задач, реше-
ниями каждой из которых служат некоторые биномиаль-
биномиальные коэффициенты, так что решение первоначально по-
поставленной задачи является суммой биномиальных коэф-^
фициентов. Поэтому даже решение простой задачи может
потребовать вычисления таких сумм. Существует много
тождеств, включающих биномиальные коэффициенты,-
Таково, например, тождество
ей
/2дУ_(-1)"(ЗпI
)
впервые доказанное Диксоном [3] в 1890 г. и более просто —
Лунгреном [5] в 1947 г. Приведем некоторые простые и
полезные тождества:
п
п
(9с)
п
Первые два тождества следуют из соотношения A-\~х)п =
= V1
*? )хк, если положить в нем сначала #=1, а затем
# =—1. Для получения третьего соотношения мы диф-
дифференцируем исходное соотношение, а затем полагаем
х = —1; четвертое же получается г-кратным дифференци-
дифференцированием, после чего х полагается равным —1.
Перестановки и сочетания могут быть применены Кг
перечислениям и косвенным образом, если применить важ-

2. Перестановки и сочетания 17
ную общую формулу, выведенную Сильвестром. Предполо-
Предположим, что п объектов рассматриваются по отношению к
некоторым свойствам А1У А2, ..., Ап. Пусть Л^ (/ = 1, ..., АО
объектов имеют свойство Аь, Нц объектов имеют как
свойство А-1У так и Ар а в более общем виде М\/я...:/, объ-
объектов имеют все свойства Л/,, Л*2, ..., Д-,. Тогда, если
N @) есть число объектов, не имеющих ни одного из
свойств, то
(-1)' 2 #,,.../,+ ...+(-1)^,,...*. (Ю)
Это доказывается легко1*. Объект считается один раз в п>
если не имеет никаких свойств, и совсем не учитывается
во всех остальных членах. Рассмотрим объект, который
имеет в точности I ^ 1 свойств. Тогда он принимается за
1 в общем числе пу за —/в —Л^/» за (о ) в 2-1^/7 и
вообще за (—1)*Л) в члене (— I)"9 ^ -ЛГ/, /я... /,. Но
для ^ ^ 1 из тождества (9Ь) мы имеем
-'+ (У + • • • +(- О' (У + • • ■ =0. (И)
Таким образом, всякий объект, не обладающий никаким
из свойств, вносит 1 в правую часть формулы A0), а объ-
объект, обладающий I ^ 1 свойствами, вносит 0. Это доказы-
доказывает формулу. Таким же образом, если N (г) есть число
объектов, обладающих точно г свойствами, то
A2)
Метод, основанный на использовании тождества A0), известен
давно. Он известен под различными названиями: метод включения и
ключения, метод решета, символический метод, метод перекрестной
классификации.- Прим. перев.
2 М. Холл

18 Гл. II. Методы перечисления
Здесь объект, обладающий точно г свойствами, вносит 1 в
первую сумму и ничего не вносит в остальные. Объект,
имеющий в точности ^^> г свойств, вносит (—1M"~г(]( )
в сумму (-1)<-'(8) X #Л ...V Но
что получается, если в (9с1) положить п = { и разделить
обе части на (—1)гг! Таким образом, объекты, имеющие
более чем г свойств, вносят 0 в правую часть формулы A2),
и эта формула доказана.
Одним из приложений формулы A0) является решение
задачи о беспорядке1}. Мы ищем число перестановок
а, а2 ... ап A4)
п чисел 1, 2, ..., п, таких, что а^ь для всех /=1,
2, ..., п. Рассмотрим множество 5 всех п\ перестановок
Ьг Ь2 ... ЬпУ и пусть свойство А1 состоит в том, что
Ь = 1. Тогда для всяких 11 ^
поскольку они являются перестановками, в которых 5 объек-
объектов закреплены в своих позициях, а остальные объекты
свободны. Здесь число беспорядков есть число N @), и
применение формулы A0) дает равенство
= п\ — п(п— 1I+^ (л — 2)!+...+
которое после упрощений имеет вид
а это есть целое число, ближайшее к -1
1 )и н азывается также задачей о встречах.— Прим. перев.

3. Рекуррентные формулы и производящие функции 19
3. Рекуррентные формулы и производящие функции
Число беспорядков для п элементов было впервые най-
найдено Эйлером рекуррентным методом, который можно найти
у Нетто [7], стр. 66. Пусть ип будет числом беспорядков
для 1, 2, ..., п. Находим непосредственно, что и1 = 0,
и = 1, и, = 2. Предположим, что а1У а2, ..., ап — неко-
некоторый беспорядок. Тогда ( "' п ) есть переста-
\а1 и2 ... ип/
новка, переставляющая все буквы. Здесь ах может прини-
принимать какое-либо одно из п—1 значений 2, ..., п. При
фиксированном выборе а1=/ мы имеем частичную пере-
перестановку
где аг ... ап суть числа 1,2, ...,/'— 1 »<ягу —[— 1» • •., п.
Такие частичные перестановки бывают двух типов: те, в
которых <2у=7М, и те, для которых а^^=\. Эти типы пол-
полностью исчерпывают все виды перестановок и взаимно
исключают друг друга. В первом типе мы имеем переста-
перестановку
(^, ...,/, •••,/> ...,/2 \ . I .
^*2» * ' • » * » • • • » #/» • • • » ^д/
которую можно ассоциировать с беспорядком 2, ..., п
Л*
Обратно, если в каком-либо беспорядке 2, ..., п мы заменим
нижнее /на 1, то получим частичную перестановку первого
типа. Следовательно, их число будет ип^г. Что касается пе-
перестановок второго типа № •••'/» * * *' М , то, если мы
вычеркнем РА, останется беспорядок 2, ...,*/ — 1, / +
4—1
"г» •-., п и число беспорядков будет ип_2. Поскольку
ил-1 и ип_2 не зависят от выбора / и / может принимать
{*—1 различных значений, мы получим ип = (п— 1)Х
^(мй-1ТИв-1)' Формула приводит к тому же результату,
что и другие методы. Обобщая этот метод, Джейкоб

20 Гл. II. Методы перечисления
[2] и позднее Керавала [4] нашли рекуррентный прием
для нахождения числа трехстрочных латинских прямо-
прямоугольников. Это число равно п\ ип, где ип удовлетворяет
соотношению
+ (п + 3) (п + 4) (я8 + 8л + 13) ип+2 +
+ 2 (п + 2) (л + 3) (п + 4) (п2 + 5п + 3) и„+,
а первыми значениями будут
Метод Джейкоба и Керавала состоит в исследовании трех-
трехстрочных таблиц
а,
,
в которых во второй и третьей строках используются
обязательно все те же самые буквы, что в первой и второй,
но две из этих букв могут быть заменены новыми. Можно
рассмотреть шесть различных вариантов таблицы с непов-
неповторяющимися значениями в столбце, и для каждого из них
будут существовать числа ип, Vп и т. д. беспорядков.
Между ними найдены соотношения, которые и привели
к указанному выше рекуррентному приему.
С последовательностью чисел и0, и1У и2, ..., ип, ...
мы можем связать степенной ряд / (х) = ио-\- ихх -\- и2х2 -[-...
... -|- ипхТг -Ь • • •» который называется производящей функ-
функцией для ип. Рекуррентные соотношения для ип будут часто
приводить к определенным соотношениям для 1(х), и если
нам удастся найти явное выражение этой функции, то мы
тогда сможем вычислить ип. Наоборот, знание свойств
функции может привести к рекуррентным соотношениям
для ип; рассматривая }(х) как аналитическую функцию,-
мы можем применить теорему Коши для вычисления и^
точно или приближенно. На этом этапе комбинаторные зада-
задачи становятся по существу аналогичными многим задачам ана-
аналитической теории чисел. Иногда более удобно рассматривать

3. Рекуррентные формулы и производящие функции 21
ряды !(х) = ио + и1х-{'и2х12\-\г . .. +ия*/п!+ .. . или
даже ряды других типов, включая ряды Дирихле и ряды
Ламберта.
Приведем пример, иллюстрирующий этот метод. Отыщем
число способов ип образования бинарного, но неассоциа-
неассоциативного произведения п сомножителей, взятых в порядке
а а ... ап. Здесь и2 == 1, а для трех сомножителей мы имеем
{ага^пг и а, (ад), откуда и9 = 2. Положим формально, что
и = 1. Если бинарное произведение является соединением
первых г букв, умноженным на некоторое соединение остав-
. шихся п — г букв {аг ... аг) (аг+1 ... ап), то первые г букв
можно скомбинировать иг способами, а остальные]я—г букв—
ип_г способами. Таким образом, мы получаем рекуррентную
формулу для л^2, ип = игип_1-\-ихип_х-\Г ,. . -]гип-1и11)-
Этому соотношению удовлетворяет и соглашение и1 = 1.
Положим, что I (х) = игх-\-и2х2-{- ... -\-ипхп-{- ..., и,
отбросив предосторожности, продолжим рассуждения фор-
формально, игнорируя все вопросы о сходимости. Полученная
рекуррентная формула эквивалентна формальному соотно-
соотношению и (х)]2 = — х-{-Пх). Решая его как квадратное
уравнение, получим /(я) = A — у \ —4х)/2, где мы ставим
знак минус, чтобы иметь ряды без постоянного члена. Те-
Теперь, представляя эту функцию степенным рядом, мы най-
найдем, что коэффициент при хп будет
П\
Эта формула упрощается и приводится к виду х>п =
— [B/г—2)!]/[п! (п—1I]. Мы можем теперь провести рассужу
дения в обратном порядке, чтобы проверить себя и заклю-
заключить, что ип = Vп. Функция /(*) = A — У\ — Щ\2—ана-
литическая в круге |#|<Ст» и> следовательно, в ее сте-
степенном ряде коэффициент при хп есть Vп. Теперь внутри
круга сходимости функция [}(х)]2—также аналитическая
и, так как [}(х)]2 — [(х) — х, мы получаем, сравнивая
Это выражение иногда называется конволюцией или сверткой.
"Прим. перев.

22 Гл. П. Методы перечисления
коэффициенты при хп, я^2, что ип = х)грп.т1-\- .. . -}-
Л"Х)п-1°\' Так как и^ = V^=^ и рекуррентное соотно-
соотношение то же, что и выше, то ип = юп = [Bгс — 2)!]/[лг! (п— 1)!]
для всех п^2.
Если мы имеем линейную рекуррентную формулу с
постоянными коэффициентами ип+г = а1ип+г_1-}г ... -\-агип>
то легко видеть, что производящая функция [(х) = и
-\-игх-\-... -\-ипхп-\- ... является рациональной:
=
1 ~— A-уХ ~~~ ш , , с*-ДГ
где формулы
выражают соотношения между исходными значениями
^о» • * •» "г-1 и производящей функцией. Если аг = 0, мы мо-
можем рассматривать рекуррентное соотношение низшего по-
порядка. Взяв
в качестве характеристического полинома, мы сможем по-
показать, что общее решение задачи дается в виде
где Аг (п) — произвольный полином относительно п степени
е1—1, (е1 — кратность корня с^).
Мак-Магон в своей двухтомной книге [6] широко раз-
развил теорию рекуррентных методов и производящих функ-
функций. Здесь нет возможности дать сколько-нибудь удовле-
удовлетворительное описание этой работы. Однако, быть может,
нам удастся передать некоторые особенности его методов.
Если ах, ..., ап — некоторые неопределенные вели-
величины, то
= (* — аг)...(х — ап) = хп — а,*"-1+ ... + (— \)па
где а1У а2, ..., ап — хорошо известные элементарные сим-

3. Рекуррентные формулы и производящие функции 23
метрические функции
Если т=с1 + с1+ ••• +С5> гДе с,^с8>...>сг есть
разбиение целого числа /п, то существует симметрическая
функция от величин а, связанная с этим разбиением,
Н(сл, ..., сс)= У.а/!^/,2 • • • #5*, гДе мы берем в точности
один член каждого вида. Если мы теперь обозначим кт
сумму ^/Л = 2^(^!» •••» О» гДе суммирование ведется по
всем разбиениям т, то получим основную симметрическую
функцию степени т. Теперь соотношение между к и а не
зависит от п:
1
ИаХ ~~~~ й<Л
2 о
Отсюда мы вычисляем:
^з = ^1 —2а1а2 + аз»
Мы можем выразить комбинаторные величины как коэф-
коэффициенты, возникающие в результате действий над вели-
величинами /г. Так, если мы хотим, следуя Мак-Магону, найти
число способов разбиения семи элементов а, а, а, E, р,
V» б на множества из четырех и оставшихся трех элемен-
элементов, то это будет коэффициент А C, 2, 1, 1) в произведе-
произведении /14й8, где /г4 и Нь суть функции от четырех неопреде-
неопределенных величин а, р, у, б. Этот коэффициент равен 11.
Трудность здесь, как и в других случаях, состоит в том,
что, хотя комбинаторная величина и представлена как
коэффициент, нет никаких указаний на то, как найти его
значение. Чтобы дать различные выражения для получае-
получаемых здесь функций, необходимы некоторые тождества и
теоремы.

24 Гл. II. Методы перечисления
Теорема, которую Мак-Магон называет главной теоре-
теоремой, такова: I
Главная теорема. Если Х19 Х2, ..., Хп заданы
посредством соотношения (X г, Х2, ..., Хп) = А (х1У ..., хп)^
где А — (аи) есть пу^п-матрица, то коэффициент при
хС\ • •. хСп в разложении произведения Хс^ ... Хспп равен
коэффициенту при х*1 ... хспп в разложении дроби
1
A - а,*,) A - а2х2) ... A - апхп)
где знаменатель символический и в его разложении член
а^... ах должен быть заменен минором Л, образованным
из 1-х, \-х, ..., 1-х строк и столбцов Л.
В качестве приложения этой теоремы Мак-Магон вьь
2М /О \ *
числил биномиальную сумму V (—^)к ( и) » найденную
первоначально Диксоном [3] в 1890 г. и не так давно
(в 1947 г.) Лунггреном [5]. Мак-Магон заметил, что
)
V ( 1)Й(Т) —эт0 коэффициент при хтутгт в выра*
жении (у — г)т(г — х)т(х — у)т и главная теорема приме-
/0-1 1\
няется для случая А = \ 1 0 — 1
\— 1 1 0
Разлагая знаменатель | A — ахх) A — а2у) A — аьг) \ со-
согласно условию, принятому в теореме, получим
ах | х — \ а21 у — | а, \ г +1 ага21 ху +1 ахаг \ хг
агаь \уг — \ аха2аг \ хуг
или, после вычисления миноров, \-\-ху-\-хх-\-уг. Следо-
Следовательно, нам надо отыскать коэффициент при хтутгт в
разложении
4 - - 1
Так как каждый член имеет четную степень, то сумма

3. Рекуррентные формулы и производящие функции 25
_— ——
т / \ з
чп ( \)к ( ) равна нулю, если т не является чет-
ным. Если т = 2п, т. е. четно, то положим уг = и2,
д ху = ш2, так что хуг = тт, и в разложении дроби
^ _\^ у2 _|_ ^ будем искать коэффициент при и2пюгпхю2п.
Он должен получиться из члена (—\уп(и2-\-V2^{^ыJуп,
и с помощью полиномиальной теоремы мы сможем найти
результат Диксона:*
п [(Зп)!]
В качестве частного примера выражения комбинатор-
комбинаторных величин через коэффициенты Мак-Магон ([6], т. I,
стр. 253) представил как коэффициент число латинских
квадратов вида п\п. Если это число обозначить через
Ь, то будем иметь
Этот результат был выведен посредством операторов. Од-
Однако он недостаточно хорошо приспособлен для вычисле-
вычислений, зависящих от п-х степеней суммы п\ членов. Большая
часть сочинения Мак-Магона посвящена исследованию опе-
операторов. Мы вынуждены ограничиться упоминанием двух
операторов Хаммонда. Если а19 ..., а1 являются, как и
выше, элементарными симметрическими функциями, то
++а
есть дифференциальный оператор, применяемый к функ-
функциям от а, рассматриваемым как независимые переменные.
В свою очередь, если
т = е\Р\ + е2р2 ~Ь • • • 4" егРг (Р1 ^ Р2 ^ • •' ^ Рг)
есть разбиение числа т, где ^4- — множитель при р(, то мы
введем обозначения {р\1 р\2 ... р^) для соответствующей
симметрической функции. Тогда операторы Э3 определя-
определяются так, что
?
р Р? ... Ргг) = 0, если 8=^=р191 = 1, . •., г,

26 Гл. II. Методы перечисления
Зависимость между операторами й8 и операторами В8 точно
такая же, как зависимость между степенными суммами]
а/и элементарными симметрическими функциями.]
;
Именно, по правилу Ньютона,
Существует много взаимозависимостей между этими и дру-
другими операторами, но автор не смог найти достаточно при-
примеров, где эти операторы вели бы к результатам, которые
легко вычислить.
4. Разбиения
Разбиение положительного целого числа п есть пред-
представление этого числа в виде суммы целых положитель-
положительных чисел п = а1-\-а^-\' ... -}-ак. Здесь почти никогда
не возникает вопроса о существовании разбиения; задача
обычно состоит в отыскании числа распределений. Инте-
Интересным примером проблемы существования является гипо-
гипотеза Гольдбаха о том, что каждое целое четное число ^ 4
может быть записано как сумма двух простых чисел; од-
однако она, собственно, относится к области теории чисел,
хотя при исследовании разбиений трудно разграничить
комбинаторные и теоретико-числовые задачи. Мы можем
искать число распределений п на определенное число к
частей или же оставить это число неуточненным. Мы мо-
можем считать существенным или несущественным порядок
частей аг, а2, ..., ак. В силу этого возникают четыре
разных вопроса о числе распределений. На два из них, в
случаях когда порядок частей существен, ответить легко.
Другие два вопроса гораздо более трудны.
Если мы расположим в ряд п единиц и сделаем к— 1
отметок в к — 1 промежутках между ними, то ряд единиц
разделится на к частей и мы таким образом получим я =
= аг -\- аг -[-...-]- ак, где а19 а2, ..., ак — числа единиц
в каждом отрезке. Следовательно, число решений в данном
/п 1
случае является биномиальным коэффициентом ( ,

4. Разбиения 27
Если мы не будем задавать число частей к, то смо-
сможем получить упорядоченное распределение, делая от-
отметки либо в каждом промежутке между единицами, либо
не в каждом. Это может быть проделано 2п способами;
следовательно, число упорядоченных разбиений равно 2п~1.
Мы не можем получить число неупорядоченных раз-
разбиений, деля число упорядоченных разбиений на подходя-
подходящий делитель, так как разбиение с повторяющимися ча-
частями не дает стольких разбиений, сколько их дает раз-
разбиение с тем же числом различных частей.
Назовем Рк(п) число разбиений п на к (неупорядочен-
(неупорядоченных) частей. Очевидно, что п = п есть единственное раз-
разбиение на одну часть, так что Р1(п)=1. Мы можем найти
двойную рекуррентную формулу для Рк(п) следующим обра-
образом. Если п = ах-{-а%-\- ... +а* — разбиение п на к неу-
неупорядоченных частей, я — к = (а1 — 1) -{- (ай — 1) -(- • • • +
-\-(ак—1) — разбиение п — к на к или меньше частей,
так как если а1=1, то а(—1=0. Это соответствие
к
взаимно однозначное, так чтоРк(п) — \\Р.(п — к). Оче-
1 = 1
видно, Рк(к)=\9 так как к = ах-\-.. . -\-ак имеет в ка-
качестве единственного положительного решения а1 = а2==
= ... =аЛ= 1. Таким образом, мы можем без труда запол-
заполнить таблицу для Рк(п).
п 123 456789 10
к
1
2
3
4
5
6
7
8
9
10
1
1
1
1
1
1
1
2
1
1
1
2
-2
1
1
1
3
3
2
1
1
1
3
4
3
2
1
1
1
4
5
5
3
2
1
1
1
4
7
6
5
3
2
1
1
1
5
8
9
7
5
3
2
1
1
11 15 22 30 42

28 Гл. II. Методы перечисления \
" *■ ' — Ш
Из рекуррентных соотношений мы можем найти значе
ния Рк(п) для малых к. Так: ,
я = 0B)
Л я=1B)
I
« = 0F)
п=1F)
п = 2 F)
п = 3 F)
п = 4 F)
л = 5 F). [
к
Доказательство того, что рк (п) = V Р1 (п) приблизительна
п2
12
п2
12
м2
1 О |
п2
п2
12
1
12
1
3
1
4
1
3
1
12
1 (п— 1
1=1
равно ^ (? I), дал Аулук [1] в 1942 г. Этим подтверж*
дается то, что можно было ожидать, а именно: так как дл*
больших значений п в большинстве разбиений п на к ча-
частей все части различные, число упорядоченных разбиений,
которое равно B~|), приблизительно в к\ раз больше*
чем число неупорядоченных разбиений. |
Общее число р(п) неупорядоченных разбиений п, оче-*
п
видно, равно У^Рь(п). Но это не наилучший способ вы-
вычисления р(п). Мы имеем производящую функцию ;
" Р (») *• = (^) (,-пЬ,) ((Т^г,) • • • (^Ь

4. Разбиения 29
Если мы положим п = ах-\-аг + • • • + яи» гДе аг
есть число частей равных / в разбиении п, то непосред-
непосредственно видно, что в разложении бесконечного произведения
-1
содержится член лг" = л:а1(л:2)а2 .... (х')а* • • •> гДе каждый
(*')** вносится соответствующим множителем A—х1)~1 и,
следовательно, для каждого разбиения имеется в точности
один член. Таким образом, доказывается формальное
00»
равенство рядов ^р(п)хп и бесконечного произведения
со
(/ — х1) \ Это равенство будет справедливо, так как
1=1
бесконечное произведение сходится и является анали-
аналитической функцией внутри единичного круга.
Мы уже немного знаем о порядке величины р(п).
Теперь заметим, что в упорядоченных разбиениях п на к
частей одно неупорядоченное разбиение соответствует самое
большее к\ упорядоченным распределениям. Следовательно,
Л
как р(п)^>~кГ\к— \) Длявся"
кого к<^п, то р(п)^>Скпк для некоторой постоянной Ск.
Таким образом, р (п) растет быстрее, чем любая степень п.
С другой стороны, если бы для некоторой положительной
постоянной С и числа а > 1 мы имели р (п) > Са", то
ряд 2р(^)*" расходился бы вне круга радиуса 1/а,
а это противоречит тому факту, что он должен сходиться
внутри единичного круга. Таким образом, р (п) возрастает
быстрее, чем всякая степень п, и медленнее, чем любая
экспоненциальная функция ап для а>1. ,;;
Мы уже заметили, что 2 р (п) хп эквивалентна бесконечно-
со
му произведению ДA —хт). А это произведение само яв-
1
ляется производящей функцией 2 <?„*", где коэффициент
сп имеет комбинаторный смысл.
Очевидно, сп = А(п) — В(п), где А(п) есть число раз-
разбиений п на четное число различных частей, а В (п) есть

30 Гл. II. Методы перечисления
число разбиений п на нечетное число различных частей,
Эйлер впервые доказал замечательный факт, что сп почт)
всегда есть нуль. Более строго,
о* со
/1 у к\ II ^ /
Приведем здесь комбинаторное доказательство тождества!
Эйлера, найденное Дж. Франклином [§]. Представим раз-
разбиение п на неравные части точечной схемой, где частями
будут строки, самая короткая из которых будет наверху,;
самая длинная — внизу, а левые концы строк образуют
вертикальный столбец. Так, разбиение
изображается на схеме так:
Буквой Т обозначим „верхнюю линию" и проведем „боко-
„боковую линию44 5, состоящую из всех точек на прямой,
начинающейся с правого конца основания и образующей
угол 45° с основанием. В данном случае как 7\ так и 5
имеют по две точки. Исходя из этой схемы, мы можем
построить любую другую схему одним из двух методов:
1) если 7^5, переместить верхнюю линию так, чтобы
образовать новую боковую линию; 2) если Т^>8> пере-
переместить боковую линию так, чтобы образовать новую
верхнюю линию. К приведенной выше схеме применим
первый метод и, передвигая верхнюю линию, чтобы обра-
образовать новую боковую, получим схему

4. Разбиения 31
Она соответствует разбиению 16 = 7+ 6 + 3. Здесь 7 = 3,
5 = 2, и, следовательно, применим второй метод, приво-
приводящий снова к распределению 16 = 64-5 + 3-4-2. Эти
методы взаимно обратны и, если они применимы, устанав-
устанавливают взаимно однозначное соответствие между четными
и нечетными разбиениями. Для большей точности заметим,
что метод 1 применяется, когда 7<^5 или когда 7 = 5
и верхняя линия не пересекается с боковой линией;
метод 2 применяется, если 7>5+1 или если 7 = 5+1
и верхняя линия не пересекается с боковой. Таким обра-
образом, мы имеем взаимно однозначное соответствие между
четными и нечетными распределениями на неравные части
с двумя исключениями. Первый исключительный случай
G = 5 и верхняя линия пересекается с боковой) соответ-
соответствует разбиению вида
B6 -
четность которого совпадает с четностью к. Во втором
исключительном случае G = 5+1 и верхняя линия пере-
пересекается с боковой) разбиение имеет вид
четность этого разбиения также совпадает с четностью к.
Отсюда сп = А(п) — В(п) = 0, если п не имеет вида
C&*±&)/2, когда сп = (—1)*. Это доказывает тождество
Эйлера.
Произведя умножение в левой части тождества
(—1)** 2
к = 1
...-\-р(п)хп ...]=1,
найдем рекуррентное соотношение для р(п):
п — 2) — р(п — 5) — р(п — 7)-\-...
• ••+(- 1)*-р(П

32 Гл. II. Методы перечисления
удобное для вычисления последовательных значений р(п)\
1,
= 56,
= 2, рA2) = 77,
рD) = 5, рA4)=135,
рE) = 7, р A5)= 176,
рF)=11, рA6) = 231,
рG)=15, рA7) = 297,
р A8) = 385,
= 490,
рA0) = 42, р B0) = 627.
Изучая значения р (п), индийский математик Рамануджан
высказал и впоследствии доказал любопытные предложе-
предложения:
р Eп -\- 4) = 0 (той 5); р Gл + 5) = 0 (той 7);
Первые два из них нетрудно доказать, если, кроме тож-
тождества Эйлера, мы возьмем другое тождество того же рода,
найденное Якоби:
00
П A— хЛу=1 — Зх + 5*8 — 7*в+...=
оо
= 2
Обозначим
К(х) = х П A -хк)' = х П A —х*) П A —хк)г =
оо
— \)кх 2 2
= — СО
Здесь в ряде для К(х) мы имеем член с х5п+5у когда

4. Разбиения 33
Это приводит к соотношению
где как & + 1, так и 2/ + 1 сравнимы с 0 по модулю 5.
фф A)к+г№{\)
где ка + , + р у
Но коэффициент при таком члене равен (—1)к+г№-{-\),
и, таким образом, он кратен 5. Отсюда в К(х) коэффи-
коэффициент каждого члена с х*п+5 кратен 5. Теперь A—хк)*=в
==A— хък){тоАЪ)у а из этого следует, что A ~^5
= 1(тос15). Это означает, что коэффициенты степенного
ряда К(х) суть целые и кратные 5, за исключением сво-
свободного члена, который равен единице. Следовательно,
коэффициент при х*п+* в разложении
г\*(\ 2ч4 /A — *5)A —л10) ..
X) A X) ...{
— х)(\ —х2)...
кратен 5 так же, как и коэффициент при х5п+5 в разло-
разложении
A X) ( Л — X ) у 1 — X ) . . .
который равен /?Eп + 4)» откуда рEл-|-4) = 0(тос15).
Таким же способом мы можем доказать, что р Gп -|- 5) =
^ 0 (той 7), рассматривая в правой части разложения
*2 [A — *)A — **) • • -]* = х2 A — Зх + 5х2 — 7х* .. .J
член с показателем 7я4-7, возникающим из показателей
^ I 2 г~2— » и с коэффициентом, равным
( 1) +* Bй-|-1)B/-|-1). Но здесь из сравнения
вытекает, что
откуда
м. х
олл

34 Гл. II. Методы перечисления
Дальнейшие рассуждения проходят аналогично. Столь ж(
простого доказательства сравнения
по-видимому, не существует. Это зависит от более глубо-
глубоких свойств эллиптических и модулярных функций.
Существуют и другие любопытные арифметические свой<
ства р(п). Тождества Роджера — Рамануджана выражают
два из них:
X {X X) ^1
A - х) A - х2) ... A - хт)
1
X ) ... ^ 1 X ) у1 X ) . . •
И
х ' и
1 - х ^ A - х) A - х2)
I • • • =
- х2) ...
1
A — л:2) A — д;7) ... A — л:3) A — д:8) ...
Показатели в знаменателях справа образуют в каждо^
случае две арифметические прогрессии с разностью 5. Эти
прогрессии были найдены в 1894 г. английским математик
ком Роджером, а позднее независимо — Рамануджаном,
Харди [10] в своих лекциях о Рамануджане подчеркивает
что удивительное в этих формулах заключается в числе 5;
ряды слева имеют сравнительно хорошо известный вид,
Правая часть первого тождества перечисляет разбие
ния п на части вида 5/г-[-1, Ьк-\-А, а левая часть —
разбиения п на части с минимальной разностью 2. В ле-
левой части член с показателем степени п появляется тогда
когда п = т2 -\- ах -\- 2а2 -}-••• -\- тат> что соответствует
разбиению
+а2)+ ...
которое является разбиением п па т частей с минимальной

4. Разбиения 35
разностью 2, и, наоборот, разбиение на части с минималь-
минимальной разностью 2 имеет единственное представление этого
вида. Аналогично, так как т(т-\- 1) = 2-^4 -{- ...-[- 2т,
левая сторона второго тождества перечисляет разбиения
на части с минимальной разностью 2, где наименьшая
часть будет по крайней мере 2, и тождество указывает,
что число таких разбиений равно числу разбиений п на
части вида Ък~{-2, Ьк-\-?>.
Одной из наиболее интересных частей теории разбиений
является исследование асимптотического поведения р(п).
Мы будем следовать лекциям Харди о Рамануджане, где
дан превосходный обзор работ в этой области. Первым
приближением является р(п) ~ ехр ( я |/ 4-л1'
Если Р (х) = A__х)A_Х2) > то функция Р (х) — ана-
аналитическая внутри единичного круга и единичный круг
является ее естественной границей. В качестве стандарт-
стандартного приема аналитической теории чисел мы применяем
теорему Коши, чтобы найти
где С — контур, охватывающий начало координат. Точка
х=\ является нулем каждого из сомножителей произве-
произведения A —х){\ —х2) ... A —хк) ...; таким образом,
1 можно рассматривать как полюс весьма высокого порядка
Для Р(х). Аналогично х — —1 является нулем для поло-
половины сомножителей, и, более общо, # = ехр^^ является
нулем для каждого <у-го сомножителя. Таким образом,
оказывается, что х=\—самая сильная особенность для
на единичной окружности и что точки ехр^^ явля-
ются особенностями, интенсивность которых убывает по
Мере возрастания <у. Так как Р(х) — эллиптическая моду-
модулярная функция, то существуют функциональные уравне-
уравнения, которым она удовлетворяет. Так, если

36 Гл. //. Методы перечисления
ТО
ехр
BлГ2 V *У \б1о 1
х
где х — действительное число, близкое к 1, тогда х1 очень
близко к нулю, а Р(х1) весьма близко к 1. Таким обра-
образом, меняя Р(х1) на 1, получаем очень хорошее прибли-
приближение для Р(х) вблизи особенности х=\. Аналогичные
тождества дают хорошие приближения для р(х) вблизи
каждой рациональной точки на единичной окружности,
Если мы проводим аппроксимацию вблизи рациональных
точек со знаменателями ^, не превышающими некоторого С1,
и выбираем в качестве С окружность, лежащую внутри
единичного круга, радиус которого зависит от я и B, то
аппроксимирующие функции будут элементарными. Их
можно точно проинтегрировать и, при достаточной тща-
тщательности, оценить ошибку. Первый результат, доказанный
Харди и Рамануджаном, дает остаточный член порядка
ехр (бп1!2) для всякого положительного б, когда взято
достаточное число членов. Мак-Магон, применив рекуррент-
рекуррентные формулы, вычислил значения р(п) вплоть до я = 200,
найдя, что р B00) = 3 972 999 029 388. Восемь членов фор-
формулы Харди — Рамануджана дали это значение с ошибкой
порядка только 0,004, которая, естественно, была гораздо
меньшей, чем они рассчитывали получить. Это подсказало
им мысль проверить член, дающий ошибку, более внима-
внимательно, и они нашли, что при подходящих константах а
и М, если C = сш1/з, остаток не превышает Мп*1!*.
Радемахер [8], пытаясь упростить анализ Харди —
Рамануджана, внес небольшие изменения в их рассуждения
и был поражен, найдя сходящийся ряд для р(п):
со
р{п)= 2
<7=1
где
(«) =
л У2 йп
'2 Г '" 24
/■ - 2А

Литература 37
где и)р,д — корень 24-й степени из единицы. Здесь р про-
пробегает все целые числа, взаимно простые с ц и не пре-
превосходящие ц.
ЛИТЕРАТУРА
1. Аулу к (А и 1 иск Р. С), Ап азутрЫк Ьгти1а
!ог Ръ{п), ^. 1псИап Маш. 8ос. (Л^), 6, 113-114A942).
2. Джейкоб (ЛасоЬ 5. М.), ЬаПп гес1ап§1ез о! с!ер!Ь
1Ьгее, Ргос. Ьопйоп Ма(Н. 8ос. B), 31, 329—354 A930).
3. Диксон (Б1хоп А. С), Оп 1Ье зит о! 1Ье сиЬез о!
1Ье соеШс1еп1$ 1п а сег!а1п ехрапзюп Ьу 1Ье Ыпот1а1
1Ьеогет, Меззеп^ег о/ Маш., 20, 79-80 A890).
4. Керавала (Кега^а1а 5. М.), ТЬе епитегаНоп о!
1Ье 1а1т гес!ап§1е5 о! с!ер!Ь 1Ьгее Ьу теапз о! а AШе-
гепсе е^иа^^оп, Ви11. СакиИа МаНг. ^ос, 33, 119—127
A941).
5. Лунггрен (Ь]ип^^геп Ш.), Ап е1етеп!агу ргоо! о!
а 1огти1а о! А. С. Б1ХОП, [Ыогзк. Маг. Т'шззкг., 29,
35—38 A947).
6. Мак-Магон (МасМаЬоп Р.), СотЫпа1:огу Апа1у$15,
СатЪпс1§е 11туег5Иу Ргезз, СатЬг1A§е A915).
7. Нетто (Ы е 11 о Е.), ЬеЬгЬисЬ с1ег СотЫпа1ог1к,
В. С. ТеиЬпег, Ье1р21§, 1901.
8. Радемахер (КаAетасЬег Н.), А сопуег§еп1 зег1е5
1ог 1Ье рагИ11оп ГипсИоп р (п), Ргос. Маг. Асай. 5а., 23,
78—84 A937).
9. Франклин (РгапкПп 3.), 5иг 1е с1ёуе1орретеп1 Aи
рго^иИ 1пИп1 A — х) A — х2) ..., С. К. Асай. Гг., 92,
448—450 A881).
10. Харди (Нагс1у О. Н.), Кататфп, СатЪпс1§е \]п\-
Н Ргезз, СатЬпсЗ^е A940).

ГЛАВА III
ТЕОРЕМЫ ВЫБОРА
1. Основные теоремы
Мы рассмотрим здесь несколько теорем, которые гаран-
гарантируют существование определенных выборов при соответ-
соответствующих предположениях. Они интересны сами по себе
и могут быть использованы в качестве теорем существова-
существования в р аз личных комбинаторных задачах.
Теорема о различных представителях. Если
для каждого индекса I в системе индексов I имеется ко-
конечное подмножество 81 множества 8, то различные
представители множеств, именно элементы а^ такие,
что а1^81 для всех I и аьфа^ если 1ф], найдутся
тогда и только тогда, когда удовлетворяется следующее
условие.
Условие С. Среди элементов любого конечного числа
к множеств 5,- имеется по меньшей мере к различных.
Заметим, что в этой теореме подмножества 5, и 5у- при
] могут в действительности содержать в точности одни
и те же элементы и отличаться, таким образом, только
своими индексами. Если общее число п множеств конечно,
а сами множества бесконечны, то теорема остается в силе,
так как можно, очевидно, отбросить все, кроме п, элементы
в каждом 5,-, не нарушая условия С. Эта теорема впер-
впервые была выведена Ф. Холлом [12] и обобщена разными
авторами [11, 3, 7].
Аналогичная теорема относительно матриц была дока-
доказана Кёнигом [5]. Мы будем употреблять термин „линия"
матрицы, понимая под ним как строку так и столбцы.
Теорема о матрицах. Если элементы прямоуголь-
прямоугольной матрицы — нули и единицы, то минимальное число
линий, которые содержат все единицы, равно макси-
максимальному числу единиц, которые могут быть выбраны
таким образом, чтобы среди них не нашлось двух рас-
расположенных на одной и той же линии.
Конечный случай теоремы Ф. Холла эквивалентен тео-
теореме Кёнига; каждая из этих теорем может легко быть

/. Основные теоремы 39
выведена из другой. Следующая теорема гарантирует, что
мы можем осуществить ту или иную из двух выборок
в случае, когда ясно, что ни одна из них в отдельности
не может быть гарантирована.
Теорема Рамсе я. Пусть 8 — множество, содержа-
содержащее N элементов; предположим, что семейство Т всех
подмножеств 8, содержащих в точности г элементов,
разделено на два семейства а и р, взаимно исключающих
друг друга. Пусть р^г, ц^-г, г ^ 1. Тогда, если
я(Р> <7> г)^Ы есть число, зависящее только от целых
чисел р, ц, г и не зависящее от множества 8, то либо
существует подмножество А из р элементов, в котором
все г-подмножества принадлежат семейству а, либо суще-
существует подмножество В из ц элементов, в котором все
г-под множества входят в семейство р.
Мы начнем с построения алгоритма для теоремы о различ-
различных представителях в случае конечного числа множеств.
Практически в конкретном случае нелегко установить, вы-
выполняется условие С или нет. Очевидно, что условие С есть
необходимое условие, потому что если различные предста-
представители существуют, то для любых к множеств представи-
представителями будут к различных элементов, содержащихся в этих
множествах. С помощью нашего алгоритма мы, не произ-
производя никаких предварительных испытаний, либо найдем
множество различных представителей, либо получим к
множеств, которые содержат меньше чем к элементов, что
нарушает условие С и доказывает, что не существует
множества различных представителей.
Допустим, что множества 5,, 52, ... , 8п записаны по
порядку. Выберем произвольный элемент а1 из 51 и до тех
пор, пока это возможно, будем выбирать произвольные аг
из 5,-, отличные от ранее выбранных элементов а. Если
этот процесс удастся довести до 5П, то мы получим сово-
совокупность различных представителей. Мы можем, однако,
Достичь множества 5Г, все элементы которого Ьх, Ь2, ... , Ъх
были использованы как представители некоторых
5Х, ... , 5г-1. Тогда мы построим несколько вспомога-
вспомогательных множеств То, Т13 ••• . Множество То.состоит из
элементов Ьх, Ъг, ... , Ьг, которые мы считаем упорядо-
упорядоченными. Множество 7\ состоит из элементов множества,
представителем которого является Ьх, за исключением

40 Гл. III. Теоремы выбора
самого Ьх и всех остальных использованных элементов.
Тх может быть пустым, но если оно непусто, то его эле-
элементы, обозначенные как Ьг+1, ... , Ъ8, непосредственно:
следуют за Ь19 ... , Ьг. Далее, если /-й элемент Ь1 есть
представитель множества Зр мы построим множество Ть
состоящее из тех элементов 8р которые еще не использо-
использованы, и запишем эти элементы после элементов, уже
использованных. Мы продолжаем так поступать до тех
пор, пока не случится одно из двух: 1) мы достигнем
некоторого Ь1У который не является представителем, или
2) последовательность исчерпывается элементами Ь19 ... , Ь3
как представителями множества. В случае 1 Ь1 = Ъ^ {11^> г)
входит в множество 8^, представителем которого является
6/а, причем 12<С.К' Если /а^>^, то Ъ1% входит в множество
5^, представителем которого является2 Ь1я, причем /,</,,
и т. д. Таким образом, мы получаем последовательность
Ь1г Ь1я, ... , Ь1т с убывающими индексами Aт ^ I), такую»
что каждый ее член является элементом множества, пред-
представителем которого является следующий элемент. Но
теперь мы можем заменить представителей, беря Ъ^ в ка-
качестве представителя 5^, Ь1% — в качестве представителя
5уа, ... , Ь1т__1-—в качестве представителя 5ут_1? осво-
освобождая Ъ1т от выбора в качестве представителя 5Г. В ре-
результате этого процесса 5Х, ... , 5Г_Х так же, как и 5Г,
имеют различных представителей, и мы можем тем же
путем найти представителя 5г+1. Таким образом, если
случай 2 никогда не наступает, мы можем найти различ-
различных представителей для всех множеств 5Х, 52, ... , 5И.
Когда имеет место случай 2 и последовательность Ъх, ..., Ь3
исчерпывает элементы, могущие выступить в качестве пред-
представителей, то эти элементы являются представителями 5
множеств и по построению каждый элемент этих 5 мно-
множеств содержится в последовательности. Но тогда эти 5 мно-
множеств, а также множество 5Г образуют 5-(-1 множеств,
которые содержат только 5 различных элементов; таким
образом, мы находим множества, нарушающие условие С.
Исходя из этого доказательства теоремы Ф. Холла для ко-
конечного числа множеств, можно различными путями полу-
получить доказательство для случая, когда число множеств беско-
бесконечно, Способ доказательства, которого мы здесь придер-

1. Основные теоремы 41
живаемся, имеет то преимущество, что дает дополнитель-
дополнительные сведения для конечного случая. Назовем конечное
число г множеств 5^, ... , 5^ блоком Вг 8, где 5 — число
различных элементов в г множествах. Тогда, согласно
условию С, для каждого блока Вг8 имеем 8^г. Более
того, в доказательстве для конечного случая показано,
что если условие С удовлетворено, можно найти различных
представителей для любого конечного числа множеств,
т. е. для множеств любого блока. Назовем вычеркиванием
О вычеркивание некоторых элементов из некоторых мно-
множеств 5г-. Вычеркивания могут быть частично упорядочены
естественным способом: будем говорить, что Д^О2, если
каждый элемент, вычеркнутый из множества посредством
Д, оказывается также вычеркнутым посредством Д. Со-
Сосредоточим внимание на вычеркиваниях, при которых сохра-
сохраняется условие С. Тогда, если Д ^ Д е . .. —возрастаю-
—возрастающая цепочка вычеркиваний, сохраняющих условие С, то
верхний предел этой цепочки есть тоже вычеркивание Д
сохраняющее условие С, так как для всякого блока Вг 8
имеется только конечное число вычеркиваний Д и, следо-
следовательно, существует последнее вычеркивание, так что ^
сохраняет условие С для каждого блока и, следовательно,
для всех блоков. В силу леммы Цорна, должно существо-
существовать максимальное вычеркивание Д сохраняющее условие С.
Покажем, что вычеркиванием ^ каждое множество 5/
будет сведено к единственному элементу а1 (где а1 — раз-
различные представители множеств). Блок Вг 5, в котором
5 = /*, назовем критическим блоком Вгг. Если Вг г^Вги,
то элементы Вг г не могут быть использованы как пред-
представители множеств блока Вх ц, не входящих в Вг г. Сле-
Следовательно, допустимое вычеркивание состоит в удалении
элементов критического блока из множеств, не входящих
в этот блок, и мы можем предположить, что это проделано
посредством О. Затем в критическом блоке Вг г выберем
различных представителей, сводящих каждое множество
к единственному элементу. Можно также предположить,
что это проделано посредством В. Наконец, если множество
5/ не принадлежит ни к какому критическому блоку и
если а[ есть элемент множества 5,, построим вычеркивание,
которое сводит 5,- к единственному элементу аь и вычер-
вычеркивает а1 из всякого другого множества. Теперь а1 не

42 Гл. III. Теоремы выбора \
принадлежит ни к какому критическому блоку, так как]
в противном случае он был бы исключен из 5/в Таким!
образом, для блока Вг 8, содержащего а19 но не содержа-]
щего 5,-, первоначально имеем 8^г-\-1; после вычер-
вычеркивания он становится блоком Вг%8_г, где 5—1^
Если ВГ8 содержит 5,., то г—1 других множеств должны|
содержать до вычеркивания по меньшей мере г—1|
элементов, отличных от аг\ следовательно, после вычерки*
вания Вг 8 содержит по меньшей мере г элементов. Такш^
образом, условие С сохраняется. Мы видим, что в случае!
максимального вычеркивания Б каждое множество 5,- сво-|
дится к единственному элементу а1 и, таким образом,)
элементы а, являются различными представителями. |
Последнее рассуждение можно сделать более изящным*
применив следующую теорему. >\
Теорема. Если условие С соблюдается, то сущест\
вует некоторое множество 5,., такое, что всякий элемент^,
5,- может быть выбран в качестве его представителя &
системе различных представителей.
Следствие. Если наименьшее множество имеет Ц
элементов, то существует по меньшей мере 1A — 1) ...
(г — п-\-\) различных представителей, если г^п, и пД
меньшей мере Л различных представителей, если г<^п.
Если имеются критические блоки, то и среди них есть
минимальный критический блок Вг г. Всякая система раз-?
личных представителей для Вг г может быть распространена!
на представителей всех множеств. Что касается множеств^
5/ из Вг г, то его представителем может быть любой эле1
мент, так как внутри Вг г блоки не являются критическими
и, следовательно, применимо рассуждение, проведенной
выше. Если же критических блоков не существует, тй|
применимость этого рассуждения очевидна. 1
Рассмотрим теперь теорему Кёнига о матрицах. Пуст!|
А — п X ^-матрица, составленная из нулей и единиц. Пред
положим, что т — минимальное число линий, содержащи
все единицы, а М — максимальное число единиц, никаки
две из которых не расположены на одной линии. Тогд
очевидно, что т^М, так как ни одна линия не може
пройти через две из М единиц. Мы можем, использова^
теорему Ф. Холла, доказать неравенство М ^ т. ПусЩ
— г-\-з, где г — число строк, а 5 — число столбцов!

1. Основные теоремы 43
расположим эти г строк так, чтобы они были первыми, и
назовем их ^^ ... , Яг Для каждой из строк /?, соот-
соответственно образуем множества 5г, ... , 5Г, где 5,- состоит
из номеров / столбцов, для которых аи=\, исклю-
исключая номера 5 столбцов, входящих в указанное выше мини-
минимальное число. Теперь, если к из этих множеств содержат
меньше, чем к элементов (скажем, V элементов), то соответ-
соответствующие V<^к столбцов могут быть использованы, чтобы
заменить к строк, и в таком случае все единицы будут вклю-
включены в меньшее число линий. Поскольку это противоречит
предположению минимальности /л, то условие С удовлетво-
удовлетворяется для множеств 5Х, ... , 5Г и мы можем выбрать г еди-
единиц из г строк так, чтобы не было двух единиц в одном и
том же столбце и ни одной в 5 столбцах. Теми же самыми
рассуждениями мы можем выбрать 5 единиц из 5 столбцов,
чтобы не было двух единиц в одной и той же строке и
ни одной в г строках. Это дает нам всего г-{-8 — т
единиц, расположенных не более чем по одной на одной
и той же линии. Отсюда М^т, а поскольку мы ранее
установили, что т^М, то отсюда следует, что М = т,
а это доказывает теорему.
В свою очередь, исходя из теоремы Кёнига, нетрудно
доказать теорему Ф. Холла. Пусть даны множества 5Х,
52, ... , 5„ и элементы а19 ... , ат. Образуем матрицу
Аа^, где аи-~1, если Яу входит в 5,, иа/у-=0, если
А б
нет. Теперь, если единицы матрицы А могут быть разме-
размещены в г строках и 5 столбцах, причем г-{-$<^п, то для
к = п — г строк, не совпадающих с г выбранными строками,
единицы имеются только в $<^п— г = к столбцах и ус-
условие С для этих к множеств нарушается. Но если мини-
минимальное число линий будет г-|-5 = я, то, согласно теореме
Кёнига, существуют п единиц, таких, что никакие две из
них не лежат на одной линии, а соответствующие п эле-
элементов образуют множество различных представителей п
множеств.
Теорема Рамсея в случае г = 2 может быть применена
к теории графов следующим образом. Пусть даны N точек.
Каждая пара точек (г = 2) соединена дугой, а каждая
Дуга окрашена в один из двух цветов (-а или E). Тогда,
если N достаточно велико, существует или множество р
точек, все дуги которого окрашены в цвет а, или множе-

44 Гл. III. Теоремы выбора
ство <7 точек, все дуги которого окрашены в цвет р. Задача
в этой постановке была исследована Глисоном и Гринву-
дом [2]; им даже удалось получить результат, являющийся
доказательством теоремы Рамсея для любого числа цветов.
Мы, следуя Эрдёшу и Секерешу [13], докажем теорему
Рамсея полной индукцией относительно г, р и <у, допус-
допустив, что результат справедлив для г—1 и для любых
значений р, д, затем — для г, р, <у—1 и, наконец,—для
г, р — 1, д. Для г= 1 значение N равно р-\-ц— 1. Это сле-
следует из того, что мы можем построить множество, содержа-
содержащее р — 1 элементов а и ц — 1 элементов р, откуда N ^> Р +
4~д — 2. Но если для N ^ р-\- д — 1 не найдется р эле-
элементов а, то их не более чем р — 1 и, следовательно, су-
существует по крайней мере N — (р—1)^<7 элементов р.
Если при р = г существуют г-множества, то любое из них
будет удовлетворять условиям выбора. Если пфг, то
каждое г-множество есть г-множество элементов р, и, сле-
следовательно, при И^д будет существовать ^-множество,
в котором все г-множества состоят из элементов р. Ана-
Аналогично, если 9 = г, достаточно иметь Ы^р. Таким об-
образом, в качестве исходных значений для нашей индукции
мы имеем
п(р, ?, 1) = р + <7— 1, п(г, ?, г) = <7, п(р, г, г) = р.
Помимо этих начальных значений, условия р ^ г,
<7^г, г^з1 также удовлетворяются для р', <?', г\
где г' = г—1, или при р' = р—1, д' = <7, г'=г, или
при р' — р, Я' = Я—1, г' = г.
В соответствии с нашей индукцией выберем
р1 = п(р—1, д, г), ^71 = лг(р, ц—1, г). Затем предполо-
предположим, что п(р, ц, г)^п(р1У цх, г—1) —|— 1. Чтобы доказать
это, предположим, что Л/^п(р1, цх, г—1)+1. Выбереь!
фиксированный элемент а0 из 5 и определим а' и Р' мно*
жества из (г—1)-множества 5'= 5 — а0 по следующему
правилу. Если а0 и (г—1)-множество из 5' = 5 — а0 об-
образуют а-множество из 5, то мы назовем это множество
а'-множеством из 5', если же а0 и (г— 1)-множество из 5
образуют р-множество из 5, мы назовем его Р'-множествоЦ
из 5'. Так как 5 имеет по меньшей мере п(р1, <7Г г—1|
элементов, то 5' содержит или ргмножество, в которой
все (г— 1)-множества суть ос-множества, или ^-множество!

2. Приложения теорем 45
б котором все (д—1)-множества суть р-множества. Пред-
Предположим первое. Пусть 7\— /^-множество, в котором все
р — 1-множества будут а'-множествами. Так как
A, д, г), то 7\ будет или содержать д-мно-
р1
жество <3, в котором все г-множества суть р-множества,
и в этом случае <3 удовлетворяет нашим требованиям.
Если же нет, то 7\ содержит (р— 1)-множество Р', в ко-
котором все г-множества суть а-множества. Но в таком
случае Р' и а0 образуют р-множество Р, в котором г-мно-
жества те же, что и в Р', или состоят из а0 и (р—^-мно-
(р—^-множества из Р\ Но все (р—1)-множества из V суть
а'-множества, откуда одно из них, взятое с элементом а0,
есть а-множество из 5. Следовательно, все г-множества
из Р суть а-множества, так что Р удовлетворяет нашим
условиям. Рассуждение будет аналогичным, если сущест-
существует ^-множество Т2, в котором все (д—1)-множества
суть множества р.
В рекуррентном правиле
К(Р, Я> 0<л(р1, щ» г—1L-1,
где
г), Я1 = п{р, 9—1, г),
равенство сохраняется не всюду. В самом деле, Глисон
и Гринвуд [2] доказали, что
Я,
где
2), цх = п{р, <7—1, 2)
Для четных рг и цх. Из этого следует, что п C, 4, 2) <
< 4 4-6= 10, и в самом деле Гринвуд и Глисон доказа-
доказали, что лC, 4, 2) = 9.
2. Приложения теорем
Приложения этих теорем довольно многочисленны.
Примером приложения теоремы Рамсея может служить
следующая теорема, которую доказали Эрдёш и Секереш [ 13].
Теорема. Для любого заданного целого числа п су-
существует целое N==NA1), такое, что среди N точек
плоскости, расположенных так, что никакие три из них
Не лежат на одной прямой, найдутся п точек, образую-
шМх выпуклый п-угольник.

46 Гл. ///. Теоремы выбора \
-»1 .. %...... у ~т°*^&_
Доказательство состоит из двух частей. •
Лемма 1. Из 5 точек на плоскости, расположенных
так, что никакие три из них не лежат на одной прщ
мой, 4 точки оказываются вершинами выпуклого четы]
рехугольника.
Доказательство. Если выпуклая оболочка 5 точек
образует выпуклый четырехугольник или пятиугольник,
то это очевидно. Если же выпуклой фигурой является
треугольник Д В, С, а другие две точки, Ь и Е, распо-
расположены внутри треугольника, тогда две из трех точек
Л, В, С расположены по одну сторону от прямой ИЕ^
скажем В и С, и в этом случае точки В, С, Д Е обра-
образуют выпуклый четырехугольник. !
Лемма 2. Если каждые четыре точки из п данныЩ
точек образуют выпуклый четырехугольник, то эти щ
точек являются вершинами выпуклого п-угольника. \
Доказательство. Для я = 4 это очевидно. Перей-1
дем по индукции к случаю п точек. Предположим, чтс|
все четырехугольники, образованные из точек А19 А2, -
Ап> Ап+1, являются выпуклыми. Тогда А19 А2, •••, ^
будут, по предположению, вершинами выпуклого /г-уголЦ
ника Сп, и мы можем считать, что они именно в такой
порядке расположены вдоль периметра. Если точка Ап+^
находится внутри Сп, то она должна попасть внутрь одного
из треугольников АхА^Аг, АхАгА#* • -,Л, Ап_г Ап. Но тогд
для некоторого / мы имеем точки Ах А(А1+1Ап+1, которы
не образуют выпуклого четырехугольника, что противоре
чит предположению. Это доказывает более общее предполо
жение, что в случае п -\- 1 точек выпуклый многоугольник^
образованный п из них, не содержит оставшуюся точк)|
внутри себя. Теперь, если мы соединим точку Ап+1 сс|
всеми точками Аг, А2,- • •, Ап прямыми, то поскольку Ап+
лежит вне выпуклого многоугольника, то среди этих пря
мых будут две крайние, скажем Ап+1А1 и Ап+1А;-, образую-
образующие угол, охватывающий выпуклый /г-угольник. Если допус
тить, что Аг и А;- не являются последовательными вершинами
то Ап+1 и другие точки должны образовать выпуклый
многоугольник, содержащий остальные точки внутри себя|
Так как этого не может случиться, то Ас и Лу следуют одни)
за другой и, помещая Ап+1 между ними, мы получаеМ
выпуклый (п-\- 1)-угольник. Это доказывает вторую лемму]

2. Приложения теорем А1
Доказательство теоремы теперь следует непосредственно
из теоремы Рамсея и двух лемм. Пусть 4-множества делятся
на выпуклые и невыпуклые четырехугольники. Поскольку
нет 5-множества, содержащего только невыпуклые четырех-
четырехугольники, то если N достаточно велико, будет существо-
существовать /г-множество, все четырехугольники которого выпуклые.
Из теоремы о различных представителях мы получаем
следующую теорему:
Теорема об одновременных представите-
представителях. Пусть множество 8 разделено на п непересекающихся
подмножеств двумя способами: 8 = А1-\- •• • ~{-Ап — В1-\-
-}-••• +ВИ. Тогда, если нет к подмножеств Л, которые
бы содержались в меньшем, чем к, числе подмножеств В,
то существуют элементы х19 • • •, хп, которые являются
одновременно представителями множеств А и мно-
множеств В.
Доказательство. Для каждого подмножества Л,-
определим множество 5,-, состоящее из элементов с такими
индексами /, что А1 О В; не пусто. Условие теоремы явля-
является условием С для множеств 5,. Но выбор различных
представителей для 5,- дает для каждого А{ свое особое
В], с которым оно имеет непустое пересечение. Выбирая в
этом пересечении по одному элементу в каждом случае,
мы получаем элементы хх, х2, •••,*„ различных множеств
Л, а также различных множеств В, как и требовалось.
Необходимость условия очевидна, и, рассматривая допол-
дополнения, мы видим, что условие симметрично как для мно-
множеств Л, так и для множеств В. Естественным следствием
этой теоремы является
Теорема. Если Я — подгруппа конечной группы С,
ш мы можем выбрать элементы, которые являются
одновременно представителями правого и левого множеств,
дополнительных к Я.
Здесь каждое из левых дополнительных множеств А{
и каждое из правых дополнительных множеств Ву содер-
содержат то же число элементов, что и Я, и теорема доказана.
Эта теорема также справедлива, если О бесконечна, а Я
имеет конечный индекс. Известно, что в О существует
нормальная подгруппа К с конечным индексом, которая
с°Держится в Я. Отсюда следует справедливость теоремы,
Так как каждое правое или левое дополнительное к Я

48 Гл. III. Теоремы выбора
множество содержит то же самое число дополнительных
множеств /С, что и Я. !
В качестве дальнейшего приложения теоремы о различ-
различных представителях мы имеем следующую теорему:
Теорема. В векторном пространстве конечного или
бесконечного числа измерений всякие два базиса имеют
одинаковые кардинальные числа.
Пусть X/, /6 Л а также уу., /6Л—два базиса вектор-
векторного пространства V над полем р. Представляя каждый
вектор X/ как линейную комбинацию векторов у, мы полу-
получаем множество 5; векторов у, ассоциированных с векторами
X,-, именно тех векторов у у, которые входят с ненулевыми
коэффициентами в выражение для х,- через векторы уу.«
Множества 5,- конечны и должны удовлетворять условию
С, так как в противном случае векторы х были бы линейно
зависимы. Следовательно, мы можем выбрать различные
элементы у из множеств 5,- и кардинальное число элемен-
элементов у будет во всяком случае не более числа элементов х.
Аналогично кардинальное число элементов х будет не более
кардинального числа элементов у, следовательно, оба кардин
нальных числа должны быть равны.
В качестве приложения теоремы Кёнига мы рассмотрим
задачу о распределении должностей. Предположим, что
имеется п должностей, занимаемых п людьми, и что
оклады а^ A= 1, . . ., п\ у' = 1, .. ., п) для /-го человека
в у'-й должности. Предполагается, что оклады — неотрица-
неотрицательные целые числа. Требуется найти оптимальное рас-
распределение п должностей между п лицами, т. е. такое
распределение, при котором сумма соответствующих окла-
окладов будет максимальной. Существует, очевидно, п\ вариан-
вариантов, из которых нужно выбрать оптимальный. Задача
состоит в том, чтобы найти систематический метод отыска-
отыскания и исследования решения с помощью сравнительно
малого числа попыток. Докажем теорему.
Теорема. Дана матрица А — (а,-•). Максимум суммы
п п
ау\ 4~ а2;2 ~Ь • • • 4~ ап/п равен минимуму У] щ -\- 2 уу для
1=1 /=1
всех чисел ^.(/=1, ..., п), V^(^=^^ 2, ..., /г), таких,
что и^-\-V^^а^^ во всех случаях. Общее значение дости-
достигается, когда и,- + гь. =а//. и эти значения являются
1 ' УI *У;)
решением задачи о распределении должностей.

2. Приложения теорем
49
Доказательство. Если задана матрица (а/у), мы
всегда можем найти числа и19 V^, удовлетворяющие нера-
неравенству и1-\-Ю]^а,1р беря все числа и равными 0 и каж-
каждое V] равным максимуму а/у(/=1, 2, ..., п). Поскольку
"/ + Х}1 ^ а<л> то> суммируя, получаем У щ + 2 ХI > 2 а<Ур
следовательно, если т есть минимум 2а*~1~2у/> а ^ —
максимум 2#/л> тогда т^М, Мы должны доказать, что
т = М. Для выбора элементов и и V образуем вспомога-
вспомогательную матрицу 5 = F;7), полагая Ьи-=\, если
щ —|— Ыу=а/у-, и &/у-=0, если &,- -|- Уу > а/у-. Тогда, если
имеется п элементов Ь и среди них нет двух, лежащих
на одной линии, то они дают нам положения п элементов
а, т. е. а//4, таких, что2"/ + 2с;У=:::2а|'Л» откуда т=М,
и, следовательно, попутно решена задача о распределении
должностей. В случае, когда элементы а—целые неотрица-
неотрицательные, при первоначальном выборе элементы и я V были
целыми. Если мы не получаем решения сразу и оказы-
оказывается, что элементов Ь меньше, чем п, а среди них нет
двух, лежащих на одной линии, то, по теореме Кёнига,
существует I<^п линий, которые включают в себя все
единицы. Предположим, что среди этих линий г строк
и § столбцов. Тогда мы и и V заменим через и* и у',
полагая
и{ — -пг
V^=V^ — у
для г строк,
для остальных строк,
ДЛЯ 5 СТОлбцОВ,
Для остальных столбцов.
Здесь,
если
то
1
или
1
=1, а в сумме
или и
если
время
1
у , или щ==и
одновременно, откуда и^-{-V^==и^-\-V^9
и мы все еще имеем и^-\-V^
а^^.
Но,
2 0
а{7, то и^-\-V^^и^-\-V^—\>а^^. В тоже
2 о/ + |
4 М. Холл

50 Гл. III. Теоремы выбора
Следовательно, сумма^ и{ -\~ 2 ^у уменьшилась на целоз
число. Мы продолжаем таким образом изменять элементу
и и V на 1/2 до тех пор, пока далее уменьшать 2"/~Ь2°)
станет невозможно. Когда же это произойдет, то, приме*
нив теорему Кёнига, мы получим решение задачи о рас*
пределении должностей. Теорема, однако, справедлив^
и без ограничения, что а^ должны быть целыми неотри-
неотрицательными числами. В самом деле, если а,у-— произволь-
произвольные числа, мы можем всюду добавить постоянную, чтобц
заменить числа а неотрицательными числами. Более того;
результат не изменится, если мы умножим каждое а^
на положительную константу. Отсюда, так как теорема!
справедлива, когда аи — целые, то она будет также верна;
и для случая, когда а^ являются рациональными. Если!
мы с помощью сложения и умножения нормируем числа а,
так чтобы 0^а,7^1, где аи — рациональные числа со
знаменателем N. то после умножения на N числа а будут
находиться в интервале 0^а,у<;Л^ и будем иметь
0^^^и^-{-Уу^V^^:пN. Так как сумма уменьшается на
целое число на каждом этапе, то существует самое боль
шее пЫ этапов, на каждом из которых и и V изменяются*
не более чем на 1/2. Отсюда получаем
пЫ ^ ^ , пМ пЫ ^ ^ ЗпЫ
Теперь, деля на Ы9 чтобы вернуться к рациональному ре-
решению, получаем для рациональных решений
п ^ . , п п
<«< + у и _т
Из компактности области значений и и V следует, что
если мы аппроксимируем иррациональные числа аи рацио-
рациональными, то в пределе найдется такой набор элементов
и и V, который даст равенство для теоремы и оптимальное
распределение должностей.
Заметим, что в задаче о распределении должностей'
определение вспомогательных переменных а и V имеет
большое значение не только для нахождения решения, ней
и для исследования его. Дело в том, что если нам задано
некоторое распределение должностей, то соответствующая

2. Приложения теорем 51
сумма окладов легко вычисляется, но без знания и и V
невозможно исследовать само распределение, чтобы решить,
будет оно оптимальным или нет.
Существует тесная связь между комбинаторным анали-
анализом и теорией линейных неравенств и, более общо, с тео-
теорией выпуклых пространств; эта связь еще не изучена
полностью. Рассмотрим так называемые двойные стохасти-
стохастические матрицы. Двойная стохастическая матрица X
это квадратная матрица из действительных, неотрицатель-
неотрицательных чисел, суммы которых по строкам и по столбцам
равны единице. Формально
, ..., л,
1, Ь —~-~ 1 , • • • , II/.
Термин „двойная стохастическая матрица" возник
в теории вероятностей. Подобную матрицу можно рассма-
рассматривать как матрицу, дающую вероятность перехода для
случая, когда имеется п различных состояний; Хц — ве-
вероятность того, что за /-м состоянием последует у-е состоя-
состояние. В я2-мерном пространстве всех действительных
п X гс-матриц двойная стохастическая матрица образует
выпуклое и ограниченное подпространство размерности
(п— IJ, а переменные х{р /, /= 1, ..., п— 1, определяют
все остальное пространство. Здесь мы ассоциируем Х = (хц)
с точкой (г19 ...,2„2), где хи=гии'_1)п. Мы называем
пространство 5 выпуклым, если вместе с точками Рг, ..., Рг
и аг-\- ... -\-аг= 1 оно содержит точки вида а1Р1-\-
+ Р2-[-...+агРг, где а^О (/=1, ..., г) й
-. --\-пг=\. В частности, когда а1 ^0, а2^О
и а1-[-я1=1, сг1Р1-\-а2Р2 с переменными а дает отрезок,
соединяющий Рг и Рг. Точка Р выпуклого пространства
называется экстремальной, если она не может быть выра-
выражена в вышеуказанной форме как линейная комбинация
любых точек пространства. Легко видеть, что в простран-
пространстве двойных стохастических матриц матрицы перестано-
вок, которые имеют по единственной единице в каждой
строке и в каждом столбце, образуют экстремальные точки.

52 Гл. III. Теоремы выбора
Теорема. Всякая (п X п)-матрица из неотрица-
неотрицательных чисел, все строки и столбцы которой имеют
одну и ту же сумму, может быть записана как сумма
матриц перестановок с положительными коэффициен-
коэффициентами.
Доказательство. Пусть М = (т -у) (/, / = 1, .. •, п)—
матрица, в которой сумма элементов каждой строки и
каждого столбца равна I. Допустим, далее, что число
ненулевых элементов тц равно т. Если М не есть тожде-
тождественный нуль, то хю^п, а если ш = п, то М есть/-крат-
есть/-кратная матрица перестановок. Пусть 51-(/=1, 2, ..., п) —
множества тех у, для которых ти-^=0. Мы утверждаем,
что условие С справедливо для 5-. В самом деле, если
условие С не удовлетворяется, то все ненулевые элементы
к строк окажутся расположенными менее чем в к столб-
столбцах. Отсюда, суммируя эти элементы по строкам, полу-
получим Ы, а суммируя по столбцам, получим самое большее
(к — 1) г, что противоречит условию теоремы. Следовательно,
условие С выполняется и множества 5{- имеют различные
представители /1? ..., /п, которые образуют перестановку
1, ..., п. Тогда Р = (ру) — матрица перестановок, если
р/;..= 1, а все остальные ри=0. Более того, если
выбрать в качестве и наименьшее из пцд, тоМ — иР будет
состоять из неотрицательных элементов, суммы которых по
строкам и столбцам равны I — и, а ненулевых членов
будет меньше, чем в М. По индукции, М — иР — и2Р2-\-
+ ... -|- игРг и М = иР-{- и2Р2 -)-...+ игРг, что и требо-
требовалось доказать.
Отсюда непосредственно следует, что всякая двойная
стохастическая матрица может быть выражена через ма-
матрицы перестановок и что только эти последние являются
единственными экстремальными матрицами. Так как линей-
линейная функция, заданная на отрезке, достигает максимума
(или минимума) на концах этого отрезка, то отсюда сле-
следует, что всякая линейная функция, которая достигает
максимума (или минимума) в выпуклом пространстве,
будет достигать его в экстремальной точке.
Таким образом, мы установили важную связь между
выпуклым пространством двойных стохастических матриц
и дискретным пространством матриц перестановок, которые
являются экстремальными точками. Так, если А (

2. Приложения теорем 53
оклады в задаче о распределении должностей, мы можем,
если желаем, рассматривать эту задачу как задачу отыска-
отыскания максимума линейной формы 2а1/*17» так как
представляет все пространство двойных стохастических
матриц. Мы знаем, что этот максимум будет достигаться,
когда X—матрица перестановок. Обратно, континуальная
задача отыскания максимума линейной формы на простран-
пространстве двойных стохастических матриц может быть сведена
к комбинаторной задаче отыскания максимизирующей
матрицы перестановок.
Метод решения задачи о распределении должностей
с употреблением вспомогательных чисел и{ и V^ есть част-
частный случай общей теоремы двойственности из теории
линейного программирования. Приложение этого общего
метода к комбинаторным задачам было недавно осущест-
осуществлено А. Гофманом и Г. Куном. Мы приводим основные
задачи и теоремы в формулировке М. Флуда [8].
Во-первых, обозначим буквой М прямоугольную (т X п)-
матрицу. Буквы а, Ь, х, у обозначают векторы-столбцы.
М, а, Ь — заданы, х, у, а также число д, — искомые. Мы
будем употреблять верхний индекс Т, чтобы обозначить
транспозицию вектора или матрицы. Векторное неравенство
означает, что это неравенство справедливо для каждой
из соответствующих компонент.
Задача I. Удовлетворить ограничениям Мх ^ а, х ^ О
и выполнить Ътх = й для й максимального в том смысле,
что не существует х, удовлетворяющего ограничениям и
приводящего к неравенству Ьгх > й.
Задача II. Удовлетворить ограничениям Мту ^ Ь,
У^О и выполнить ату = й для д, минимального в том
смысле, что не существует у, удовлетворяющего ограниче-
ограничениям и приводящего к неравенству агу < й.
Задачи I и II называются двойственными.
Основная теорема выполнимости. Ограниче-
Ограничения в задаче выполнимы (т. е. удовлетворяются некото-
некоторыми значениями х или у) тогда и только тогда, когда
двойственная задача в однородной форме (т. е. при
Ь = 0 или а = 0) имеет нулевое решение.
Основная теорема существования. 1) Векто-
Векторы х и у являются решениями задач I и II тогда и

54
Гл. III. Теоремы выбора
только тогда, когда они удовлетворяют поставленным,
в этих двух задачах ограничениям и осуществляют),
агу —Ьгх. Такие х и у существуют, если ограниче-
ограничения в обеих задачах выполнимы. 2) Задача имеет реше-
решение тогда и только тогда, когда ее ограничения выпол-
выполнимы и однородная форма задачи имеет нулевое решение.
Основная теорема двойственности. Задача
имеет решение (для единственного д) тогда и только
тогда, когда двойственная ей задача имеет решение
(для того же самого д).
Доказательства этих теорем даны Гейлом, Куном и
Таккером [1].
В случае задачи о распределении должностей вместо
переменных х^- возьмем п2 переменных с одним индексом.
Положим Х;м1„_,м = Х;,; 1=1, ..., я, /=1, ..., я; ана-
аналогично введем обозначения для окладов
Затем возьмем (я2 Х4я)-матрицу М:
М
2>
— ^
/.
/,
п
п
п
п
а
1п
1
1п
где 1п — единичная (п X я)-матрица и 1 { — (я X я)-
матрица с единицами в 1-я строке и нулями в остальных,
а 1п — вектор-столбец из ~п единиц. Неравенство Мх ^ а
выражает через первоначальные х1}- тот факт, что суммы
элементов строк (и аналогично столбцов) будут самое боль-
большее равны -|-1, а суммы их отрицательных значений —
самое большее —1, откуда вытекает, что суммы элемен-
элементов в строках и столбцах равны единице. Следовательно,
неравенство Мх^а (х^О) показывает, что мы имеем дело
с двойными стохастическими матрицами. В частности, при
Ьг=(&х, ..., Ьп) мы получаем
Ьгх =
п
Максимум последней суммы дает решение задачи о рас-
распределении должностей.
В двойственной задаче мы стремимся удовлетворить
условиям Мту^Ъ, у^О и добиться, чтобы агу было ми-
минимальным. Здесь у является 4я-компонентным вектором.

2. Приложения теорем 55
Если мы положим и — у; — уп+1 для *"=1, ..., п и
^/=#2*+/ — Узи+у для /=1, ..., /г, то условие МГу^Ь
принимает вид и[-\-х)^а{^ Положительность у не накла-
накладывает никакого условия на значения и и V. Таким обра-
образом, двойственная задача дает вспомогательные числа и
и у, а из основной теоремы двойственности следует, что
минимум суммы 2^Н~2у./> который равен агу, является
максимумом 2а«7^«7- Этот максимум дает решение задачи
о распределении должностей, так как мы показали, что
перестановки суть экстремальные точки двойных стохасти-
стохастических матриц. Практически значение теоремы двойствен-
двойственности состоит не в том, что решение одной задачи дости-
достигается посредством решения другой однотипной, но в уста-
установлении того, что одно и то же & входит в решения обеих
задач и что на практике лучше всего решать их одновре-
одновременно. Существенно, наконец, что, получив решение, мы
можем исследовать его.
Манн и Райзер [7] обобщили задачу отыскания системы
различных представителей. Они поставили вопрос: когда
заданное множество элементов е19 ..., ер которые они
назвали маргинальными, может встретиться в некоторой
системе различных представителей. При этом они доказали,
что если каждый из элементов е19 ..., ех встречается по
меньшей мере г раз в множествах 5,-, тогда существует
некоторая система различных представителей, содержащая
е19 ..., ех. Это условие, однако, слишком сильное. Гоф-
Гофман и Кун [3] нашли более подходящее условие и доказали
его с помощью теоремы двойственности. Естественно, что
условие С должно быть соблюдено. Так что условием для
маргинальных элементов будет следующее.
Условие С*. Для всякого р = 1, . .., X и для всякого
выбора /Г=е1-1, ..., е{ р маргинальных элементов число
множеств 5у«, в которых встречаются Е\ будет по мень-
меньшей мере р.
Здесь будет дана только схема доказательства.
Пусть С = (су), (/=1, ..., /и, /==1, ..., п) — ма-
матрица инцидентности, где Сц=1, если /-й объект нахо-
находится в /-м множестве, и с[;-=0 во всех других случаях.
Естественно, что т^п. Итак, *'=1, 2, ..., I будет соот-
соответствовать данным I маргинальным элементам е19 ..., ег.
Теперь определим (г, /л, /г)-матрицу перестановок как

56 Гл. III. Теоремы выбора
матрицу из нулей и единиц, причем: 1) имеется в точно-
точности одна единица в каждой из первых I строк; 2) в каж-
каждой строке имеется не более одной единицы; 3) в каждом
из п столбцов встречается в точности одна единица.
Далее рассмотрим полиэдральное выпуклое множество К
всех (/п X л)-матриц Х = (хц), таких, что
х{у ^ О, I = 1, ..., ш, ] = 1, .. ., м,
/ха Х^' 1, I 1, • • •, I,
/
т,
Рассмотрим максимум г суммы 2 е*/*;/ на ВЬШУКЛОМ
I, }
множестве К- В этом случае, согласно теореме двойствен-
т п
ности, г есть также минимум для 2 и14~ 2 УУ' где
м._|_р.^с /=1, ..., га, /==1, .Г., л, а"" ^ > О,
/ — / -)- 1, . • •, т. Доказывается лемма, утверждающая,
что экстремальные точки множества К суть (/, т, ^-ма-
^-матрицы перестановок. Это нетрудно увидеть, так как всякая
матрица X может быть дополнена до двойной стохастиче-
стохастической (тХт)"матРиЦы X, если дополнить первые I строк
нулями. Таким образом, X есть комбинация (т X /^-ма-
/^-матриц перестановок, в которых элементы, лежащие на пере-
пересечении первых I строк и последних т — п столбцов, суть
нули. Следовательно, экстремум X соответствует экстре-
экстремуму той матрицы X, которая является (/, т, /г)-матрицей
перестановок в ее первых п столбцах.
Таким образом, максимум г для 2с(/*(/ на % дости-
достигается для (?, т, #)-матрицы перестановок, следовательно,
т п
г есть целое число. Так как минимум для 2 ^ 4" 2 ^у»
, = 1 /=1
где а{- -\- V] ^ с{у, также равен г, то следующий шаг состоит
в том, чтобы показать, что для получения минимума г
могут быть взяты целые значения и и V.
Наконец, при строгом соблюдении условий С и С* по-
показывается, что в качестве чисел ии V могут быть выбраны
нули и единицы, и из этого следует, что г=п и, таким
образом, существует система различных представителей,
включающая маргинальные элементы.

2. Приложения теорем 57
Этот результат может также быть получен из вышеука-
вышеуказанного алгоритма для нахождения систем различных пред-
представителей. Если мы вычеркнем все элементы, за исключе-
исключением маргинальных, то, согласно условию С*, существует
/ различных множеств, для которых ех, . .., ег могут быть взя-
взяты как представители. Если выбрать их в качестве 51?..., 5^
и восстановить оставшиеся элементы, то алгоритм завер-
завершается системой различных представителей, где эти эле-
элементы вводятся в качестве различных представителей для
некоторых г множеств, хотя и не обязательно множеств
51? ..., 5^. Алгоритм никогда не отбрасывает элемента как
представитель, но может перенести представитель из одного
множества в другое.
Задача распределения, или транспортная, возникла из
исследования наиболее экономичного способа распределения
продукции из нескольких источников снабжения в много-
многочисленные участки потребления. Математическая формули-
формулировка этой задачи весьма сходна с формулировкой задачи
о распределении должностей. Мы задаем (тХ^)-матрицу
и ищем матрицу Х — (х^), удовлетворяющую
условиям:
XI] — Су, I 1, • • • ,
и ищем способ минимизировать ^АуХу. Флуд [8] рассмот-
рассмотрел вычислительные аспекты решения этой задачи. Двой-
Двойственная задача включает в себя числа щ, 1=1, . .., т,
о,., /==1, ..., п (Флуд употребляет символ—щ), такие,
что
/=1,2,..., п.
Затем разыскивается минимум 2С./У/~Ь2ГА'- ^ качестве
решения мы получаем Ху(йу — и{ — V^) = 0. Таким обра-
образом, решение включает в себя нахождение значений Ху
в подходящих строках и столбцах, суммы которых равны
нулю, за исключением тех случаев, когда имеют место
равенства <1у = щ-\-Ъ]. Это приводит к несколько сложным
комбинаторным исследованиям графов, ассоциированных
с положениями (/, /'), для которых A^ = щ\

58 Гл. III. Теоремы выбора
Задачу о странствующем коммивояжере также мож]
сравнить с задачей о распределении должностей, но оод
имеет дополнительные усложнения. В этой задаче мы задае!
(яХя)-матрицу М = (с1у)9 где й^ выражает в общем вид*
обобщенное расстояние от /-го города до /-го. Требуется
найти маршрут, проходящий один и только один раз чер<
каждый город и имеющий минимальную протяженность,
Расстояния йу могут быть совершенно произвольными
не предполагаются симметричными или удовлетворяющим]
неравенству треугольника.
Здесь нам нужно найти матрицу перестановок
2 Э
у ру р ^
такую, чтобы 2^7*17 была минимальной. Это — то ж
самое условие, что и в задаче о распределении должносте]
(где слово „максимум" изменено на „минимум"), с то]
разницей, что перестановка должна быть я-циклом. М]
можем увеличить диагональные элементы йи и таким об*
разом быть уверенными, что минимум 2 йуХц не включа*
ни одного из них. Тогда перестановка, найденная так же|
как в задаче о распределении должностей, будет хщщ
становкой, не имеющей фиксированных элементов. Но эта{
перестановка не дает решения задачи о странствующем!
коммивояжере, пока не доказано, что она является я-циклом.1
Тем не менее этот подход является первым шагоЦ
к решению задачи о странствующем коммивояжере. Исходя
из этого, Флуд [9] и Данциг [4] пытались различными спо-
способами получить решение для некоторых частных случаев..
Мы можем присоединить к пространству области двойных!
стохастических матриц еще ряд неравенств. Так, если;
положить *12-[-*2а-|-#81г^2, то исключили бы 3 цикл2<
A, 2, 3). Общее число таких неравенств, необходимых для
исключения циклов, более коротких, нежели я-циклы,
фантастически велико. Однако применение некоторых из
них оказывается эффективным в частных случаях. Все же
нельзя сказать, что общее решение уже известно, даже
приблизительно.
ЛИТЕРАТУРА
1. Гейл, Кун и Таккер (О а 1 е Е)., К и И п Н. XV. апс1
Тискег А. XV.), Ыпеаг рго^гагшп^ апс1 Ше 1Ьеогу о!
^атез, т АсШНу Апа1у518 о/ РгойисИоп апй АИосаНоп,
317—329, №\у Уогк, 1951.

Литература
2. Глисон и Гринвуд (О1еа$оп А. М. апс! Огееп-
\уоос! К-), СотЫпа1опа1 ге1а1юпз апс! сЬготаНс §гарЬз,
Сап. ^. МаШ., 7, 1—7 A955).
3. Гофман и Кун (НоНтапА. апс1 К и Ъ. п Н. Л.), Зузьетз
о! сНзИпс! гергезегйаИуе апс1 Нпеаг рго&гатт^ (готовится
к печати в Атег. МаШ. Моп1Ыу).
4. Данциг, Фулкерсон и Джонсон (Оап121§ С,
Ри1кег$оп К. апс1 ЛоЬпзоп 5.)» 5о1иИоп о! а 1аг§е
зса1е 1гауеНп§-5а1е5тап ргоЫет, ^. Орег. Кез. 8ос. Атег.,
2, 393—410 A954).
5. Кёниг(К6п1§ С), ТЬеог1е с1ег епсШсЬеп ипс! ипепAПсЬеп
ОгарЬеп, СЬеЬеа, Ыем Уогк, 1950.
6. Купманс (Коортапз Т. С), ОрИтит иИНгаИоп о!
1Ье 1гап5рог1аИоп зуз^ет, Есопоте(г1с, 17, 136—146, 5ир-
рктеп! A949).
7. Манн и Райзер (Мапп Н. В. апс1 К у з е г Н.), 5у51ет5
о! сИзИпс! гергезеп1а11уе5, Атег. МагН. МопШу, 60,
397—401 A953).
8. Флуд(Р1оос1 М.), Оп 1Ье НИсЬсоск A151г1Ьи11оп ргоЫет,
Расфс I. МагН., 3, 369—386 A953).
9. Флуд (Р1оос1 М.), ТЬе 1гауеПп§-5а1е5тап ргоЫет, 5ет1паг
1П ОрегаИопз КезеагсЬ, рарег Ыо 13, 1955.
10. Хичкок (НПсЬсоск р. Ь.), ТЬе сИзМЫШоп о! а
ргодис! !гот зеуега1 зоигсез 1о питегоиз 1оса1Ше5, ^. МагН.
Ркуз., 20, 224—230 A941).
И. Холл М. (На 11 М., Лг.), О1511пс1 герге5еп1а11уез о! зиЬ-
5е1з, ВиИ. Атег. МагН. Зое., 54, 922—926 A948).
12. Холл Ф. (На 11 РЬ.), Оп гергезег^аИуез о! зиЬ5е15,
^. ЬопОоп МагН. Зое, 10, 26—30 A935).
13. Эрдёш и Секереш (Ргдбз Р. апс! Згекегез С),
А сотЫпа1ог1а1 ргоЫет 1-п ^еоте!гу, СотрозШо Ма(И.,
2, 463-470 A935).

Г Л А В А IV
СУЩЕСТВОВАНИЕ И ПОСТРОЕНИЕ СХЕМ
1. Предварительные замечания
Отбор материала для этой главы оказался особенно
затруднительным. В число невключенных вопросов входя^
матрицы Адамара, впервые исследованные Пэли, многий
до сих пор не решенные задачи, самые недавние исследо!
вания Брауера. В настоящей главе внимание сконцентри|
ровано на сбалансированных неполных блок-схемах, пре1
имущественно на симметричных схемах, включающих ко<|
нечные проективные плоскости. \
Современные знания в области блок-схем не только
неполны, но и в некоторых отношениях^беспорядочны. В блок!
схеме мы имеем V элементов (в статистических приложе|
ниях — совокупностей), размещенных в Ь блоках по к от^
дельных объектов в каждом. Каждый элемент встречаете^
г раз, а всякая неупорядоченная пара встречается А раз.!
Элементарные условия для параметров будут
Ък = ъг, гF—1) = ?ф —1), \
Если Ь = у, г = к, получаем симметрическую схему. Пер1!
вое из условий делается очевидным, тогда как вт<
сводится к к (к — \) — %{о — 1).
В некоторых случаях необходимые условия, налагаемы^
на параметры, являются достаточными для существований
схем Это справедливо для систем, в которых
схем Это справедливо для систем, в которых & = 3, а
К=\ или 2. Но в других случаях существуют арифмети!
ческие условия; так, для симметричных схем наиболее
важными будут, по-видимому, арифметические свойств^
разности к — Я, которую мы обозначим через п. С другой
стороны, многие схемы зависят от арифметических свойств]
V или г. Существование определенного класса схем оказа
лось невозможным, что выяснилось главным образом бла
годаря результатам Брука и Райзера [6], а также Човла|

2. Латинские квадраты 61
и Райзера [32]. Однако построена лишь чрезвычайно малая
часть возможных схем; трудности в исследовании других
случаев в настоящее время оказались непреодолимыми.
2. Латинские квадраты
Латинским квадратом называется квадратная таблица
из п элементов (чисел или букв), такая, что каждый из
них встречается в точности один раз в каждой строке и в
каждом столбце. Так/для п = 5 имеем 2 латинских квадрата:
12345 12345
23451 21453
34512 34512
45123 45231
51234 53124
Из заданного латинского квадрата мы можем образо-
образовать другой, переставляя строки или столбцы, производя
перестановку букв или же комбинируя эти операции.
Квадраты, получаемые друг из друга подобным образом,
называют эквивалентными. Легко установить, что всякий
латинский квадрат вида 5Х$ эквивалентен одному из
двух приведенных выше квадратов. При преобразованиях,
сохраняющих эквивалентность, будут сохраняться типы
разложения на циклы перестановок, определяемых какими-
либо двумя строками, скажем
\ \ \ \ ?) = A 5 3)B 4),
хотя этот тип разложения на циклы может относиться
к другим двум строкам, если строки переставлены. Таким
образом, множество всех типов разложений на циклы
остается инвариантным при преобразованиях эквивалент-
эквивалентности. Для первого из приведенных выше квадратов все
Ю типов разложений на циклы (мы считаем каждую пару
строк лишь в одном порядке) суть 5-циклы. Для второго
квадрата имеется 6 типов, являющихся 5-циклами, и четы-
четыре типа, состоящих из 3-циклов и 2-циклов, причем вторую
группу составляют разложения перестановок, в которых
участвует вторая строка.
Таблица Кэли для умножения в группе является,
разумеется, латинским квадратом, а первый из приведен-
приведенных выше квадратов представляет собой таблицу Кэли для

62 Гл. IV. Существование а построение схем
циклической группы пятого порядка. Это замечание убеж!
дает нас в существовании латинских квадратов всех порядков!
Существует геометрическая интерпретация латинских!
квадратов. Будем рассматривать каждое из п2 мест как^
точку и проведем через эти точки линии, образующие!
3 семейства: 1) строки квадрата; 2) столбцы квадрата;]
3) линии, связанные с каждым элементом квадрата, так-
что они проходят через те ячейки, в которые вписан этот*
элемент. Эти линии образуют 3-сеть с п2 узлами. Такая
сеть состоит из трех семейств линий, каждая из которых;
содержит п точек. Линии каждого множества не пересев
каются, и через каждую точку проходит в точности одна
линия каждого множества. Наоборот, 3-сеть может быть
интерпретирована как латинский квадрат. Эквивалентность
латинских квадратов можно рассматривать как переимено-
переименование линий каждого семейства при сохранении всей
3-сети неизменной. Существует 3! = 6 различных способов
рассматривать эти три „параллельных" пучка, соответствую-
соответствующих строкам, столбцам и линиям одинаковых элементов.
Вообще говоря, 6 латинских квадратов, получаемых из
одной и той же сети, не будут эквивалентны в ранее
принятом смысле. При желании можно рассматривать эту
взаимную замену „связей" (это общее название для строк,
столбцов и линий, соединяющих одинаковые элементы)
как эквивалентность в более широком смысле. Эта расши-
расширенная эквивалентность не будет вообще сохранять типы
разложений на цикле, но, как читатель сам может пока-
показать в качестве упражнения, оставит неизменным общее
число 2-циклов.
Сходство связей вновь делается очевидным, если пред-
представить латинский квадрат посредством п2 троек, выбирая
тройку (/, /, к) для случая, когда в ячейке /-й строки и
/-го столбца мы найдем элемент к. Условие, при котором
п троек представляют латинский квадрат, таково: для
всяких двух данных координат заданная пара однознач-
однозначных чисел и, V должна встречаться в тройке в точности
один раз. Это свойство, очевидно, сохраняется при пере-
перестановке координат.
Теорема о различных представителях может быть при-
применена к построению латинских квадратов следующим
образом.

2. Латинские квадраты 63
Теорема. Пусть задан латинский прямоугольник
с г строками и п^>г столбцами. Тогда мы можем
по меньшей мере (п — г)! способами добавить к /? новую
строку, чтобы построить латинский прямоугольник
вида (г-|-1)Хя.
Здесь под латинским прямоугольником вида г Xп
подразумевается прямоугольная вида г Xп таблица из п
букв, где каждая буква встречается один раз в каж-
каждой строке и самое большее один раз в каждом
столбце. Для каждого столбца / образуем множество 5у.
из п — г букв, которые не встречались в ;-м столбце.
Если мы сможем выбрать различные представители из
5Р 52, ..., 5П, то в множество различных представителей
каждая буква должна входить в точности один раз, что
может быть использовано для построения (г —[— 1)-й строки.
Разумеется и обратно, всякая (г-(-1)-я строка содержит
различные представители для 515 52, ..., 5„. Мы должны
теперь проверить условие С. Поскольку каждая буква
встречается г раз в /?, то она встречается в точности п — г
раз в множествах 5^ ..., 5„. Но тогда к множеств 5,-
содержат к(п— г) букв, считая и повторяющиеся; а так
как каждая буква встречается в этих к множествах самое
большее п — г раз, то они должны содержать по меньшей
мере к различных букв и тогда условие С удовлетворяется.
Из следствия этой теоремы вытекает, что существует по
меньшей мере (п — г)! различных представителей и таким
образом самое меньшее (п — г)! возможностей для образо-
образования (г-\-1)-& строки. Мы заключаем отсюда, что число
латинских квадратов вида п X п будет по меньшей мере
п! (п — 1)!.. .2 ! 1 ! В самом деле, существует п ! возмож-
возможных первых строк и только одна возможная последняя
строка. При добавлении последних двух строк опреде-
определяются типы разложения их на циклы по отношению ко
всяким другим строкам. Если существует с циклов, то мы
можем добавлять последние две строки 2е X 1 способами.
Следовательно, если с=1, то последние два множителя
2! 1 ! будут верными. Но все остальные множители будут
меньшими. В самом деле, второй множитель, как мы уже по-
показали, должен быть п \\е, а в работе Эрдёша и Капланского
[36] доказано, что к-я множитель приблизительно равен п \\ек,
если к мало по сравнению с п. По-видимому, это прибли-

64 Гл. IV. Существование и построение схем
жение не проходит, если к^>уп. Но даже приведенн
выше грубо приблизительное значение показывает, ч
число квадратов огромно, даже если допустить расширен*
ную эквивалентность; именно, в случае расширенной экви|
валентности существует по крайней мере 6 (п !)8 различны^
квадратов. Квадраты всех порядков вплоть до семи былц|
перечислены. Те из них, порядок которых не превосхо*]
дит 6, перечислены Фишером и Иейтсом [25], а Нортон [17|
перечислил G X 7)-квадраты. В работе Нортона была до-
допущена ошибка, которую обнаружил Сад [20], произведя!
независимую проверку числа G X 7)-квадратов Число не-
неэквивалентных квадратов дано в следующей таблице:
п \ 2 3 4 5 6 7
1 1 2 2 17 563 .;
Таблица Нортона составлена с учетом расширенной экви-
эквивалентности, благодаря чему число типов G X 7)-квадрато^
свелось к 147, 24 из которых при перестановке связей
дают 1 класс эквивалентности каждый, 4 — 2 класса, 61$
класса и 58 — 6 классов каждый. В соответствии с числом
автоморфизмов различные классы эквивалентности могут да-
давать разное число различных квадратов. Если при подсчете
общего числа всех различных квадратов Тп, мы произве-
произведем нормирование упорядочением первой строки и первого
столбца, то получим число приведенных квадратов Iп и
= п\(п—\)\ 1п. Здесь
п I 2 3 4 5 б 7
1„ 1 1 4 56 9408 16 942 080
п
Говорят, что два латинских квадрата ортогональны, если
при наложении одного квадрата на другой каждая пара
одинаковых чисел встречается один и только один раз.
Вот, например, ортогональная пара квадратов вида 8 X 8.
наложенных друг на друга
11 22 33 44 55 66 77 88
28 31 46 13 64 75 82 57
37 48 15 26 73 84 51 62
42 17 24 35 86 53 68 71
54 63 72 81 18 27 36 45
65 74 87 52 21 38 43 16
76 85 58 67 32 41 14 23
83 56 61 78 47 12 25 34

2. Латинские квадраты 65
Ортогональная пара латинских квадратов эквивалентна
4-сети, проходящей через п2 точек, где точками будут
являться п2 ячеек, первое семейство „параллелей" задается
строками, второе — столбцами, третье — одинаковыми чис-
числами первого квадрата, а четвертое — одинаковыми числа-
числами второго квадрата. Связи взаимозаменяемы. Мы можем
представить ортогональную пару посредством множества
пг четверок. Например, одна из таких четверок F, 7, 4, 3)
будет четверкой, отнесенной к точке в 6-й строке, 7-м
столбце, 4-й линии третьего „параллельного" пучка и 3-й
линии четвертого „параллельного" пучка. Эта конкретная
ортогональная пара имеет то интересное свойство, что четыре
латинских квадрата, получаемых вычеркиванием каждой
координаты поочередно, суть латинские квадраты групп.
Для первых трех координат (первые однозначные числа,
указанные выше) это есть абелева группа типа D, 2). Для
первой, второй и четвертой координат (вторые однозначные
числа, упоминаемые выше) это будет диэдральная группа.
Для первой, третьей и четвертой получаем квадрат
12 3 4 5 6 7 8
3 8 16 7 4 5 2
5
7
8
6
4
2
6
4
7
1
3
5
7
5
6
8
2
4
8
2
5
3
1
7
1
3
4
2
8
6
2
8
3
5
7
1
3
1
2
4
6
8
4
6
1
7
5
3
который является групповой таблицей для диэдральной
группы. Для второй, третьей и четвертой координат имеем
квадрат
18 7 2 4 5 6 3
7 2 18 6 3 4 5
5 4 3 6 8 12 7
3 6 5 4 2 7 8 1
8 12 7 5 4 3 6
2 7 8 13 6 5 4
4 5 6 3 18 7 2
6 3 4 5 7 2 18
который является групповой таблицей для элементарной
абелевой группы.
5 М. Холл

66 Гл. IV. Существование и построение схем
Возможно также построить множество квадратов, кото-
которые попарно взаимно ортогональны. Множество т пар
ортогональных латинских квадратов эквивалентно т~\-2
параллельным пучкам, проходящим через п2 точек. Макси-
Максимумом для т будет п — 1, и такое множество называется
полностью ортогональным. Стивене [22] заметил, что пол-
полное множество ортогональных квадратов дает конечную
евклидову плоскость; справедливо и обратное.
Эйлер [35] первый исследовал латинские квадраты,
предложив в 1779 г. задачу о 36 офицерах. Он поставил
вопрос, возможно ли выбрать 36 офицеров 6 рангов из 6 пол-
полков по одному офицеру каждого ранга от каждого полка и рас-
расположить их в каре так, чтобы в каждом ряду и в каж-
каждой шеренге было бы по одному офицеру каждого ранга и по
одному от каждого полка. Задача эквивалентна построе-
построению парных ортогональных 6X6 квадратов. Терри [23] сис-
систематическими попытками показал, что это невозможно.
Была высказана гипотеза, что для п = 4к-\-2 не суще-
существует пар ортогональных квадратов: она подтвердилась
пока только для случаев п — 2 и /г = 6. В результате об-
обширных исследований с помощью СВАК (Калифорнийский
университет) не удалось построить ортогональную пару
A0 X Щ квадратов. После 100 часов работы быстродей-
быстродействующей машины доля исследованных возможных слу-
1ссв оказалась настолько малой, что никаких заключений
ке/ьзя было сделать. Впрочем, некоторые выводы можно
сделать на том основании, что аналогичные поиски орто-
ортогональных пар (8 X 8)-квадратов дали свыше 200 пар менее
чем за 15 минут.
Наши познания об ортогональных квадратах весьма
(Урывочны. Манн [12] нашел метод построения взаимно
(| тогональных квадратов, являющийся лучшим из извест-
нь:х методов. Пусть п = р11 р12 ... ре/ будет разложением п
в произведение простых чисел; здесь р1У р2, ..., рг — раз-
различные простые числа. Манн строит т взаимно ортого-
ортогональных (п X я)-квадратов, где т — наименьшее из чисел
р\'—1, ..., р7 — 1. Он берет конечное кольцо /?, кото-
которое является прямой суммой #=Р1 фТ^ ф ... ф Рг, где /^
есть конечное поле порядка рр. Возьмем л:0 = 0, х1 = \, ...
..., хп в качестве элементов /?. Возьмем также элемент

3. Системы троек Штейнера 67
... -}- ип где мультипликативный порядок и1
р. не меньше чем т (если каждый и1 есть простой ко-
корень, это будет верно). Тогда в г-м квадрате (г = 0,.. . ,т—1)
ш (*\/) месте будет стоять элемент иТх{-\-х^ Почти оче-
очевидно, что г-н квадрат есть латинский квадрат. И чтобы
гоказать, что при наложении г-го и 5-го квадрантов появ-
шется каждая пара, нам нужно прежде всего установить,
&о разность иг — и3 имеет инверсию. Этот результат дает,
^например, три взаимно ортогональных квадрата порядка 20.
^Никто не нашел большего числа ортогональных квадратов,
гарантирует результат Манна. Для полноты множества
^ортогональных квадратов требуется существование аффин-
Рдой и, следовательно, проективной конечной плоскости.
|Это будет рассмотрено позже.
3. Системы троек Штейнера.
В 1852 г. Штейнер [34] поставил следующую задачу.
Для какого целого числа п возможно разделить п букв
на тройки таким образом, чтобы каждая пара букв встре-
; чалась в одной и только одной тройке? Здесь мы имеем
в виду неупорядоченные пары и неупорядоченные тройки.
Необходимые условия для п легко отыскать. Каждая буква
встречается в тройке с двумя другими буквами. Так как
'буква встречается в точности один раз с каждой другой
^буквой, то п—1 должно быть четным, и, следовательно,
}п= 1 (той 2). Так как каждая тройка содержит три пары,
; а каждая^пара встречается точно один раз, то общее число
пар п(п—1)/2 должно быть кратным трем. Комбинируя
эти условия, получаем, что п имеет вид п = 6&4-1 или
6& + 3.
В 1859 г. Рисе [19] конструктивным методом показал,
что необходимые условия являются также достаточными
и что система троек существует для каждого п — 6к -|- 1
или п = 6к-\-3. Для п=3, 7, 9 мы получаем решения
я = 3*123
М. Холл
п —■-
7*123 г
Й • Л. ** \*г / |
145
167
246
257
347
356
, — д. 123
145
168
179
249
256
278
348
357
369
467
589

68
Гл. IV. Существование и построение схем
Эти решения являются единственными в пределах эквива-
эквивалентности. Два решения будут называться эквивалентными,
если одно может быть получено из другого подстановкой
букв и перестановкой троек. Для п= 13 существуют в точ-
точности два неизоморфных решения.
В оба решения мы можем включить тройки
1.
1
1,
1,
1,
2,
4,
6,
8,
Ю,
3
5
7
9
2, 4,
2, 5,
2, 8,
11 2, 9,
1, 12, 13 2, 11,
6
7
10
12
13
4, 3,
4, 7,
8
9
7, 3, 11
4, 10, 13 7, 8, 13 8, 5, 11 6, 9, 11
4, 11, 12 7, 10, 12 8, 6, 12 3, 5, 12
Для первого решения мы также берем тройки
3, 6, 10, 3, 9, 13 5, 6, 13 5, 9, 10
Для второго решения мы берем
3, 6, 13 3, 9, 10 5, 6, 10 5, 9, 13
Системы троек Штейнера из 15 букв изучили Кол,
Уайт и Каммингс [9], которые нашли 80 различных систем.
Позднее Фишер [24] перечислил системы из 15 букв, оты-
отыскав 79 систем и пропустив одну из таблицы Кола. Не-
Недавно автор и Свифт произвели систематическое исследо-
исследование систем из 15 букв, используя СВАК. Это оказалось
проверкой результата, найденного Колом, который не был
нам заранее известен.
Задавая 2 системы штейнеровых троек порядков 1Х и /2,
мы можем построить другую систему порядка (г{ш следую-
следующим образом: пусть (а/? а;, ак)— какая-либо тройка си-
системы А порядка /1? а (Ьг, Ь5, Ьи) — какая-либо тройка
системы В порядка 1г. Образуем новую систему С с гх1г
элементами с1/91= 1, .. ., 1ХУ /= 1, ..., 1Х. Тогда (с(г, с/3, скп)
будет тройкой системы С, если: 1) г = $ = г/ и (а,-, а;-, ак)
является тройкой из А\ или 2) / = / = 6 и FГ, Ъ8, Ьи)
является тройкой из В; или 3) как (а19 а;-, ак) является
тройкой из А. так и (Ьп Ь3, Ьи) является тройкой из В.
Легко проверить, что эти правила образуют С-систему

3. Системы троек Штейнера 69
т I — ■. ., -I .,... II. —.1 1.. I.!. ., .1 ,— ■■ ... , ■ ■■ .1 —. --,— -,— I — И I -I I - I - -I.——.,— —! .111 С»
троек Штейнера. Те тройки, в которых г = 8 = и = 19
образуют подсистему С, изоморфную Л, а те, в которых
{ = ] =к=19 образуют систему, изоморфную В.
Построение систем троек Штейнера всех порядков
/г = 6^ —|— 1 или 66-{-3, которое здесь будет дано, нашел
Мур [15].
Теорема. Если существует система троек Штей-
Штейнера порядка 1г, содержащая подсистему порядка^,, и
если существует также система троек Штейне распо-
распорядка ^^>1, то мы можем построить систему порядка
^ = ^^'\-^1(^% — ^3)> содержащую 1Х подсистем порядка\1г
и одну подсистему порядка 1У.
Доказательство. В этом доказательстве мы счи-
считаем, что единственный элемент образует систему троек
порядка 1, где при гь = \, требование, чтобы система
порядка 1г содержала одну систему порядка 1г, удовле-
удовлетворяется для любой системы порядка 12^>\. Мы строим
множество элементов 1 = 1г-\-1%Ц2 — /8), использованных
в (гх-\- 1)-множествах:
о0. аг, а,, . . ., а.* ,
О1. "ц> • • • > 5»
- Ъ Ь ч — / /
Мы образуем тройки этих I элементов по трем прави-
правилам: 1. Ассоциируем элементы 50 с системой порядка 1Ъ и
берем тройку (а,., ау., ак), если эти элементы соответствуют
тройкам в этой системе. 2. Приводим 50 и всякое5^- (/ = 1, ...,
гх) в соответствие с системой порядка ^2, а 50 —
в соответствие с подсистемой порядка /3- Тройки эле-
элементов а уже определены правилом 1. Другие тройки
содержат самое большее один элемент а. Образуем тройки
(ат, Ьу, Ь1к) или (Ьи, Ьш, Ь1г), согласно ^ соответствию
с системой порядка 1г. 3. Если (/, 6, г) есть тройка си-
системы порядка {г, образуем все тройки (Ь;х, Ьку,- Ьгг), где
вторые индексы удовлетворяют условию х -}- у -\-г=0(той8).
Эти три правила, взятые вместе, дают тройки для си-
системы порядка г, и мы устанавливаем, что 50 и 5,- (/= 1,..., 1Х)
образуют 1Х систем порядка 1Х, Первое правило дает тройки
6*

70 Гл. IV. Существование и построение схем
в 50, и мы замечаем, что тройка, содержащая два эле-
элемента а, будет иметь в качестве третьего элемента также а.
Второе правило дает тройки с одним элементом а и вто-
вторым Ь, а третий элемент будет также Ь из той же самой
строки, что и второй. Это правило дает также тройки для
элементов Ь из одной и той же строки. Здесь в случае
двух элементов Ь из Я,, третьим элементом в тройке будет
или а, или Ь из той же строки. Третье правило охваты-
охватывает тройки из трех различных строк. Если выбирать эле-
элементы из двух строк, то третий ряд определяется системой
порядка 1Х. Условие *-|-#-|-г = 0 (той 5) для вторых
индексов убеждает нас в том, что всякие два элемента могут
быть выбраны произвольно, и определяет единственным обра-
образом третий элемент тройки. Мы также замечаем, что в соот-
соответствии с этим условием, поскольку $ = 0 (той 5), элементы
^15» •••» ^из образуют подсистему порядка 1Х.
Мы можем доказать существование систем всех поряд-
порядков я = 6&-{--1 и п = 6к-\-3, используя несколько част-
частных случаев этого правила:
(А)
(В) ^ = 3, ^2 = г , ^з=1, ^ = 3/ —2, I ^ 3,
(С) ^ = 0, т2 = ь , 63 = «3, х~— о/ —о, I ^ 7,
Х 2 +
(Е) <1 = 3, *, = /', ^3 = 7, 1 = ЪГ —14, Г^ 15.
Мы можем применить правила рекуррентно, чтобы построить
системы для всех значений п по модулю 36. Начинаем
с систем порядков 1, 3, 7, 9, 13. Заметим, что для при-
применения правила (Е) мы должны иметь подсистему порядка 7
в системе порядка V. В самом деле, для всякого допусти-
допустимого порядка, не превосходящего 15, существует система
с подсистемой порядка 7. Так как система порядка
\ C) имеет подсистемы порядков 11} 12 и 1г,
то свойство иметь подсистему порядка 7 сохраняется при
построении. Нам нужен метод более быстрого построения,
обеспечивающий достаточно начальных систем с подсисте-
подсистемами порядка 7. Для некоторых начальных порядков дол-
должны быть использованы специальные случаи, вроде
85=1+7A3—1).

4. Построение блок-схем
71
Вид л (=1)
366-
366-
366-
366-
366-
366-
366-
366-
366-
366-
366-
366-
-1
-3
-7
-9
-13
-15
-19
Ь 21
-25
-27
-31
-33
Правило
(В)
(А)
(А)
0»
(Е)
(А)
(В)
(О)
(В)
(А)
(А)
(С)
Значение для V
126-
186-
186 -|
66-
126-
186-
126-
66-
126-
[-1
-1
^3
-1
-9
-7
-7
-3
-9
186 + 13
186 + 15
126 + 13
4. Построение блок-схем
Системы троек Штейнера являются частными случаями
общего класса размещений, которые мы называем блок-
схемами. Предположим, что мы имеем V элементов, раз-
размещенных в Ь блоках, так что каждый блок содержит к
различных элементов, каждый элемент появляется в г
блоках и каждая (неупорядоченная) пара элементов встре-
встречается всего к раз. Существуют два элементарных условия,
которым эти пять параметров должны удовлетворять
Первое выражает равенство общего числа появлений всех
элементов при подсчете двумя способами. С одной стороны,
каждый из Ь блоков содержит к элементов, а с другой
стороны, каждый из V элементов встречается г раз. Второе
условие вытекает из рассмотрения пар, в которых встре-
встречается данный элемент хг. Он встречается г раз и всякий
раз в паре с одним из к — 1 других элементов, но он также
должен встречаться с каждым из остающихся V — 1 эле-
элементов % раз. Системы троек Штейнера являются частным
случаем, в котором 6 = 3, %=1. Следовательно, в этом
случае
откуда
V
2г+1, Ъ
гBг

72 Гл. IV. Существование и построение схем
Таким образом, оказывается, что г = О, 1 (той 3), а
у = 6т-|-1 или у=:6т-|-3, т. е. получаются те самые
необходимые условия, которые мы рассматривали в пре-
предыдущей главе. В случае систем троек Штейнера мы ви-
видели, что этц необходимые условия являются также до-
достаточными для существования решения. Но вообще эти
условия не являются достаточными; необходимо найти
условия более глубокого характера. Те условия, которые
известны, имеют арифметическую природу, причем совер-
совершенно неясно, каковы же должны быть истинные условия.
Если V = Ь, то к = г и к (к— 1) = Я(^—1). В этом
случае мы называем схему симметричной блок-схемой.
Частным случаем симметричной блок-схемы при Я—1
является конечная проективная плоскость. Эти схемы под-
подверглись наиболее интенсивному изучению. Для симмет-
симметричных схем самым важным числом, связанным с сущест-
существованием схемы, оказывается число п = к — к. В самом
деле, в случае проективных плоскостей плоскость суще-
существует, когда п — простое число или степень простого
числа. Неизвестны никакие другие значения, которые да-
давали бы конечные плоскости. Но мы очень еще далеки от
какого-либо категорического утверждения.
В статистике называют блок-схемы сбалансированными
неполными блок-схемами. Более общим видом схем яв-
является частично сбалансированная неполная блок-схема,
которая отличается от сбалансированных схем тем, что
число появлений пар не постоянно. Всякий элемент хх
может иметь I видов связей, а х1 встречается в /-й связи
^ раз: /=1, 2, ...,/. Если возможно разделить все эле-
элементы на группы таким образом, чтобы соответствующее
соотношение между двумя элементами зависело только от
группы, к которой они принадлежат, то схема называется
схемой с групповой делимостью. Латинские квадраты и,
более общо, ортогональные множества латинских квадра-
квадратов могут быть рассматриваемы как схемы с групповой
делимостью. Рассмотрим тп элементов, разделенных на т
групп из п элементов. Будем говорить, что элементы
в одной и той же группе первично связаны, и положим
Ях = 0. Будем также утверждать, что элементы в разных
группах вторично связаны, и положим Я2= 1. Тогда в слу-
случае п2 блоков по т элементов в каждом мы получим мно-

4. Построение блок-схем 73
жество элементов, которые определяют т — 2 взаимно
ортогональных латинских квадрата точно тем же способом,
каким они были изображены ранее. Образцом превосход-
превосходного изложения теории частично сбалансированных схем
является исследование Боса, Клэтуорти. и Шрикхенда [4].
В нем освещены как статистическая, так и комбинаторная
стороны вопроса. Эта работа содержит также весьма обшир-
обширную библиографию.
В блок-схемах элементы размещены в множества оди-
одинаковых размеров; требуется также, чтобы единичные эле-
элементы, а также пары элементов появлялись одно и то же
число раз. Мы можем даже требовать большего и рассма-
рассматривать так называемые тактические конфигурации, требуя,
скажем, чтобы все тройки, четверки или пятерки встреча-
встречались одинаково часто. Об этом так мало известно, что мы
упомянем только 2 случая, которые связаны с любопыт-
любопытными с математической точки зрения группами Мэтью.
Дробно-линейная группа (т. е. проективная группа проектив-
проективных линий) есть множество преобразований
ах
X-
сх -\- й '
где аи — Ьс ф 0, рассматриваемых как перестановки эле-
элементов поля Рч включающего формальный элемент оо, такой,
что 1/0 = оо. Если мы положим, что Р есть поле из 11 эле-
элементов, то дробно-линейная группа преобразует 6 элемен-
элементов оо, 1, 3, 4, 5, 9 в 132 множества. Каждая пятерка
из 12 элементов оо, 0, 1, ..., 10 встречается точно в одной
из шестерок. Наибольшая группа, включающая в себя
систему шестерок, есть пятиричная транзитивная группа
Мэтью порядка 12-1Ы0-9-8. Аналогично дробно-линейная
группа над полем с 23 элементами преобразует 8 элемен-
элементов оо, 0, 1, 3, 12, 15, 21, 22 в 768 восьмерок, таких, что
каждая пятерка из 24 элементов оо, 0, 1, ...,22 встре-
встречается в точности в одной восьмерке. Наибольшей группой,
содержащей восьмерки, является пятиричная транзитивная
группа Мэтью из 24 букв порядка 24•23•22•21•20•48.
Эти две группы суть единственные известные пятирич-
пятиричные транзитивные группы (естественно, за исключением
знакопеременных и симметрических групп), а подгруп-
подгруппы с фиксированной буквой являются единственными

74 Гл. IV. Существование и построение схем
известными четверичными транзитивными группами. Эти
группы благодаря некоторым свойствам являются единст-
единственными в своем роде. Обобщая теорему Жор дана, автор [27]
показал, что единственная четверичная транзитивная группа
конечного или бесконечного числа букв, если подгруппа,
фиксирующая 4 буквы, имеет конечный четный порядок,
является группой Мэтью из 11 букв (разумеется, вместе
с симметрическими группами из 4 и 5 букв и знакопе-
знакопеременными группами из 6 и 7 букв). Группы Мэтью из 23
и 24 букв суть транзитивные расширения группы колли-
неаций проективной плоскости с 21 точкой. Цассенхауз
[31] показал, что существуют единственные четверичные
транзитивные расширения группы коллинеаций любого про-
проективного пространства.
Далее мы будем рассматривать только сбалансирован-
сбалансированные неполные блок-схемы с параметрами у, 6, г, к, к,
удовлетворяющие необходимым условиям Ък — Vг, г {к—1)
О
а — 1). О них известно больше, нежели о других
классах схем, а все методы, применявшиеся во всех дру-
других случаях, были применены и для них.
Существование нескольких классов этих схем было до-
доказано непосредственным построением. Мы уже рассмот-
рассмотрели системы троек Штейнера, которые являются частным
видом схем для к — 3, %=1, откуда 2г —у — 1 и ЗЬ =
1)г. Здесь имели место два случая: V —
1,
(+) и \
6=B/+1)C/+1), г = 3/+1, 6 = 3, Я=1. Когда 1 = 2
и & = 3, мы получим 2г = 2(р — 1) и V^ = ЗЬ, откуда
+ и г(г+1) = 36. Здесь г = 0,2(тос!3) и
6+1 6 + 3
+ (+) ()
V =0,1 (той 3). Если V имеет вид 6/+1 или 6^ + 3, то
ясно, что две системы троек Штейнера для тех же самых
V элементов, взятых вместе, дадут решение. Мы должны,
таким образом, найти решение для
Е2: V = Ы-\-4, 6 = 2B*+
Метод построения, предложенный Босом [2], основан на
применении разностей некоторой аддитивной группы, обычно
вычетов по модулю некоторого целого числа т. Для рядов

4. Построение блок-схем 75
Ех мы берем один элемент Ь и аддитивные вычеты по
модулю Ы-\~Ъ. Сначала мы берем Ы-\~Ъ троек F, /,
у —|— 3^ —|— 2), /=^0, ..., Ы-\-А(то&Ы-\-Ь). Они дают нам
Ь дважды с каждым другим элементом, а каждую пару
один раз, причем они отличаются друг от друга на
\Ъг-\~2 или — C^ + 2) еееЗ^ + 3 (той 6^ + 5).
Теперь мы используем два множества разностей:
1. (/, 2* + 3 —2/, 2^ + 3 — /) = (*„ у19г()9 где /=1,
2, ..., г-{-\. Здесь г1=^х\
{ \
2. B/, Ъ1 + 3 — /, Ъ1 + 2 — /) = (*„ у,-, г,), где / = 1,
2, ..., Л Здесь х{-\~у1 -\-21 = Ы-\-5.
С помощью первого множества мы строим все тройки
+ = 0, ...,
/ + * / + , +
-{- 4 (той 6^ -{- 5), а из второго множества — все тройки
+ + +
/ + + + « /
-[" ^ (той 6^ -|~ 5). Мы утверждаем, что эти тройки при-
приводят к построению схем. Для всяких двух различных
вычетов г, 5 (той 6^ -{- 5) возьмем одну из двух величин
г — 5 или 5 — г, лежащих в последовательности 1, ...,
Ъг-\~2. Назовем ее их меньшей разностью й. Тогда г и 5
встречаются одновременно один раз в тройке одного из
рядов, всякий раз, когда & является одной из меньших
разностей множества разностей. Предположим, что й=^
для некоторого / первого ряда. Тогда (/~Ь2«)
й(й6|5 Е й
Ь Ъ/)
^й(той6^-|-5). Если положим г — 5 =й(той6/-{-5),
то, определив / посредством /-(-24- = г(тос167-|-5), полу-
получим /-{-^ = / + 2/ — й-^г — с1~8 и тройка (/, /-{-X;,
у-[-2г) = (у, 5, г) будет содержать г и 5. В обоих рядах
Хц у(, г{ — меньшие разности, и мы находим, что каж-
каждая меньшая разность 1, 2, ..., 3^ —|— 1 встречается в точ-
точности дважды, а разность Ы-\-2 — однажды, встречаясь
второй раз в тройках F, /, / —(— 3/ —|— 2). Следовательно,
каждая пара встречается одновременно в точности два
раза, и мы построили схему. Для рядов Ег мы исполь-
используем элемент Ь и вычеты по модулю 6/ + 2. Берем тройки
F, /, / + 3/+1), / = 0, ..., 6/ + 1 (той6^ + 2) и таким
образом получаем тройки, чьи меньшие разности заданы
посредством
2/, 2* + 1—/), 1=1, ..., /,
B/, 3/ + 1—^'. 3/+1—0, 1=1 ••- '•

76 Гл. IV. Существование и построение схем
Это использование разностей можно рассматривать как по-
построение схем с заданной группой автоморфизмов. В двух
приведенных выше случаях мы имели группу автоморфиз-
автоморфизмов порядка V— 1, которая была циклической и, поскольку
рассматривались элементы, имела транзитивные составляю-
составляющие, причем одна из них состояла из единственного эле-
элемента Ь, а другая содержала оставшиеся V — 1 элементов.
Это можно обобщить, если рассматривать автоморфизм
с несколькими транзитивными составляющими. В качестве
примера возьмем семейство систем троек Штейнера с па-
параметрами V + ++
= 3, А=1. Если мы возьмем элементы у1? /2, у,, гАе /
в каждом случае пробегает значения от 0 до 21 (тос! 21 -\- 1),
мы получим всего 6/-(-3 элементов. Теперь возьмем 3/ ба-
базисных троек [г19 Bг — 1)х, 02], [/2, B^ —/J, 08], [/„
B^ — гK, 0г], где 1=1, ..., / во всех трех случаях,
и также единственную базисную тройку @1? 08, 08). Если
мы возьмем Ъг-\-1 базисных троек и добавим повсюду
у = 0, 1, ..., 21 (той 2г —[— 1), мы получим всего
C/-{- 1) B^ —{— 1) = Ь троек. Это будут штейнеровские си-
системы троек, поскольку в базисных тройках каждая „сме-
1)
1)
шанная" разность гф5, ^ = 0, 1, ..., 21 (тос!
и каждая „чистая" разность йгг= 1, 2, ..., 21 (тос!
появляются в точности один раз, так как Ъг — с8=(Ь — с)г8=
= Лгз (той 21 -\~ 1), где 6Г и с5 входят в базисную тройку.
Здесь г, 5=1, 2, 3. По-видимому, для систем троек Штей-
нера в случае ь = Ы -\-\ требуется не столь простое
построение.
Существенная часть этого „метода симметрически повто-
повторяющихся разностей", естественно, состоит в отыскании
подходящих разностных чисел. Важно отметить, что в одном
случае модуль был V— 1, а в другом — у/3. Но поскольку
мы показали, что необходимые условия являются также
достаточными, нет оснований предполагать, что эти числа
имеют какое-либо конкретное арифметическое значение,
относящееся не к постановке задачи, а только к ее част-
частному построению.
При построении схем были использованы разнообразные
остроумные применения конечных полей. Приведем дока-
доказательство простого случая.
Теорема. Если М — 1 есть степень простого числа

4. Построение блок-схем 11
д —рг, то существует симметрическая схема с парамет-
параметрами ю = Ь — А1—1, & = г —2/—1, К = (—1.
Доказательство. Рассмотрим конечное поле К
из <7 элементов. Используем хорошо известные факты,
что в К имеется (д— 1)/2 ненулевых квадратов и (д— 1)/2
неквадратов и что произведение двух квадратичных вычетов
или двух неквадратов есть квадрат. Итак, поскольку
<7 = 3(тос14), то элемент —1 есть невычет. Предположим,
что я2 — у2 — \ имеет N решений (хг, у2) при х2ф0,
у2ф0. Мы утверждаем, что х2 — у2 = с1 при ЛфО, х2ф0,
у2ф0 тоже имеет N решений (#2, у2). Потому что, если
= и2 — квадратные решения х2—у2 — с1, являющиеся
квадратичными вычетами, то они находятся во взаимно
однозначном соответствии с такими же решениями
X2 — У1=1, где Х—х\и, У = у1и. С другой стороны,
если А не является квадратом, то с1 = — и2 и мы получим
взаимно однозначное соответствие с X* — У2 = 1, полагая
У = х/и, X == у\и. Отсюда в каждом случае х2 — у2 — с1ф0
имеет N решений при х*фО, у2=^0. Таким образом, все
значения х2 — у2 при л:2=^0, у2фо, х2 ф у2 дают каждую
разность йфО одно и то же число раз N. Но всего суще-
существует [(д — 1)/2] [(д — 3)/2] разностей х2'— у2 и всего ц — 1
значений й. Отсюда (д—1)Л^ = (^—1)(? — 3)/4 и
М CI4
1
Теперь для д = 4/ — 1 получим (^—1)/2 = 2/ — 1 и
3)/4 = г — 1. Следовательно, если мы образуем
\Ъ\Ъ \Ь
)/
множеств (хх-\-Ъух%-\-Ъ% ..., #2*_х-\~Ь), где
суть ненулевые квадраты в К, а 6 пробегает <у элементов
/С, то получим М — 1 блоков с 2г — 1 элементами в каж-
каждом блоке. Каждый элемент хю встречается один раз для
данного / в форме х1-\-Ь, так что каждый элемент встре-
встречается 21—1 раз. Для некоторой пары до, 2, если хаз — г =
определяя Ь как Ь = ш — х{, получаем
1р р { у
х-ь-\- Ь = ш< Х;-\-Ь = г. Следовательно, пара до, г встречается
в блоке так же часто, как д, появляется в качестве раз-
разности й = х( — х^ Но это имеет место М = (<7 — 3)/4 раз
для всякого Л ф 0, так что мы имеем симметрическую схему
для Х = Ы — 1—1. Это полностью исчерпывает доказа-
доказательство.
г Другие построения, зависящие от конечных полей, более
сложны. Так, если М -]-1 есть степень простого числа, то

78 Гл. IV. Существование и построение схем
существует схема с а=12/-|-4, 6 = C/ + 1) D^ —|— )в
41 й 4 Л=1. Здесь при 4/-}-1 = <7 = рг мы
4
снова применяем поле К из ц элементов. Построение
будет проведено без доказательства. Пусть х будет перво-
первообразный корень из К. Тогда для некоторого нечетного
Ь мы получим (хь-{-1I (хъ— 1) = х\ где 5 также" нечетное.
Наши V = 12/-]- 4 элементов будут состоять из трех вос-
воспроизведений элементов К и дополнительного элемента оо.
Следующие четверки будут являться базисом схемы
(л:2/, *
' / = 0,
:2^+2/, *2
(<*>> ох, о2, о,).
Мы получим всю схему, добавляя к элементам базисных
четверок все элементы К поочередно.
Много блок-схем дают конечные геометрии. Евклидова
геометрия 5 измерений над полем К с рг элементами, ко-
которую мы обозначим Е6(8, рг), имеет точки Р = (хх, ..., х3),
х1 ^ К, ь = \, •.., 5 и подпространства всех измерений
1, ..., 5. Пространством и измерений будет множество
точек
и — минимальное для множества. Аналогично проек-
проективная геометрия 5 измерений над полем К, которую мы
обозначим РОE, //), имеет точки (рх0, рх19 ..., рхг)ф
Ф- @, ..., 0), *,- € К и р пробегает все поле К, исключая 0.
В РО E, рг) имеются подпространства всех измерений
1, ..., 5, а пространство и измерений будет векторным
пространством, определяемым и независимыми точками.
В конечной евклидовой или проективной геометрии
существует единственная прямая, соединяющая две различ-
различные точки. Если исходить из того, что в этих геометриях
две несовпадающие точки соединяет единственная прямая
и что каждая прямая содержится в одинаковом числе
подпространств размерности и, то из этого следует, что
если взять точки как элементы, то подпространства раз-
размерности и образуют блок-схему.

4. Построение блок-схем х 79
Теорема, и-мерное подпространство в РС($,
, образует блок-схему с параметрами
^^*^^^* ^^ А ^^^ ^^^ ^^ ^^ ^^^^^ 1'^ш* л^*^"^^*^^^* ^^ к
Употребляя ту же самую символику, мы получим следую
щую теорему.
Теорема, и-мерные подпространства в ЕС E,
= рг, образуют блок-схему с параметрами:
V = ^\
% и) — Ъ E, и — 1),
гE,
Конечные евклидовы или проективные пространства
размерности три или выше необходимо являются геомет-
геометриями с координатами из конечных полей, как было ука-
указано выше. Существуют, однако, конечные плоскости,
которые не могут быть получены из конечных полей: они
называются недезарговыми плоскостями.
Теорема. Прямые на проективной плоскости с п-\-1
точками на прямой линии образуют симметричную блок-
схему с параметрами
2 1,
Для всех известных плоскостей число п является сте-
степенью простого числа, но, может быть, существуют и дру-
другие плоскости, которые еще не построены. Следует сделать

80 Гл. IV. Существование и построение схем
одно существенное замечание. Блок-схема с параметрами
проективной или евклидовой плоскости будет определенно
плоскостью. Если блок-схема с параметрами для случаев
более высокой размерности является геометрией, то она
будет определенно дезарговой, но она может и не быть
геометрией. Так, V = Ь = \2^, г = к = 40, А,= 13 суть
параметры для проективных геометрий РО C, 3), содер-
содержащихся в РО D, 3), но, как мы увидим далее, существуют
и другие схемы с этими же параметрами. Различие возни-
возникает потому, что в случае плоскостей все плоскости, прямые
и точки удовлетворяют комбинаторным требованиям. Но для
РОC, 3), содержащейся в РСD, 3), комбинаторные тре-
требования распространяются на 4-пространства, 3-пространства
и 2-пространства как пересечения 3-пространств, но ни в коем
случае не прямых. Превосходное описание этих конструк-
конструктивных методов дано в книге Манна [13].
Свойство симметрических схем, которое будет доказано
в следующем разделе, таково, что всякие два блока имеют
вместе в точности К элементов. Так, если мы возьмем
фиксированный блок 5е, то пересечениями В% с Вх, ...,
Вю+1 будут множества р1Э ..., р^,+1, каждое из которых
содержит К элементов. 5в и множества р содержат все
вхождения к элементов Бв. Следовательно, в рр ..., р^+1
каждый элемент из к встречается г — 1 раз, а каждая
пара встречается К—1 раз. Множества р образуют так
называемую производную блок-схему. Аналогично, если
мы вычеркнем Бе и все р, то у нас останется так назы-
называемая остаточная схема. Так, для симметрической схемы
мы имеем V — V, 6 = а, г —к, к = к, Х = Х. Для произ-
производной схемы V'= к, Ь' — V — 1, г'= к — 1, к' =А,,
1. Для остаточной схемы V" = V — к^Ь" = V — 1,
, = к — Я, V■==.%,
Приведем пример из статьи Нанди [16]:
6 15 к 7 1
1
2
3
4
1
2
3
5
1
2
6
7
1
3
7
8
1
4
5
6
1
4
6
8
1
5
7
8
2
3
а
8
2
4
5
8
2
4
7
8
2
5
6
7
3
4
5
7
3
4
6
7
3
5
6
8
9
10
11
12
9 12 9 11 11 10 9 10 9 11 10 10 9 9 13
10 13 13 14 12 13 10 12 14 12 11 13 12 11 14
11 14 15 15 15 14 12 15 15 13 14 15 14 13 15

4. Построение блок-схем 81
|Для производной схемы получаем V — 7, 6=14, г = 6,
= 3, К = 2. Для остаточной схемы получаем V = 8,
*==14, г = 7,
5 Если отбросить последний блок, то остаточная конфи-
конфигурация включает элементы 1, ..., 8. Здесь для каждого
|блока четверок существует другой блок, который имеет
1три общих с ним элемента. Но для остаточной схемы,
|полученной отбрасыванием первого блока и еще каких-
каких-либо элементов, это не так. Следовательно, одна и та же
симметричная схема может давать неизоморфные остаточные
схемы.
О применении разностей в построении схем уже гово-
говорилось. Мы рассмотрим здесь систематическую попытку
построить симметрические схемы, которые даются разно-
разностями по модулю V. Как обычно, к (к — 1) —^ (V — 1).
Если а1? а2, ..., ак(тойV) суть вычеты, такие, что для
любого й = О (тос! V) сравнение
а1 — ау=й (той V)
справедливо в точности для К выборов (а/? а/) из всех а,
то мы назовем а19 ..., ак множеством разностей по мо-
модулю V. Если задать множество разностей, то V множеств
, ..., ак-\-^}(то<^V)
для / = 0, 1, ..., V — 1
образуют блоки симметричных схем. Это получается
потому, что если г =^8 суть два различных вычета, то
существует подходящее т, такое, что 1=а1-\-т (той у),
5 = а,--|-т (той у), когда а1 — а,]=& = г — 5 (той V). Таким
образом, г и 5 появляются вместе в точности в X блоках,
а блоки образуют симметричную блок-схему. В схеме, задан-
заданной множеством разностей, отображение г—>г-\-1 (тос! V)
определяет автоморфизм порядка V схемы, которая является
циклической и транзитивной относительно элементов, а так-
также относительно блоков. Нетрудно показать, что, наоборот,
-симметричная схема с таким автоморфизмом задана мно-
множеством разностей по модулю V. Ниже использованы ра-
работы автора и Райзера [26, 28].
Может случиться, что для некоторого I взаимно про-
простого с V отображение г —> г1 (тос! V) является также авто-
автоморфизмом схемы, заданной множеством разностей. Такое

82 Гл. IV. Существование а построение схем
число I мы называем мультипликатором разностного мно-
множества. Очевидно, что мультипликаторы множества разно-
разностей образуют мультипликативную группу модуля V.
В множестве разностей ах, ..., ак (тос! V) определяющим
свойством мультипликатора I является то, что }а1У (а2, ...,
1ак (тос! V) для некоторых 5 будут соответственно кратными
а1-{~8) аш-\-89 ..., ак-\~$(тос! V). Каждое ранее найденное
множество разностей имеет нетривиальные мультиплика-
мультипликаторы. Задание мультипликатора г помогает определить,
существует или нет множество разностей; если оно сущест-
существует, то знание I облегчает его построение. Теперь мно-
множество разностей а19 ..., ак(тойV) дает ту же самую
схему, что и всякий блок ах-\-и, ..., ак-\-и, и для муль-
мультипликатора I ^(а1-\-и), . . ., г (ак -\- и) являются кратными
аг-\-8-\-ги, .. ., ак-\-$-\-1и. Следовательно, если мы можем
выбрать и так, чтобы 5 -{- ?и = и (тос! у), а это мы опре-
определенно можем сделать, если (I— 1, у)=1, то множество
разностей ах-\~и, ..., ак-\~и переводится мультиплика-
мультипликатором I само в себя. В свою очередь, для любого известного
множества разностей мы можем, выбирая и подходящим
образом, найти множество, переводимое само в себя любым
мультипликатором. Простое применение теоремы, приводи-
приводимой ниже, показывает в случае, когда V — 73, & = 9, Я= 1,
что 2 является мультипликатором. Так как B— 1, 73)= 1,
то существует множество, переходящее в себя, и мы его
находим с помощью множества разностей 1,1,2,4,8, 16,
32, 37, 55, 64 (той 73). Всякое другое множество отли-
отличается от данного некоторым множителем.
Теорема. Пусть а1У ..., ак — множество разно-^
стей по модулю V. Предположим что р есть простой
делитель п = к — X, что (р, ю)=\ и что р^>к. В таком
случае р является мультипликатором множества разностей.
Доказательство. Мы имеем кольцо полиномов
с неизвестным л и его обратным значением к'1 (той (х°— 1)).
Это кольцо обладает тем основным свойством, что, если
/ = / (тос! у), то ** = д/ (той (х° — 1)). С разностным множе-
множеством а1? .. ., ак (тос! V) ассоциирован полином 6 (х) =
= ха^-\~ ... -\-хак Тогда определяющим свойством множе-
множества разностей при п = к — X является
О (*) 6 (х-!) = п + ХТ (х) (тос! (х° — 1)), (А)

4. Построение блок-схем 83
где
В доказательстве используется, во-первых, прием ослаб-
ослабления модуля в (А) и затехМ усиления его. Поскольку р | п,
то из (А) следует ослабляющее соответствие Ь(х)Ь(х~1)^
= 0 (той р, той Т (х)). Теперь умножим на 6 (х~1)р~1 и заме-
заметим,что б (х~ 1)р = б (х~р) (той р), потому что полиномиальные
коэффициенты кратны р. Следовательно, б (х) б (лг*7) =
= 0 (той р, той Т (х)). Замечая, что А (х) Т (х) =
==А A) Т (х) (той (**— 1)), потому что х°— 1 = (* — 1) Т (х),
мы получаем
б (х) б (лг*) = рМ(х) + АТ(х) (той (^ — 1)). (В)
Теперь, положив х=1 в этом соотношении, получим
=рМ A) -|-Лг^. Поскольку &2 = п-^-^ и р делится
на и, это дает Л^ = ^(тойр); итак, поскольку (р, у)==1,
то Л = ^ (той у). Используя это, преобразуем (В) в (С)
б (х) б (х~р) = р7? (д:) + ^^ И (той (^ — 1)). . (С)
Здесь коэффициент Ъ1 любого члена с х1 слева неотрицате-
неотрицателен, а справа 64- = Цтос1р), и так как р^>^, то Ь^Х,
откуда коэффициенты /? (х) будут также целыми неотри-
неотрицательными. Полагая в (С) х= 1, мы имеем й2=р/?A)-^-^у,
откуда р/?A) = п. Меняя л: на д: в тождестве (С), по-
получаем
—1)),
так как Т {х~1) = Т (х). Замечая также, что (р, у) = ,
Т (хр) ^ Т (х) (той (%^ — 1)), и заменяя х на хр в (А), имеем
б (хр) б (д:-^) = п-\-КТ (х) (той (^ — 1)). (Е)
Теперь произведение левых сторон (С) и (Б) будет таким
же, как произведение левых сторон (А) и (Е). Полагая
равными произведения правых сторон и замечая, что
р# (л;) Т (х) = р% A) Т (х) = п Т (х) (той (** — 1)), получаем
после упрощений
р/? (х) рК (х-!) = п2 (той (хю — 1)). (Р)

84 Гл. IV, Существование и построение схем
Так как Я{х) и Ц(х~г) имеют неотрицательные коэф-
коэффициенты, то в (Р) не может быть более одного неисче-
зающего члена в рК(х) или в р!^(х~1). Следовательно,
для некоторого 5 р#(х) = пх~*, р&(х~1)=^пх8. Подставляя
это в (О), имеем
6 (хр) Ь(х~1) = пх* + \Т (х) (той (хи — 1)). (О)
Умножая на 6(л:), применяя (А) и упрощая, находим
6 (хр) = х3 6 (*) (тос! (ху — 1)). (Н)
Но это есть как раз условие того, чтобы р было мульти-
мультипликатором множества разностей.
Условие р ^> Л,, разумеется, не имеет геометрического
смысла при Л,= 1, но это оказывается излишним для всех
известных множеств разностей. В самом деле, для каж-
каждого из известных множеств разностей (п, у)=1, а для
всех этих множеств всякий делитель числа п является мульти-
мультипликатором. Сингер [21] показал, что гиперплоскости проек-
проективных дезарговых пространств могут быть представлены
множеством разностей. Любое известное планарное (к= 1)
множество разностей дает дезаргову плоскость, и естественно
предположить, что это имеет место всегда, так как Манн
и Эванс [14] показали, что для всех значений я<;1600
планарное множество разностей не может существовать,
если п не является степенью простого числа, и что для
значений /г, равных степеням простых чисел, существуют
дезарговы плоскости, хотя, возможно, для некоторых из
этих значений могут также существовать недезарговы мно-
множества разностей.
Множества разностей подвергались различным обобще-
обобщениям. Бос [3] обобщил теорему Сингера, выведя аналогич-
аналогичную теорему для евклидовых пространств, а Гофман [8]
доказал соответствующую теорему о мультипликаторах для
евклидовых плоскостей. Еще более широкого обобщения
достиг Брук [5], который рассматривал симметрические
схемы для группы О порядка V автоморфизмов транзитив-
транзитивной и регулярной как относительно элементов, так и от-
относительно блоков. Он перенес соотношение (А) на кольцо
Г группы О над рациональным полем. Если группа С —
абелева, р\пч (р, а)=1, а также р^>Я, то р будет муль-

5. Теоремы существования 85
типликатором такого х—+хр, которое является автоморфиз-
автоморфизмом схемы.
Когда для параметров V, к существует множество раз-
разностей, то оно не обязательно единственное. Так, для
с; = 31, к = 15, X = 7 мы имеем самый первый пример
(т. е. наименьшее к), где существуют два неизоморфных
решения. Первым решением являются квадратичные вычеты
1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28 (той 31)
и вторым решением —
1, 2, 3, 4, 6, 8, 12, 15, 16, 17, 23, 24, 27, 29, 30 (той 31).
Если мы возьмем 3 в качестве первообразного корня,
то существуют вычеты с индексами 0, 1, 3 (той 6). В самом
деле, автор [30] доказал, что существуют два неизоморф-
неизоморфных решения для V = р, к — (р— 1)/2, 1 = (р — 3)/4 всегда,
когда р — простое число вида р = Ахг-\-27. Если сущест-
существует бесконечное множество простых чисел этого вида,
то существует бесконечно много примеров неизоморфных
разностных множеств с одними и теми же параметрами.
Еще более удивительный случай четырех неизоморфных
решений при у=121, & = 40, А, = 13 приведен в указан-
указанной выше статье.
5. Теоремы существования
Всякое конечное размещение V объектов в Ь блоках
может быть представлено (у X ^-матрицей А = {а1})\
1= 1, ... , V, /= 1, . .. , Ь (объекты и блоки перенуме-
перенумерованы), где а^=1, если /-й объект находится в / -м
блоке, и а/у-=0, если не находится. Обозначим символом АТ
транспонированную матрицу А. Тогда
..., V, A)
где г{ = Ъи — число всех появлений /-го объекта, а
— число совместных появлений в блоке
у у л
/ -го и / -го объектов. Таким образом, для блок-схемы
(и, более общо, для частично сбалансированных схем) мат-
матрица В включает информацию, определяющую главные
требования. То же самое соотношение может быть выра-
выражено посредством квадратичных форм от V переменных
*!, х2, ... , Ху, связывающих переменную с каждым объ-

86 Гл. IV. Существование и построение схем
ектом. Если теперь мы свяжем блок В;- с линейной формой

X /у*/' то
^^ B)
Для решения спорных вопросов относительно существо-
существования схем весьма полезно рассматривать матрицу В как
данную, а A) как уравнение относительно А с тем огра-
ограничением, что А состоит из нулей и единиц, или анало-
аналогично рассматривать B) с заданным ф, из которого дол-
должны быть найдены все Ь.
Имеются две теоремы существования, которые исхо-
исходят непосредственно из матричных формулировок. Если
задана блок-схема, то ги = г для всех I, и К^=К для
всех 1^=]\ так что
г ... 'к
В = \ '. '. ). C)
■Л ... /"■
Мы без труда найдем детерминант от В
D)
Если г = Х, то схема тривиальна, так как, если рас-
рассматриваются все появления каждого х1 с каждым дру-
другим Хр каждый блок состоит из всех V объектов. Следо-
Следовательно, нам нужно рассмотреть только /*^>А,, а в этом
случае -<М В ф 0. Отсюда мы можем вывести неравенство
Фишера
^ V. E)
В самом деле, если Ь <^V, то ранг А будет меньше,
чем V, и В будет вырожденной, что противоречит тому,
что йе1Вф0. Для симметричных схем легко находится
более сильный результат.
Теорема. Если в симметричной блок-схеме V чет-
четное, то к — X является квадратом.
Доказательство. Когда Ь = V, А является квад-
квадратной матрицей, так что <М В = (<МЛJ. Но для симмет-

5. Теоремы существования 87
ричной схемы к2 — к-=ьк — Л,, и поскольку г = к, то
\ к2. Следовательно, йеЩ = к2(к — к)*'1. Но
\
для того, чтобы с!е1 В был квадратом, а V — четным, тре-
требуется, чтобы разность к — Л, была квадратом. Это про-
простое и сильное условие не было найдено вплоть до 1950 г.,
когда оно было открыто независимо Човла и Райзером [32],
а также Шрикхендом [33]. В обоих случаях исследования
были стимулированы новым подходом, введенным Бруком
и Райзером [6].
В 1949 г. Брук и Райзер обнаружили, что в матрице,
или в квадратичной формулировке схем, условие, чтобы
пц были нулями и единицами, означает, что они а 1ог1юп
являются элементами рационального поля. Но в этой трак-
трактовке соотношение A) для симметричных схем доказывает
рациональную конгруэнтность В и тождественной матрицы,
а B) соответственно доказывает рациональную эквивалент-
эквивалентность квадратичной формы С и суммы V квадратов
^ (*,,..., дд=2>*'+2 X *«*<*/=2*7- F)
Для рациональной эквивалентности квадратичных форм
пригодился мощный аппарат Хассе — Минковского, где
применяется гильбертов символ норменного-вычета. Мы да
дим здесь элементарный вывод вытекающих отсюда условий.
Обозначим к — к = п. Тогда
Ь\+... + Ц = п(*> + ...+х1) + Ь(х1 + ...-{-х9У. G)
Рассмотрим сначала случай, когда 0=1(тос14). По
теореме Лагранжа всякое целое число п есть сумма четырех
квадратов, а произведение двух сумм четырех квадратов
рационально выражается ^через сумму четырех квадратов.
Таким образом, п(х]~{-х}^1-\-х}^г-\-х}^^ в G) может
быть выражено в виде #*4~#?+1 + #?+» + #*+« при у, ра-
рациональных относительно х, и наоборот.
Так, если V=\ (той 4), имеем
, (8)
где уу = х^ а все Ь и ш = хг4~--- Л~ху выражены раци-
рационально через независимые переменные у19 ... , уу. Теперь
(8) является тождеством в независимых переменных
1

Гл. IV. Существование и построение схем
У19...,Уг Предположим, что Ь1 = Ь11у1-]г... ^у
Если Ъххф\ и мы положим Ь1 = у1 или если Ьи=1 и
мы положим Ь1 =— ух то в любом случае мы получим
соотношение, которое мы можем рассматривать как требо-
требование, чтобы ух был некоторой рациональной комбинацией
переменных у2, ... , уу, а также дающее Ь\ = у\. Выполнив
это требование, получаем
(9
Продолжая этот процесс для Ь2, ... , Ьу-Х, мы оконча-
окончательно получаем
\ \ A0)
Здесь Ь.о и IV, которые всюду сохраняли свою независи-
независимость, рационально зависят оту^. Это существенно, так как
если бы такое соотношение, как A0), выполнялось для лю-
любых Ьу, уу и до, тождественно равных нулю,-оно не имело
бы смысла. Теперь, взяв в качестве ую целое, которое яв-
является произведением знаменателей до и Ьу в A0), полу-
получаем уравнение
A1)
разрешимое в целых числах при х=^0, как следствие су-
существования схемы для ю= 1 (той 4). Когда V = 3 (тос! 4),
мы добавляем к обеим частям G) по пх\+и где ху+1 —
новая переменная, и получаем, как выше,
A2)
с независимым ую+х. Это]означает, что уравнение
A3)
разрешимо в целых числах. Эти результаты мы объеди-
объединяем в теореме.
Теорема. Если существует симметрическая схема
с параметрами V, к, к и мы обозначим п^=к — Я, то:
а) при V четном п будет квадратом; б) при V нечетном
выражение г2 = пх2 + (— 1 Уу ~1)/2 Яу2 разрешимо в целых
числах, которые не все равны нулю.
Справедливо и обратное, именно, если эти условия вы-
выполняются, то A) и B) имеют рациональные решения.

5. Теоремы существования 89
Когда п — квадрат, мы можем положить
...,у, A4)
чтобы получить рациональное решение B). Но чтобы до-
доказать противное, вообще говоря, оказывается необходи-
необходимым более глубокое применение аппарата Хассе — Мин-
ковского.
Применяя эту теорему к проективным плоскостям, мы
имеем А=1 и ъ^=п2 -\-п-\-\, которое нечетно для лю-
любого п. Для п = 0,3 (той 4) мы получаем V = 1 (тос! 4)
и разрешимость г2^пх2-\-у2 очевидна. Но для
я = 1,2 (той 4) мы получаем V = 3 (той 4) и в соответствии
с хорошо известными результатами теории чисел
г2 = пх2 — у2, или г2 \у2 = пх2 разрешимы в целых числах,
не равных нулю, тогда и только тогда, когда п является
суммой двух квадратов: п^=а2-\-Ъ2. Отсюда мы получаем
важное следствие.
Следствие. Необходимое условие существования про-
проективной геометрии с п -\- 1 точками на прямой состоит
в том, что если я = 1,2 (тос! 4), то п имеет вид:
п = а%-\-Ь*.
Это следствие было основным результатом оригиналь-
оригинальной статьи Брука и Райзера. В ней доказано, что не су-
существует геометрий для п = 6, 14, 21, 22, ... . Так как
геометрия существует всегда, когда п является степенью
простого числа, то п =10 — наименьший сомнительный
случай. Тэрри еще раньше показал, что для я = 6 плоско-
плоскости не существует. Однако следует подчеркнуть, что из
вышеупомянутого результата не вытекает результат Тэрри,
так как существование пары ортогональных (п X ^-квад-
^-квадратов может оказаться возможным и в случае, если пол-
полное множество взаимно ортогональных квадратов не су-
существует. В самом деле, по построению, осуществленному
Манном, существует пара ортогональных B1 >( 2 ^-квад-
^-квадратов, хотя не существует даже геометрии этого порядка.
Другое свойство матрицы — инцидентность — вытекает из
того факта, что если 5 обозначает (у X с/)'матРицУ> гДе
каждый элемент — единица, то для симметрической схемы
A5)

90 Гл. IV. Существование и построение схем
Учитывая, что каждый объект появляется к раз, а каж-
каждый блок содержит к объектов, мы можем записать A)
в виде
\ A6)
где / — есть тождественная (уХ^)-матрица. Тогда, при-
применяя A5), запишем
A7)
Отсюда для симметричных схем получим
= (к — Я)/ + Я5. A8)
Это показывает, что матрица инцидентности А симметрич-
симметричной схемы перестановочна со своей транспонированной
матрицей. Такие матрицы называются нормальными) они
имеют много важных свойств. Теперь из A7) мы видим,
что в симметричной схеме всякие два различных блока
имеют вместе в точности Я элементов. Соотношения A5),
A6) и A7) зависимы, и в самом деле Райзер [18] доказал,
что соотношение A6) вместе с А8^=к8 влекут за собой
остальные соотношения и даже соотношение к (к — 1) =
1).
()
Другой подход был введен Коннором [10] в 1952 году.
Этот подход основан на том, что в B) формы Ь;- имеют
действительные коэффициенты. Так, если для пробы за-
заданы I начальных блоков и определены Ьг, Ь2, . .. , Ьи
то из B) следует, что
Л Ы Ц . A9)
Если схему можно дополнить, отыскав Ьг+1, ... ,
то форма C* должна быть полуопределенной. В самом
деле, поскольку все ^ рациональные, если 1 — Ь—V, то
симметрический детерминант, соответствующий B*, должен
быть квадратом. Если I ^> Ъ — у, то соответствующая ()*
будет вырожденной. Это испытание I начальных блоков
Коннор проводит в форме оценки {IX О~ДетеРминанта-
Положим, что Вг, ... , Вг — заданные I блоков. Тогда
пусть 8и- — число элементов в пересечении В[ и В;- (для
симметрической схемы мы знаем, что во всех случаях
$;у. —Я). Образуем матрицу Сг = (си), «, /=1 . . , /, где

5. Теоремы сущестсования 91
сп = (г — к) (г— Я), с1}' — %к — Г5/У«. Тогда теорема Коннора
выглядит следующим образом:
Теорема. Если возможно дополнить I заданных бло-
блоков В1, . .. , Вг до блок-схемы, тогда необходимо, чтобы:
а) с1е1С^0, если I <^Ь — у,
Ь) йе!С^ = 0, если 1~^>Ь — V,
с) еслиг = Ь — ю, ток(г)-ь+73+1 {г — Х)™-ь~1 йе\Сг является
полным целым квадратом.
Заметим, что если мы имеем дело с симметричной схе-
схемой, то С^ тождественно равна нулю и не содержит ника-
никакой информации. На практике эта теорема дает наиболее
полную информацию для почти симметрических схем, т. е.
когда V и Ь почти равны. В предыдущем разделе было
доказано, что существование симметрической схемы вле-
влечет за собой существование производной схемы и остаточ-
остаточной схемы. Обратное, вообще говоря, не имеет места.
Для симметричной схемы с параметрами V = Ь = 25,
к 9 7 — 3 остаточная схема имеет параметры V = 16,
]
рр
= 24, г = 9, й = 6, Я = 3. Бхаттачария [7] дает следую-
следующий пример:
1 2 7 8 14 15 1 4 7 8 И 16
3 5 7 8 И 13 2 4 8 10 12 14
2 3 8 9 13 16 5 6 8 10 15 16
3 5 8 9 12 14 1 6 8 10 12 13
1 6 7 9 12 13 1 2 3 И 12 15
2 5 7 10 13 15 2 6 7 9 14 16
3 4 7 10 12 16 1 4 5 13 14 16
3 4 6 13 14 15 2 5 6 11 12 16
4 5 7 9 12 15 1 3 9 10 15 16
2 4 9 10 11 13 4 6 8 9 И 15
3 6 7 10 И 14 1 5 9 10 11 14
12 3 4 5 6 И 12 13 14 15 16
Поскольку 5-й и 16-й из этих блоков имеют 4 общих
элемента: 1, 6, 12, 13, то ясно, что эта схема не может
быть расширена до симметрической, в которой любые два
блока имели бы в точности 3 общих элемента. Однако
существует симметрическая схема для V = 25, й = 9,
хотя существование вышеуказанной схемы не доказывает
этого. Симметрической схемой с Л,= 1 является проективная

92 Гл. IV. Существование и построение схем
плоскость. Остаточная схема является евклидовой плоско-
плоскостью, а хорошо известно, что всякая евклидова плоскость
может быть расширена до проективной плоскости. Коннор
и* автор [И] ^использовали аппарат из первой работы
Коннора, чтобы показать, что при Я = 2 всякая схема
с параметрами остаточной схемы может быть расширена
единственным образом до симметричной схемы. Пример
Бхаттачария показывает, что соответствующий результат
для к = 3 неверен. Разница, видимо, состоит в том, что
для симметричных схем при к=1 или Х = 2 производные
схемы тривиальны, в то время как для Я = 3 это не так.
Коннор и другие| применили этот ^аппарат к частично
упорядоченным блок-схемам.
Пытаясь выяснить, почему ^аппарат Коннора не может
дать никакой информации о симметрических схемах, Холл
и Райзер [29] получили результат противоположного харак-
характера. Если для симметрической схемы, параметры которой
удовлетворяют условиям Човла — Райзера, выбраны началь-
начальные блоки Вх, ..., Вг и если, поскольку это, очевидно,
необходимо, любые два различных В имеют к общих
элементов, то. выбирая Вг, ..., Ви чтобы определить
первые I столбцов, мы можем отыскать матрицу А с та-
такими I столбцами, которые не только действительны, но
даже рациональны и нормальны, удовлетворяющую урав-
уравнениям инцидентности: ААТ=АТА = В = (к — Я) I-{-К8.
Этот результат также был обобщен в ранних результатах
Алберта [1].
Дальнейшее применение этого метода^" к У теоремам
существования пока не осуществлено, но очевидно, что
этот метод гораздо более сильный, нежели метод Коннора.
Мы замечаем, что в B) линейные формы Ьх, . .., Ьъ
не только действительны, но также неотрицательны.
Таким образом, если мы испробуем начальные опытные
блоки, задавая Ь1У ..., Ьг> то получим
Отсюда, если начальные блоки можно дополнить до пол-
полной схемы, форма С} * должна быть суммой Ь — г квадра-
квадратов неотрицательных линейных форм. Условия, которые
могут быть наложены на (Э *, будут тем строже, чем больше
мы имеем ограничений в выборе начальных блоков и чем

5. Теоремы существования 93
большую информацию относительно существования и по-
построения схем мы получаем. Теперь Коннор использует
только то условие, что 0. * будет полуопределенной. Автор
поставил общий вопрос, могут ли полуопределенные формы
с неотрицательными коэффициентами всегда быть представ-
представлены в виде суммы квадратов неотрицательных линейных
форм. Профессор 'А. Горн доказал существование форм,
которые не имели этого свойства, а автору удалось по-
построить следующий пример:
,3_ _
\ о Х2Х* —
~2 *
Ясно, что С} полуопределенна и имеет положительные
коэффициенты. Мы покажем, что предположение о пред-
представимости ф как суммы квадратов неотрицательных форм
ведет к противоречию. Если С}=^Ь2., а некоторое
. . .ах(-\~Ьхк...), то смешанное произведение
не может взаимно уничтожиться с членами из других Ь
поскольку не существует отрицательных смешанных .произ-
.произведений. Отсюда Ь, в котором как члены с х2, так и
члены с хъ имеют положительные коэффициенты, не содер-
содержит других х, поскольку 0, не имеет членов хгхг, х2х^
хъхъ. Следовательно,
Если тепе ь в О мы положим
— оу 4_9г у —__^1_ ^1 у
х^ х2
2 2 '  2 2 '
5
то ф сведется к -^ (х2 -{- х3J и Р х должно быть полуопреде-
полуопределенным. Тогда

94 Гл. IV. Существование и построение схем
Следовательно,
Но мы сразу видим, что при ^ ^ , V, ^~ ^ о
о о
форма Ах\-\~~^х2хъ-\- Вх\ неопределенна, следовательно,
мы пришли к противоречию. Профессор Горн установил,
что формы B, имеющие то свойство, что (Р) — ($ есть
сумма квадратов неотрицательных линейных форм, состав-
составляют выпуклый конус К в пространстве, заданном коэф-
коэффициентами (?. Присоединенное пространство К * соответ-
соответствует формам, которые неотрицательны для неотрицательных
аргументов. Таким образом, подсчет экстремальных точек
в К * дал бы критерии, определяющие, будет форма (}
иметь свойство (Р) или же нет.
Во многих случаях может быть показано, что если
квадратичная форма ф, связанная со схемой, может быть
представлена как сумма самое большее Ь квадратов
неотрицательных линейных форм, то эти формы дают
решение схемы. Таким образом, оказывается, что число
слагаемых, пожалуй, самое решающее из всех условий.
Возможно, что теория выпуклых поверхностей даст су-
существенно новые вклады в комбинаторный анализ.
ЛИТЕРАТУРА
1. Альберт (А 1 Ь е г^1 А. А.), Ка1юпа1 погта1 та^псез
заИзГут^ Ше шсмйепсе е^иа^^оп, Ргос. Атег. Ма1Н. Зое,
4, 554—559 A953).
2. Бос (Возе К. С), Оп Ше сопз1гис1юп о! Ъа1апсес1 тсотр-
1е*е Ыоск екз^пз, Апп. Еи^етсв, 9, 353—399 A939).
3. Б о с (Возе К. С), Ап аШпе апа1о§ие о! Зт^ег'з Шеогет,
^. Ыйьап Ма1Н. Зое. (N3), 6, 1 — 15 A942).
4. Бос, Клэтуорти и Шрикхенд (Возе К. С,
С 1 а 1 ^ о г 1 Ь у Ш. Н. апс! 5 Ь г 1 к Ь а п с! е 5. 5.), ТаЫез
о! рагИаИу Ъа1апсес1 с1ез1§пз №ЙЬ 1^о аззос1а1е с1аззез,
ТесН. ВиИ. Ыо 107, ЫогШ СагоПпа А§г1си11ига1 Ехрег1теп1
51а1юпA954)
5. Б р у к (В г и с к К. Н.), ОШегепсе зе!з 1п а ПпНе §гоир,
Тгапз. Атег. Ма1Н. Зое, 78, 464—481 A955).
6. Брук и Райзер (Вгиск К. Н. апс1 Нузег Н. Л.),
ТЬе попех1з1епсе о! сег!а1п ПпИе ргб]'есЦуе р1апез, Сап
^. Ма(п, 1, 88—93 A949).

Литература 95
7. Бхаттача'рия (ВЬаНасЬагуа К. Ы.), А .._
Ьа1апсес! тсотр1е!е Ыоск с1е$1§п, Зс[тсе апй СиИиге, 9,
508 A944).
8. Гофман (НоНтап А. Л.), СусНс аШпе ркпез, Сап
^. МаНг., 4, 295—301 A952).
9. Кол, Уайт и Каммингс (Со1е Р. N.. \УЬ 11 е А. 5.
апс! Ситгтмп^з Ь. С), Сотр1е1е с1аззШса1юп о! Шас!
5уз1етз оп !Шееп е1етеп15, Мет. Ма(. Асай. 8а., XIV,
зесопс! тето1г, 89 рр. A925).
10. К он нор (Соппог \У. 5.), Оп 1Ье з!гис1иге о! ЬаГапсес!
тсотр1е!е Ыоск с1ез1§пз, Апп. МаНг. 8Ш., 23, 57—71
A952).
11. Коннор и Холл М. (Соппог \У. 5. апс! На 11 М., Лг),
Ап етЪескПщ* {Ьеогет !ог Ъа1апсес1 тсотр1е1е Ыоск с1ез1§пз,
Сап. У. МаНг., 6, 35—41 A953).
12. Манн (Мапп Н. В.), Оп 1Ье сопз1гисИоп о! зе1з о! огШо-
§опа1 ЬаИп 5^иа^е5, Апп. МаНг. 8(а(., 14, 401—414 A943).
13. Манн (Мапп Н. В.), Апа1уз1з апс! Оез1§п о! Ехрег1теп1з,
Ооуег РиЬПса11опз, 1пс, Ые^ Уогк, 1949.
14. М ан н и Э в а н с (Мапп Н. В. апс! Еуапз Т. А.), Оп
з1тр1е сШГегепсе 5е1з, 8апкпуа, 11, 357—364 A951).
15. Мур (Мооге Е. Н.), Сопсегп1п§ 1г!р1е 8уз1ет5, МаНг.
Апп., 43, 271—285 A893).
16. Нанди (ЫапсН Н. К.), А !игШег по!е оп поп-1зотогрЫс
зо1и11оп5 о! 1псотр1е1е Ыоск ск51§П5, 8апккуа, 7, 313—316
A946).
17. Нортон (Мог1оп Н. №.), ТЬе 7x7 5^иа^е5, Апп. Еп-
8еЫс8, 2, 269—307 A939).
18. Райзер (НузегН. Л.), А по!еопа сотЬ1па1ог1а1 ргоЫет,
Ргос. Атег. МаНг. 8рс, 1, 422—424 A950).
19. Рисе (К 1 е 5 5 М.), ОЬег е1пе 51етег5сЬе сотЫпа!ог15сЬе
Аи!§аЬе ^е1сЬе 1п 45-з1еп Вапс!е сЛезез Лоигпа1з, 5еКе 181,
яез1еШ ^огс1еп 151, СгеИе'з ^.. 56, 326—344 A859).
20. Сад E а с! е А.), Ап оггиззюп 1*п Ыог1оп'з Из! о! 7X7
5^иа^е5, Апп. МаНг. 8Ш., 22, 306—307 A951).
21. СингерE1П§ег Л.), А 1Ьеогет 1П !1п11е рго]'есЦуе §ео-
те!гу апс! зоте аррНсаИопз 1о питЬег 1Ьеогу, Тгап$.
Атег. МаНг. 5ос., 43, 377—385 A938).
22. Стивене E1еуепз Ш. Ь.), ТЬе сотр1е!е1у ог!Ьо§опа1
Ьа1т 5^иа^е, Апп. Еи^етсз, 9, 82—93 A939).
23. Терри (Таг г у С), Ье ргоЫёте с!ез 36 оН1с1ег5, С.
А85. Ргапс. Аь\ 8а., 1, 122—123 A900); 2, 170—203
A901).
24. Фишер (Р15сЬег К. А.), Ап ехаттаИоп о! 1Ье с!Шегеп!
ро551Ые зоШНопз о! а ргоЫет 1П тсотр1е1е Ыоскз, Апп.
Еицетсв, 10, 52—75 A940).
25. Фишер и Иейтс (р1зЬегН. А. апс! Уа1ез Р.),
51а115Иса1 ТаЫез !ог Вюю§1са1, А§г1си11ига1, апс! МесПса1
^езеагсЬ, 2пс! ее!., ОНуег апс! Воус! Ыс!., Ьопс!оп, 1943.
26. Холл М. (Н а11 М., Лг.), СусНс рго]есИуе р1апез, пике
МаШ. Л., 14, 1079—1090 A947).

96 Литература
27. Холл М. (Н а 11 М., Лг.) Оп а {Ьеогет о! Логс1ап, РасЦ[с
МаНг. ^., 4, 219—226 A954).
28. Холл М. и Ра из ер (Н а 11 М., Лг. агк! Нузег Н. Л.),
СусПс таскпсе та{псез, Сап. ^. МаНг., 3, 495—502 A951).
29. ХоллМ. и Райзер(На11 М., Лг. апс! Кузег Н. Л.),
Ыогта1 сотркИопз о! 1ПС1Aепсе та1г1сез, Атег. ^. МаНг.,
76, 581—589 A954).
30. Холл М. и Райзер (На 11 М., Лг. агк! 1^ у зег Н. Л.),
А зигуеу оГ сИ!!егепсе зеЬ, Ргос. Атег. МаНг. 8ос, 7,
975—986 A956).
31. Ц ас сен х а у с Bаз5'епЬаи$ Н.), ОЬег 1гапзШуе
Ег^ег1егип§ ^е^1ззег Огирреп аиз Аи1отогрЫ5теп еп^-
НсЬег теЬгсИтепз1опа1ег Оеоте1пеп, МаНг. Апп., 111,
748—759 A935).
32. Ч о в л а ги Райзер(СЬо^1а5. апс! К у з е г Н. Л.),
СотЫпа>опа1 ргоЫетз, Сап. ^. Маш., 2, 93—99 A950).
33. Шр'и к х ен д E Ь г 1 к Ь а пс! е 5. 5.), ТЬе 1тро5з1ЫШу о!
сег!ат зутте1г1са1 Ьа1апсес1 шсотр1е!е Ыоск ае51^пз. Апп.
МаИг. 8Ш., 21, 106—111 A950).
34. Штейнер E 1е 1 пег Л.), СотЫп?1;ог15сЬе Аи^аЬе,
СгеПе'8 ^.у 45, 181 — 182 A953).
35. Эйлер (Еи1ег Ь.), Соттеп1а11опе5 АгНЬтеИсае, II,
302—361, Петербург, 1849.
36. Эрдёш и Капланский (Е г с! о з Р. апс! К а р-
1апзку I.), ТЬе а5утр1оИс питЬег о! Ьа1т гес{ап§1ез,
Атег. У. МаНг., 68, 230—236 A946).

ОГЛАВЛЕ Н ИЕ
Предисловие к русскому изданию 5
Глава I. Введение и резюме 7
1. Введение 7
2. Общие направления и итоги 10
Глава II. Методы перечисления 13
1. Общие замечания 13
2. Перестановки и сочетания 13
*3. Рекуррентные формулы и производящие
функции 19
4. Разбиения 26
Литература 37
Глава III. Теоремы выбора 38
1. Основные теоремы 38
2. Приложения теорем 45
Литература 58
Глава IV. Существование и построение схем . . 60
1. Предварительные замечания 60
2. Латинские квадраты 61
3. Системы троек Штейнера 67
4. Построение блок-схем 71
5. Теоремы существования 85
Литература 94

М. Холл
КОМБИНАТОРНЫЙ АНАЛИЗ
Редакторы И. Л. Никольская, А. А. Бряндинская
Художник Н. А. Липин
Художественный редактор В. И. Шаповалов
Технические редакторы
Е. И. Щилина и Л. М. Харьковская
Корректор Р. %. Новик
Сдано в производство 28/УШ—1962 г.
Подписано к печати 14/ХП—1962 г.
Бумага 84 X Юв1/^ ~1,6 бум. л.
5,1 печ, л..
Уч.-изд. л. 4,6. Изд. № 1/1258
Цена 32 коп. Зак. № 332§
ИЗДАТЕЛЬСТВО
ИНОСТРАННОЙ ЛИТЕРАТУРЫ
Москва, 1-й Рижский пер., д. 2.
Первая Образцовая типография
имени А. А. Жданова
Московского городского совнархоза
Москва, Ж-54, Валовая, 28.
Отпечатано в Производственно-издательском
комбинате ВИНИТИ
Люберцы, Октябрьский просп., д. 403, Зак. 260

ИЗДАТЕЛЬСТВО ИНОСТРАННОЙ ЛИТЕРАТУРЫ
Выпускает серию брошюр под общим названием
«БИБЛИОТЕКА СБОРНИКА „МАТЕМАТИКА"»
Вышли из печати
В 1959 г.
Минусинский Я.,Сикорский Р., Элементарная тео-
теория обобщенных функций. Вып. I. Варшава, 1957, перевод с
английского, 3,5 изд. л.
Хёрмандер Л., К теории общих дифференциальных опе-
операторов в частных производных. Уппсала, 1959, перевод с англий-
английского, 6 изд. л.
Халмош П. Р., Лекции по эргодической теории. Токио,
1956, перевод с английского, 7 изд. л.
К а п л а н с к и й И., Введение в дифференциальную алгебру.
Париж, 1957, перевод с английского, 4 изд. л.
В 196 0 г.
К а р л е м а н Т., Математические задачи кинетической теории
газов. Уппсала, 1957, перевод с французского, 5,7 изд. л.
Хейман В. К., Многолистные функции. Кембридж, 1958,
перевод с английского, 8,4 изд. л.
НомидзуК., Группы Ли и дифференциальная геометрия.
Токио, 1956, перевод с английского, 6 изд. л.
Судзуки М., Строение группы и строение структуры ее
подгрупп. Берлин — Геттинген — Гейдельберг, 1956, перевод с англий-
английского, 7 изд. л.
Рутисхаузер Г., Алгоритм частных и разностей. Базель —
Штутгарт, 1957, перевод с немецкого, 4 изд. л.
И то К., Вероятностные процессы. Вып. I, Токио, 1957, пе-
перевод с японского, 6,1 изд. л.
В 196 1 и 19 62 гг.
Гренандер У., Случайные процессы и статистические
выводы. Стокгольм, 1960, перевод с английского, 8 изд. л.
Гординг Л., Задача Коши для гиперболических уравнений.
Чикаго, 1957, перевод с английского, 5,3 изд. л.
Гудстейн Р. Л., Математическая логика. Лейчестер, 1957,
перевод с английского, 7,9 изд. л.