«Комбинаторика» М. Холл
.pdfМ.Холл
КОМБИНАТОРИКА
ИЗДАТЕЛЬСТВО «МИР» Москва 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