Комбинаторика

М.Холл КОМБИНАТОРИКА ИЗДАТЕЛЬСТВО «МИР» Москва 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. Выпуклые пространства. Выпуклые конусы и двойственные им пространства 8.2. Линейные неравенства 8.3. Линейное программирование. Симплексный метод Глава 9. Графические методы. Последовательности де Брёйна 9.1. Полные циклы 9.2. Теоремы о графах 9.3. Доказательство теоремы де Брёйна Глава 10. Блок-схемы 10.1. Предварительное обсуждение 10.2. Элементарные теоремы о блок-схемах 10.3. Теорема Брука — Райзера — Човла 10.4. Формулировка теоремы Хассе — Минковского. Приложения Глава 11. Разностные множества 11.1. Примеры и определения 11.2. Конечные поля 11.3. Теорема Зингера 11.4. Теорема о множителе 11.5. Разностные множества в группах общего вида 11.6. Некоторые семейства разностных множеств Глава 12. Конечные геометрии 12.1. Основания 12.2. Конечные геометрии как блок-схемы 12.3. Конечные плоскости 12.4. Некоторые типы конечных плоскостей Глава 13. Ортогональные латинские квадраты 13.1. Ортогональность и ортогональные таблицы 13.2. Основные теоремы 13.3. Построение ортогональных квадратов. 13.4. Опровержение предположения Эйлера Глава 14. Матрицы Адамара 14.1. Конструкции Пэли 14.2. Метод Уильямсона 14.3. Три новых метода Глава 15. Общие методы построения блок-схем 15.1. Методы построения 15.2. Основные определения. Теоремы Ханани 15.3. Прямые методы построения 15.4. Системы троек 15.5. Блок-схемы с k>3 Глава 16. Теоремы о пополнении и вложении 16.1. Метод Коннора 16.2. Коположительные и вполне положительные квадратичные формы 16.3. Рациональные пополнения матриц инцидентности

95 102 110 128 128 130 134 140 140 144 149 155 167 167 172 178 183 189 196 230 230 235 238 248 261 261 263 269 277 283 283 299 305 308 308 308 318 327 343 348 348 365 378

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