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

В. Н. САЧКОВ ВВЕДЕНИЕ В КОМБИНАТОРНЫЕ МЕТОДЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 075100 Криптография и 075200 Компьютерная безопасность Москва Издательство МЦНМО 2004 УДК 519. 6 ББК 22. 176 С22 Сачков В. Н. С22 Введение в комбинаторные методы дискретной математики. — 2-е изд. , испр. и доп. —М. : МЦНМО, 2004. —424 с: ил. ISBN 5-94057-116-6 Книга содержит изложение ряда основных комбинаторных методов современной дискретной математики в систематизированном виде. Предпочтение отдается тем методам, которые носят перечислительный характер, наиболее отработаны теоретически и имеют наибольшее число приложений. Книга предназначена для студентов вузов, обучающихся по специальностям «Прикладная математика», «Кибернетика», «Криптография», «Компьютерная безопасность», а также для научных работников, работающих в области прикладной математики, кибернетики, защиты информации и криптографии. Во втором издании добавлена глава IX «Дискретные функции», добавлены разделы к некоторым другим главам, расширен круг задач. ББК 22. 176 Владимир Николаевич Сачков ВВЕДЕНИЕ В КОМБИНАТОРНЫЕ МЕТОДЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Редактор Т. Коробкова Лицензия ИД № 01335 от 24. 03. 2000 г. Подписано в печать 26. 03. 2004 г. Формат 60 х 90 */1б- Бумага офсетная. Печать офсетная. Печ. л. 26,5. Тираж 1600 экз. Заказ №9958. Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер. , 11. Тел. 241-05-00. Отпечатано с готовых диапозитивов в ППП «Типография „Наука"». 119099, Москва, Шубинский пер. , 6. ISBN 5-94057-116-6 Э^вБЭ^БУНбг1 © Сачков В. Н. , 2004 © МЦНМО, 2004 ОГЛАВЛЕНИЕ Предисловие ко второму изданию 5 Предисловие 7 Глава I. Основные понятия и элементарные методы 9 § 1. Множества 9 §2. Отображения, соответствия, функции 16 §3. Отношения, операции, алгебры 25 §4. Числа, многочлены, операторы 37 §5. Преобразования 49 § 6. Булевы функции 56 Задачи 61 Глава II. Формулы обращения и метод включения—исключения 63 § 1. Метод включения—исключения 63 §2. Неравенства Бонферрони 68 §3. Формулы обращения для частично упорядоченных множеств 72 Задачи 83 Глава III. Производящие функции 85 § 1. Формальные степенные ряды 85 §2. Производящие функции 102 §3. Метод дифференциальных уравнений 115 §4. Метод линейных функционалов 122 §5. Асимптотические разложения 136 §6. Числа Каталана 143 Задачи 150 Глава IV. Графы и преобразования 157 § 1. Графы 157 §2. Деревья 168 §3. Циклы подстановок 178 §4. Графы преобразований 189 §5. Блоки 200 Задачи 207 Глава V. Общая комбинаторная схема и теория Пойа 208 § 1. Группы и эквивалентность отображений 208 §2. Общая комбинаторная схема 215 4 ОГЛАВЛЕНИЕ §3. Коммутативный несимметричный/2-базис 218 §4. Некоммутативный несимметричный/2-базис 227 §5. Коммутативный симметричный /2-базис 234 §6. Некоммутативный симметричный/2-базис 243 § 7. Теорема Пойа 249 Задачи 258 Глава VI.