Введение в дискретную математику, Ландо С.К., 2014

Введение в дискретную математику, Ландо С.К., 2014.

  В основу предлагаемой вниманию читателей книги легли записки семестрового курса лекций, читавшегося автором в течение нескольких лет первокурсникам факультета математики Высшей школы экономики. В курс включены начальные сведения о перечислительных задачах, о графах и их инвариантах, о конечных автоматах. Автор стремился связать изучаемый материал с тем, который излагается при изучении других предметов — в первую очередь, алгебры и математического анализа.
В книге содержится большое количество задач, многие из которых снабжены решениями. Книга предназначена для студентов, изучающих математику и информатику, и преподавателей этих же предметов.




Элементарные производящие функции.
В первой части курса мы займемся задачами перечисления. Они заключаются в подсчете числа объектов, принадлежащих некоторому семейству конечных множеств. У каждого множества семейства имеется свой номер, и результатом перечисления служит некоторая последовательность натуральных чисел. Перечислительные задачи встречаются во всех областях математики, и в последние годы они вышли на первый план в алгебраической геометрии, топологии, многих направлениях математической физики.

Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема, однако, состоит в том, чтобы найти «хорошее» решение, не требующее выписывания всех элементов изучаемых множеств. При этом понять, что такое хорошее решение, довольно трудно. Зачастую удается лишь сравнить два решения и сказать, какое из них лучше.

Наиболее подходящим языком для решения перечислительных задач оказывается язык производящих рядов. Операции с комбинаторными объектами очень естественно выражаются в терминах производящих функций. Однако перечислительная комбинаторика не сводится к производящим функциям — привлечение методов из смежных областей математики (например, из анализа или теории групп) дает новый взгляд на перечислительные задачи и позволяет находить неожиданные подходы к их решению.

Оглавление
От автора
Часть I Элементы перечислительной комбинаторики
Глава 1. Элементарные производящие функции
§1.1. Перестановки и сочетания
§1.2. Бином Ньютона
§1.3. Экспонента
§1.4. Производящие функции и действия над ними
§1.5. Дифференцирование и интегрирование производящих функций
§1.6. Алгебра и топология формальных степенных рядов
§1.7. Задачи
Глава 2. Рациональные производящие функции
§2.1. Геометрическая прогрессия
§2.2. Последовательность Фибоначчи
§2.3. Рекуррентные соотношения и рациональные производящие функции  
§2.4. Неоднородные рекуррентные соотношения
§2.5. Произведение Адамара рациональных производящих функций
§2.6. Асимптотика коэффициентов рациональных функций
§2.7. Задачи
Глава 3. Перечисление путей на графах
§3.1. Пути в графах
§3.2. Пути, перечисляемые рациональными производящими функциями  
§3.3. Числа Каталана
§3.4. Задачи
Глава 4. Производящие функции нескольких переменных
§4.1. Треугольник Паскаля
§4.2. Экспоненциальные производящие функции  
§4.3. Треугольник Дика
§4.4. Треугольник Бернулли—Эйлера и перечисление up-down-перестановок  
§4.5. Числа Эйлера в треугольнике Дика с кратностями
§4.6. Производящая функция для треугольника Дика с кратностями
§4.7. Задачи
Глава 5. Теневое исчисление
§5.1. Определения и примеры
§5.2. Применения биномиальных последовательностей
§5.3. Биномиальные последовательности и сдвиги  
§5.4. Явное построение биномиальных последовательностей
§5.5. Последовательности Шеффера
§5.6. Коалгебра многочленов
§5.7. Задачи
Глава 6. Разбиения
§6.1. Разбиения и разложения
§6.2. Тождество Эйлера
§6.3. Разбиения множеств в треугольнике Моцкина с кратностями
§6.4. Задачи
Глава 7. Производящие функции Дирихле
§7.1. Принцип включения-исключения
§7.2. Производящие функции Дирихле и действия над ними
§7.3. Обращение Мобиуса
§7.4. Мультипликативные последовательности
§7.5. Задачи
Часть II Графы, их перечисление и инварианты
Глава 8. Перечисление деревьев и лесов
§8.1. Перечисление помеченных деревьев
§8.2. Леса и многочлены Абеля
§8.3. Перечисление посаженных лесов  
§8.4. Обращение функции и суммирование по деревьям
§8.5. Задачи
Глава 9. Числа Гурвица
§9.1. Графы и перестановки  
§9.2. Числа Гурвица
§9.3. Уравнение транспозиции
§9.4. Задачи
Глава 10. Соотношение удаление-стягивание и теорема Татта
§10.1. Графы, изоморфизм и инварианты  
§10.2. Хроматический многочлен
§10.3. Немного о топологии графа
§10.4. Многочлен Пенроуза
§10.5. Соотношения Татта
§10.6. Теорема Татта
§10.7. Доказательство теоремы Татта
§10.8. Новые примеры инвариантов Татта
§10.9. Задачи
Глава 11. Алгебра Хопфа графов
§11.1. Алгебра Хопфа графов
§11.2. Примитивные элементы  
§11.3. Факторалгебры биалгебры графов
§11.4. 4-инварианты
§11.5. Оснащенные модификации графовых алгебр
§11.6. Задачи
Часть III Языки, грамматики, автоматы
Глава 12. Языки и конечные автоматы
§12.1. Язык Дика
§12.2. Конечные автоматы
§12.3. Автоматы со стеком
§12.4. Задачи
Глава 13. Языки и формальные грамматики с однозначным выводом
§13.1. Правила вывода в языке Дика
§13.2. Формальные грамматики с однозначным выводом
§13.3. Производящие функции регулярных языков  
§13.4. Представления производящих функций в виде непрерывных дробей  
§13.5. Сравнения в последовательностях
§13.6. Задачи
Ответы, указания, решения
Решения задач главы 1  
Решения задач главы 2
Решения задач главы 3
Решения задач главы 4
Решения задач главы 5
Решения задач главы 6
Решения задач главы 7
Решения задач главы 8
Решения задач главы 9
Решения задач главы 10
Решения задач главы 11
Решения задач главы 12
Решения задач главы 13
Контрольные задания
Задачи зачета
Домашняя работа
Задачи экзамена
Библиографические замечания  
Литература  
Предметный указатель.

Купить .





Теги: учебник по математике :: математика :: Ландо