Читать онлайн «Введение в комбинаторный анализ»

;. ^г К. А. Рыбников ВВЕДЕНИЕ В КОМБИНАТОРНЫЙ АНАЛИЗ ИЗДАНИЕ ВТОРОЕ Ж ИЗДАТЕЛЬСТВО МОСКОВСКОГО УНИВЕРСИТЕТА 1985 УДК 519. 1 Рыбников К. А. Введение в комбинаторный анализ / 2-е изд. — М. : Изд-во Моск. ун-та, 1985 — 308 с. В книге (1-е издание вышло в 1972 г. ) излагаются построенные на единой теоретической основе методы исследования дискретных систем л решения соответствующих комбинаторных задач. Рассмотрены: начала теории дискретных множеств, основные комбинаторные понятия и операции, логические методы, таблично-матричный аппарат, дискретные геометрические системы, методы решения экстремальных задач и методы вероятностного характера. Содержание взаимосвязано со сборником «Комбинаторный анализ: задачи и упражнения» («Наука», 1982). Для студентов математических специальностей университетов. Рецензенты: чл. -кор. АН КазССР В. М. Амербаев, д-р физ. -мат. наук В. А. Малышев Печатается по постановлению Редакционно-издательского совета Московского университета 1702070000—082 р — 97—85 077(02)-85 © Издательство Московского университета. 1985 г. ОГЛАВЛЕНИЕ Предисловие 5 Глава 1. Теоретические основы комбинаторного анализа 6 § 1. 1. Что изучают в комбинаторном анализе н какие типы задач решают 6 § 1. 2. Необходимые сведения из теории множеств и алгебры 7 § 1. 3. Выборки и упорядочения 15 § 1. 4. Распределения и заполнения 21 § 1. 5. Системы множеств 29 Глава 2. Производящие функции 33 § 2. !. Основы метода производящих функций 33 § 2. 2. Виды производящих функций и нумераторов 36 § 2. 3. Операторный аппарат метода производящих функций 48 § 2. 4. О приложениях метода производящих функций 58 § 2. 5. Теория Редфилда—Пона 62 Глава 3. Комбинаторно-логический аппарат 69 § З. 1. . МР. ТПЛ ИК. ЛЮИГНИЙ И ■к-Ушпчпчий 69 § 3. 2. Системы представителей множеств 73 § 3. 3. Начала теории Рамсея 77 Глава 4. Табличио-матричный аппарат комбинаторного анализа 82 § 4. 1. Системы инцидентности и специальные матрицы 82 § 4. 2. Латинские прямоугольники и квадраты 88 § 4. 3; Блок-сдамы— -ЗЬ... § 4. 4* Перманенты 106 Глава 5. Геометрические системы 123 § 5. 1. Геометрические интерпретации 123 § 5. 2. О проективных пространствах 125 § 5. 3. Конечные проективные плоскости 128 § 5. 4. Графы 135 Глава 6. Методы решения экстремальных задач 150 § 6. 1. Экстремальные комбинаторные задачи и подходы к их решению 150 § 6. 2. Метод ветвлений и ограничений 156 § о. З. Эвристические методы 164 § 6. 4. Оптимизация иа графах 170 § 6. 5. Потоки в сетях 174 Глава 7. Вероятностные методы в комбинаторном анализе 183 § 7. 1. Примеры применения вероятностных методов 183 § 7. 2. Задачи планирования эксперимента 186 § 7. 3. Энтропийный метод 191 § 7. 4. Метод случайного баланса 195 § 7. 5. Разделяющие системы подмножеств 201 3 Глава 8. Комбинаторный анализ на частично упорядоченных множествах 208 § 8. 1. Частично упорядоченные множества 208 § 8. 2. Решетки 228 § 8. 3. Функции инцидентности и обращение Мебиуса 248 § 8. 4. Матроиды 270 Заключение 303 Литература 304 ПРЕДИСЛОВИЕ В учебных планах математических и других специальностей высших учебных заведений, во всей практике их учебно-научной деятельности возрастает роль тех математических дисциплин, в которых изучают дискретные системы.