«Комбинаторика» М. Холл

М.Холл

КОМБИНАТОРИКА

ИЗДАТЕЛЬСТВО «МИР» Москва 1970

Известный американский математик М. Холл уже знаком советскому читателю по изданным в русском переводе книгам — «Теория групп» (ИЛ, 1962) и «Комбинаторный анализ» (ИЛ, 1963). Настоящая книга является наиболее полным изданием в области комбинаторного анализа. Она состоит из трех основных частей: проблемы перечисления, теоремы выбора и связанные с ними вопросы и проблемы существования и построения блок-схем. Книга написана на высоком научном уровне и освещает самые новейшие достижения в области комбинаторики.

Она доступна весьма широкому кругу читателей и, несомненно, заинтересует математикой различных специальностей.

ОГЛАВЛЕНИЕ

Предисловие редактора перевода	5
Предисловие	7
Глава 1. Перестановки и сочетания	9
1.1. Определения	9
1.2. Приложения к теории вероятностей	13
Задачи	16
Глава 2. Формулы обращения	18
2.1. Принцип включения и исключения. Обращение Мёбиуса	18
2.2. Частично упорядоченные множества и их функции Мёбиуса	26
Задачи	32
Глава 3. Производящие функции и рекуррентные соотношения	33
3.1. Правила и свойства	33
3.2. Комбинаторные задачи	37
Задачи	42
Глава 4. Разбиения	45
4.1. Разбиения. Тождества и арифметические свойства	45
4.2. Асимптотические свойства p (n)	59
Задачи	63
Глава 5. Системы различных представителей	64
5.1. Теоремы Ф. Холла и Д. Кёнига	64
Задачи	78
Глава 6. Теорема Рамсея	79
6.1. Формулировка и доказательство теоремы	79
6.2. Одно приложение теоремы Рамсея	81
Задачи	83
Глава 7. Некоторые экстремальные задачи	85
7.1. Задача о назначениях	85
7.2. Теорема Дилуорса	90
Задачи	94
Глава 8. Выпуклые пространства и линейное программирование	95

8.1. Выпуклые пространства. Выпуклые конусы и двойственные им	95
пространства
8.2. Линейные неравенства	102
8.3. Линейное программирование. Симплексный метод	110
Глава 9. Графические методы. Последовательности де Брёйна	128
9.1. Полные циклы	128
9.2. Теоремы о графах	130
9.3. Доказательство теоремы де Брёйна	134
Глава 10. Блок-схемы	140
10.1. Предварительное обсуждение	140
10.2. Элементарные теоремы о блок-схемах	144
10.3. Теорема Брука — Райзера — Човла	149
10.4. Формулировка теоремы Хассе — Минковского. Приложения	155
Глава 11. Разностные множества	167
11.1. Примеры и определения	167
11.2. Конечные поля	172
11.3. Теорема Зингера	178
11.4. Теорема о множителе	183
11.5. Разностные множества в группах общего вида	189
11.6. Некоторые семейства разностных множеств	196
Глава 12. Конечные геометрии	230
12.1. Основания	230
12.2. Конечные геометрии как блок-схемы	235
12.3. Конечные плоскости	238
12.4. Некоторые типы конечных плоскостей	248
Глава 13. Ортогональные латинские квадраты	261
13.1. Ортогональность и ортогональные таблицы	261
13.2. Основные теоремы	263
13.3. Построение ортогональных квадратов.	269
13.4. Опровержение предположения Эйлера	277
Глава 14. Матрицы Адамара	283
14.1. Конструкции Пэли	283
14.2. Метод Уильямсона	299
14.3. Три новых метода	305
Глава 15. Общие методы построения блок-схем	308
15.1. Методы построения	308
15.2. Основные определения. Теоремы Ханани	308
15.3. Прямые методы построения	318
15.4. Системы троек	327
15.5. Блок-схемы с k>3	343
Глава 16. Теоремы о пополнении и вложении	348
16.1. Метод Коннора	348
16.2. Коположительные и вполне положительные квадратичные формы	365
16.3. Рациональные пополнения матриц инцидентности	378

16.4. Целые решения уравнений инцидентности		389
Приложение I. Уравновешенные неполные блок-схемы с числом		398
повторений каждого элемента от 3 до 15
Приложение II. Матрицы Адамара типа Уильямсона		410
Библиография		413
Предметный указатель		419
Предметный указатель
Автоморфизм блок-схемы 167	Включения и исключения принцип
Адамара матрица 283	(метод) 18, 19
Аксиомы проективной геометрии 230	Вполне положительная квадратичная
— — плоскости 238	форма 367
Аффинное пространство 235	Выделенные блоки 312
База 319	Выпуклая оболочка множества 81
Базисная точка 169	Выпуклое множество 95
Биномиальный коэффициент 10, 12	— пространство 95
Блок 65	— тело 81, 95
— критический 66	Выпуклый конус 97
Блок-схема 140, 309	Галуа поле 175
— дополнительная 347	Гаусса — Якоби тождество 53
— остаточная 144	Гиперплоскость 96, 179, 234
— производная 143	Голоморф группы 198
— разрешимая 274	Граничная гиперплоскость 96
— с делимостью на группы 275	Граф 129
— связь с ортогональными	2-граф 135
таблицами 275, 276	Групповое кольцо 191
— симметричная 143	— разностное множество 170
— уравновешенная относительно пар	Гуда теорема 134
элементов 271	Дважды связанные блоки 356
— — неполная 140	Двойственное пространство 101
— центрально разрешимая 312	Двойственности теорема 105
— циклическая 168	Двойственные задачи линейного
де Брейна последовательности 128	программирования 105, 110, 111
де Брейна теорема 136	Двойственный граф 135
Брука теорема 190	Дезарга теорема 231
Брука — Райзера теорема 241	Дезаргова плоскость 233
Брука — Райзера — Човла теорема	Диаграммы разбиения 48, 50
149	Дилуорса теорема 90
Бхаттачария теорема 337	Дирихле производящая функция 43
Веблена — Веддербёрна система 250	Дзета-функция 29
Веддербёрна теорема 234	Дополнение блок-схемы 347
Ведущий главный минор 159	Допустимость задачи линейного
m-вершина 131	программирования 105, 111
Витта теорема 381	Евклидово пространство 95
	Задача о беспорядках 19

