Читать онлайн «Курс лекций по дискретной математике»
Автор Лупанов О.Б.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
имени М. В. ЛОМОНОСОВА
Механико-математический факультет
Курс лекций по
дискретной математике
Лектор — Олег Борисович Лупанов
IV курс, 7 семестр, поток математиков
Москва, 2006 г. Оглавление
1. Комбинаторика и теория графов 4
1. 1. Введение в комбинаторику . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. 1. 1. Простейшие комбинаторные объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. 1. 2. Оценки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1. 2. Теория графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1. 2. 1. Графы. Правильная реализация. Критерий Понтрягина – Куратовского . . . . . . . . . . . 5
1. 2. 2. Оценки количества деревьев и графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1. 2. 3. Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.
2. 4. Двудольные графы. Критерий Холла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1. 3. Формальные степенные ряды и производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . 10
1. 3. 1. Формальные степенные ряды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1. 3. 2. Формальное дифференцирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1. 3. 3. Сходимость в пространстве формальных рядов . . . . . . . . . . . . . . . . . . . . . . . . . 13
1. 3. 4. Подсчёт количества неприводимых многочленов над Fp . . . . . . . . . . . . . . . . . . . . . 14
1. 3. 5. Формула обращения Мёбиуса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1. 3. 6. Тождества Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1. 3. 7.
