В книге известного западногерманского математика нашли отражение два направления современного комбинаторного анализа — теория перечисления и теория упорядоченных структур. Она написана ясно и четко, содержит много примеров и упражнений.
Для математиков-прикладников, специалистов по теории кодирования, синтезу схем, систематике; полезна студентам, специализирующимся по прикладной математике.
Author(s): Айгнер М.
Publisher: М.: Мир
Year: 1982
Language: Russian
Pages: 558
Предисловие редактора перевода ......Page 6
Предисловие ......Page 9
Предварительные сведения ......Page 12
1. Классы отображений ......Page 17
A. Классификация ......Page 18
B. Представление ......Page 19
Упражнения 1.1 ......Page 21
A. Включение ......Page 22
B. Уточнение (измельчение) ......Page 25
C. Монотонность ......Page 30
Упражнения 1.2 ......Page 33
3. Подстановки ......Page 34
A. Алгебраические свойства ......Page 35
B. Комбинаторные свойства ......Page 37
Упражнения 1.3 ......Page 40
4. Модели ......Page 41
Упражнения 1.4 ......Page 43
Замечания ......Page 44
Гл. II. Решетки ......Page 46
A. Представление в виде решетки идеалов ......Page 47
B. Произведение цепей и кодирование ......Page 52
C. Ранговая функция ......Page 55
Упражнения II.1 ......Page 58
A. Модулярные решетки ......Page 61
B. Полумодулярные решетки ......Page 65
Упражнения II.2 ......Page 69
A. Геометрические решетки и матроиды ......Page 71
B. Дополнительность ......Page 77
С. Неразложимые геометрические решетки ......Page 83
Упражнения П.З ......Page 89
4. Фундаментальные примеры ......Page 90
B. Решетка делителей ......Page 91
D. Решетки векторных пространств ......Page 92
E. Решетки разбиений ......Page 93
Замечания ......Page 95
A. Число всех отображений и всех инъективных отображений : N—*R ......Page 97
B. Число я-подмножеств и г-мультимножеств на множестве R ......Page 98
C. Число ^-подпространств я-мерного векторного пространства ......Page 102
D. Число сюръективных отображений /: N —> R и г-разбиений множества W ......Page 103
E. Число r-разбиений и упорядоченных r-разбиений числа п ......Page 105
F. Число распределений ......Page 106
G. Резюме ......Page 107
Упражнения III.1 ......Page 108
A. Элементарные производящие функции ......Page 110
B. Рекуррентность ......Page 114
C. Обращение последовательностей ......Page 120
Упражнения III.2 ......Page 122
A. Нормализованные последовательности и дифференциальные операторы ......Page 125
B. Операторы, перестановочные со сдвигами ......Page 132
C. Коэффициенты связи ......Page 137
Упражнения II 1.3 ......Page 143
A. Порядковый многочлен ......Page 145
B. Стандартные таблицы ......Page 154
Упражнения III.4 ......Page 162
Замечания ......Page 165
Гл. IV. Функции инцидентности ......Page 166
A. Определение и структура ......Page 167
B. Важные функции инцидентности ......Page 170
С. Мультипликативные функции ......Page 176
Упражнения IV.1 ......Page 180
2. Обращение Мёбиуса ......Page 182
A. Разностные операторы ......Page 183
B. Формулы решета ......Page 187
C. Некоторые приложения ......Page 192
Упражнения IV.2 ......Page 195
3. Функции Мёбиуса ......Page 198
A. Замыкание ......Page 199
B. Соответствие Галуа ......Page 204
C. Характеристический многочлен ......Page 210
Упражнения IV.3 ......Page 212
A. Алгебра Мёбиуса ......Page 215
B. Кольцо нормирований ......Page 222
C. Характеристика ......Page 227
Упражнения IV.4 ......Page 229
Гл. V. Производящие функции ......Page 231
A. Редуцированные алгебры ......Page 233
B. Фундаментальные ряды ......Page 236
C. Решетки разбиений ......Page 241
Упражнения V.1 ......Page 247
A. Взвешенные структуры ......Page 249
B. Приложения к графам ......Page 254
Упражнения V.2 ......Page 257
3. G-модели ......Page 259
A. Проблема ......Page 260
B. Главная теорема ......Page 261
C. Замкнутые множества и цикловой индекс ......Page 266
Упражнения V.3 ......Page 273
A. Инвариантность моделей относительно подстановок ......Page 275
B. Главная теорема ......Page 277
C. Приложения ......Page 282
Упражнения V.4 ......Page 292
Замечания ......Page 294
Гл. VI. Матроиды. Введение ......Page 295
A. Определение и примеры ......Page 296
B. Независимые и порождающие множества ......Page 301
С. Ранговая функция и полумодулярные функции ......Page 308
Упражнения VI.1 ......Page 312
A. Линейные матроиды и пространства функций ......Page 314
B. Графы ......Page 318
C. Трансверсальные матроиды ......Page 321
D. Геометрии инцидентности ......Page 327
Упражнения VI .2 ......Page 330
3. Построение матроидов ......Page 331
A. Ограничение и сжатие ......Page 332
B. Произведение и сумма ......Page 338
C. Расширение матроидов ......Page 343
D. Усечение ......Page 346
Упражнения VI.3 ......Page 352
A. Двойственность ......Page 356
B. Примеры ......Page 361
C. Связность ......Page 366
Упражнения VI.4 ......Page 371
Замечания ......Page 373
1. Линейные матроиды ......Page 374
A. Теоремы координатияации ......Page 375
B. Геометрические конфигурации ......Page 381
C. Критическая проблема ......Page 384
Упражнения VII.1 ......Page 388
A. Характеризация бинарных матроидов ......Page 391
B. Регулярные матроиды ......Page 398
Упражнения VI1.2 ......Page 406
A. Связность и вложение ......Page 408
B. Гомология и сети ......Page 415
C. Раскраски ......Page 425
Упражнения VII.3 ......Page 433
4. Трансверсальные матроиды ......Page 436
A. Характеризация ......Page 437
B. Гаммоиды ......Page 441
C. Последовательно-параллельные сети ......Page 445
Упражнения VI1.4 ......Page 449
Замечания ......Page 451
1. Максиминные теоремы ......Page 452
А. Теоремы о графах ......Page 453
B. Теоремы о паросочетаниях ......Page 457
C. Теоремы кодирования ......Page 460
Упражнения VIИЛ ......Page 465
A. Системы множеств и трансверсали ......Page 467
B. Принцип выбора Радо ......Page 472
C. Приложения ......Page 476
Упражнения VIII.2 ......Page 482
3. Теоремы Шпернера ......Page 485
A. Свойство Шпернера ......Page 488
B. Паросочетательное свойство и унимодулярность ......Page 492
C. Симметрические частично упорядоченные множества ......Page 500
Упражнения VIII.3 ......Page 505
4. Теоремы Рамсея ......Page 509
A. Теорема Рамсея для булевых алгебр ......Page 510
B. Некоторые приложения ......Page 514
C. Дальнейшие результаты ......Page 517
Упражнения VIII.4 ......Page 520
Замечания ......Page 522
Библиография ......Page 523
Предметный указатель ......Page 545