—— встречах 20

—— гостях 24

—— кёнигсбергских мостах 133

—— назначениях 85, 108—109

—— супружеских парах 24

—— школьницах 335 Замыкание множества 96 Зингера теорема 179 Зингеровы разностные множества

196

Изоморфные блок-схемы 167 Инцидентности матрица 141

—отношение 230

—система 140

Йонсена теорема 388 Квадратичный вычет 155

—закон взаимности 156

—невычет 155

Кёнига теорема 72 Киркмана задача 335, 336 Класс разности 321 Конгруэнтность 381 Конечная геометрия 230 Конечное поле 172 Коннора метод 349 Конфигурация 231

Коположительная квадратичная форма 367

—— — тест для проверки 378 Кососимметрического типа матрица

290

Лангранжа теорема 151 Латинский квадрат 74

—прямоугольник 73, 74

Лежандра символ 156 Линейное программирование 104,

105

Линейно упорядоченное множество

27

Линия в матрице 72 Локально конечное частично

упорядоченное множество 27 Макнейша теорема 263 Манна теорема 267

Матрица инцидентности 141

—кососимметрического типа 290 H-матрица см. Адамара матрица Мёбиуса функция 21 Множитель разностного множества

183, 184, 190

Модулярность 231 Недезаргова плоскость 233 Независимые элементы 91 Неприводимый полином 175 Несравнимые элементы 90

Нормализованная матрица Адамара

283

Норма точки 95 Общих представителей система 75

Опорная гиперплоскость 96 Опорное решение 119 Оптимальное назначение 85 Орбита 319 Ориентированный граф 129 Ортогональная таблица 262 Ортогональные векторы 262

—латинские квадраты 244

—матрицы 261

Осевое преобразование 115, 116 Оси правило выбора 120 Основное матричное соотношение

144

Остаточная блок-схема 144 Отделяющая гиперплоскость 96 Паппа теорема 231 Параллельное множество

трансверсалей 310 Параллельные блоки 243 Первообразный элемент 177 Перестановка 9, 10 Петля 129 Поле 172

Полиномиальный коэффициент 13 Полный цикл 128 Полуполе 254

Порядок конечной проективной плоскости 241

Почти-поле 253

Представление квадратичной формы

381

Примитивный корень (первообразный элемент) 177

«Принцип ящиков» 174 Проективная геометрия 178, 230 Производная блок-схема 143 Производящая функция 33

—— экспоненциальная 34 Прямая сумма матриц 383

—— полей Галуа 227

Прямое произведение матриц 288 Путь 129 Равноблочная компонента 271

Разбиения целого числа 45, 48, 50

—— — арифметический свойства 56 Разбиения целого числа

производящая функция 49 Различных представителей система

64, 66

—— — алгоритм нахождения 70, 71 Размерность проективного

пространства 230

(v, k, λ)-разностное множество 168 Разностных множеств типы 196, 197 Разрешимая блок-схема 274 Райзера теорема 146 Рамсея теорема 79

Свободное множество блоков 271 Свойство «здоровой

наследственности» 334

— «нездоровой наследственности»

334

Связанные блоки 356 Связный граф 129 Символ норменного вычета

Гильберта 158

— Хассе 159 Симметричная блок-схема 143 Симплексный метод 110, 119

T -система (трансверсальная система) 309

Система троек 327 Скалярное произведение 100

Смешанная разность 321 Сопряженные разбиения 48 Сочетание 9, 11 Сравнимые элементы 90

Стирлинга числа второго рода 42

— — первого рода 42 Строго зависимое подмножество 93 Структурная матрица St 352

Тактическая конфигурация 140 Тернар 249 Тернарная операция 249

Трансверсальная система 309 Уильямсона метод 299 Уравновешенная неполная блок-

схема 140 Условие С 65, 69 Фаркаша теорема 102

Ферма теорема о классах вычетов 174 Фибоначчи числа 42 Фишера неравенство 144

Формула обращения Мёбиуса 22 Ханани теорема 337 Характер 289

Характеристическая матрица блоков

350

Характеристический полином рекуррентного соотношения 35, 37

Хассе символ 159 Хассе—Минковского теорема 160 Холла системы 251 Холла Ф. теорема 65 Хорна форма 376 Центр блок-схемы 312

Центральная разрешимость блоксхем 312

Цепь 26

Цикл 128, 129

Циклическая блок-схема 168 Циклические последовательности 22 Циклическое разностное множество

168

Частично упорядоченное множество

26

Чистая разность 321 Штейнера система троек 328

—— — метод построения Мура 330 Эйлера предположение 265, 277 Эйлера теорема 131

—— обобщение см. Гуда теорема

Эйлера тождество 50 Эквивалентность матриц Адамара

283

—ортогональных таблиц 263 Экстремальная точка 96

—— выпуклого конуса 97 Якоби тождество 55