Читать онлайн «Лекции по дискретной математике»

Лекции по дискретной математике М. Вялый В. Подольский А. Рубцов Д. Шварц А. Шень Оглавление Предисловие 8 I Начальные примеры 10 1 Математическая индукция 11 1. 1 Задача о раскраске плоскости . . . . . . . . . . . . . . . . . . . . . . . . 11 1. 2 Общая схема доказательств по индукции . . . . . . . . . . . . . . . . . 15 1. 3 Варианты рассуждений по индукции . . . . . . . . . . . . . . . . . . . . 16 1. 3. 1 С чего начинать? . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1. 3. 2 Сведение к меньшим . . . . . . . . . . . . . . . . . . . . . . . . . 18 1. 3. 3 Переформулировка: принцип наименьшего числа . . . . . . . . . 19 1. 4 Как не надо . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1. 5 Как догадаться, что доказывать? . . . . . . . . . . . . . . . . . . . . . . 22 1. 6 Доказательства по индукции и без . . . . . . . . . . . . . . . . . . . . . 25 1. 7 Индукция и рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1. 8 Доказательства неравенств по индукции . . . . . . . . . . . . . . . . . . 31 1. 8. 1 Неравенство Бернулли . . . . . . . . . . . . . . . . . . . . . . . . 31 1. 8. 2 Среднее арифметическое и геометрическое . . . . . . . . . . . . 32 1. 9 Пример из алгебры: системы однородных уравнений . . . . . . . . . . . 35 1. 10 Коды Грея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1. 11 Теорема Холла о представителях . . . . . . . . . . . . . . . . . . . . . . 40 1. 12 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . 42 2 Подсчёты 44 2. 1 Правило суммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2. 2 Рекуррентное соотношение: пример . . . . . . . . . . . . . . . . . . . . . 48 2. 3 Рекуррентное соотношение: число путей . . . . . . . . . . . . . . . . . . 51 2. 4 Слова и правило произведения . . . . . . . . . . . . . . . . . . . . . . . 53 2. 5 Выбор с ограничениями . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2. 6 Подсчёты с кратностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2. 7 Подмножества и числа сочетаний . . . . . . . . . . . . . . . . . . . . . . 61 2. 8 Ещё о числах сочетаний . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 1 Оглавление 2 2. 8. 1 Симметрия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2. 8. 2 Сумма чисел в строке . . . . . . . . . . . . . . . . . . . . . . . . . 64 2. 8. 3 Знакочередующаяся сумма . . . . . . . . . . . . . . . . . . . . . . 65 2. 8. 4 Снова о включениях и исключениях . . . . . . . . . . . . . . . . 66 2. 8. 5 Пути, подмножества, слова . . . . . . . . . . . . . . . . . . . . . 67 2. 8. 6 Соседние числа в строке . . . . . . . . . . . . . . . . . . . . . . . 69 2. 8. 7 Монеты и перегородки . . . . . . . . . . . . . . . . . . . . . . . . 70 2. 9 Бином Ньютона и производящие функции . . . . . . . . . . . . . . . . . 72 2. 10 Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2. 10. 1 Правильные последовательности скобок . . . . . . . . . . . . . . 80 2. 10. 2 Рекуррентная формула . . . . . . . . . . . . . . . . . . . . . . . . 82 2. 10. 3 Вычисление с помощью отражений . . . . . . . . . . . . . . . . . 84 2. 10. 4 Вычисление с производящей функцией . . . . . . . . . . . . . . 86 2. 10. 5 Вычисление с теорией вероятностей и поворотами . . . . . . . . 88 2. 10. 6 Доказательство по индукции с дробными параметрами . . . . . 89 2. 10. 7 Неассоциативные произведения, триангуляции и стековый калькулятор . . . . . . . . . . . . . . . . . . . . . . . . 90 2. 11 Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3 Графы 95 3. 1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3. 1. 1 Граф авиарейсов . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3. 1. 2 Перестановка коней . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3. 1. 3 Эйлер и мосты в Кёнигсберге . . . . . . . . . . . . . . . . . . . . 98 3. 1. 4 Рукопожатия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3. 1. 5 Задачи и решения . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3. 1. 6 Разбор контрольной* . . . . . . . . . . . . . . . . . . . . . . . . . 101 3. 1. 7 Знакомые и незнакомые . . . . . . . . . . . . . . . . . . . . . . . 103 3. 2 Неориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3. 2. 1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3. 2. 2 Соседи.