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

С. К. Ландо Введение в дискретную математику Электронное издание Москва Издательство МЦНМО УДК . ББК . Л Ландо С. К. Введение в дискретную математику Электронное издание М. : МЦНМО, с. ISBN - - - - В основу предлагаемой вниманию читателей книги легли за- писки семестрового курса лекций, читавшегося автором в течение нескольких лет первокурсникам факультета математики Высшей школы экономики. В курс включены начальные сведения о перечис- лительных задачах, о графах и их инвариантах, о конечных автома- тах. Автор стремился связать изучаемый материал с тем, который излагается при изучении других предметов – – в первую очередь, ал- гебры и математического анализа. В книге содержится большое количество задач, многие из ко- торых снабжены решениями. Книга предназначена для студентов, изучающих математику и информатику, и преподавателей этих же предметов. Подготовлено на основе книги: С. К. Ландо. Введение в дискретную математику. – – М. : МЦНМО, . К. , . © МЦНМО, . Оглавление Отавтора... ... ... ... ... ... ... ... ... ... ... ... ... . Часть I Элементы перечислительной комбинаторики Глава . Элементарные производящие функции §1. 1. Перестановкиисочетания... ... ... ... ... ... ... ... 11 §1. 2. БиномНьютона... ... ... ... ... ... ... ... ... ... . 14 §1. 3. Экспонента... ... ... ... ... ... ... ... ... ... ... . 15 §1. 4. Производящиефункцииидействия надними . . . . . . . . . . . 18 § 1. 5. Дифференцирование и интегрирование производящих функций 22 § 1. 6. Алгебра и топология формальных степенных рядов . . . . . . . 25 §1. 7. Задачи... ... ... ... ... ... ... ... ... ... ... ... . 26 Глава . Рациональные производящие функции §2. 1. Геометрическаяпрогрессия... ... ... ... ... ... ... . . 30 §2. 2. ПоследовательностьФибоначчи... ... ... ... ... ... . . 31 § 2. 3. Рекуррентные соотношения и рациональные производящие функции... ... ... ... ... ... ... ... ... ... ... ... ... . 33 § 2. 4. Неоднородные рекуррентные соотношения . . . . . . . . . . . . . 36 § 2. 5. Произведение Адамара рациональных производящих функций 38 § 2. 6. Асимптотика коэффициентов рациональных функций . . . . . . 40 §2. 7. Задачи... ... ... ... ... ... ... ... ... ... ... ... . 42 Глава . Перечисление путей на графах §3. 1. Путивграфах... ... ... ... ... ... ... ... ... ... . . 48 § 3. 2. Пути, перечисляемые рациональными производящими функ- циями... ... ... ... ... ... ... ... ... ... ... ... ... . . 49 §3. 3. ЧислаКаталана... ... ... ... ... ... ... ... ... ... . 52 §3. 4. Задачи... ... ... ... ... ... ... ... ... ... ... ... . 57 Глава . Производящие функции нескольких переменных §4. 1. ТреугольникПаскаля... ... ... ... ... ... ... ... ... 60 § 4. 2. Экспоненциальные производящие функции . . . . . . . . . . . . 62 §4. 3. ТреугольникДика... ... ... ... ... ... ... ... ... . . 63 § 4. 4. Треугольник Бернулли– –Эйлера и перечисление up-down-пе- рестановок... ... ... ... ... ... ... ... ... ... ... ... . . 64 § 4. 5. Числа Эйлера в треугольнике Дика с кратностями . . . . . . . . 69 Оглавление § 4. 6. Производящая функция для треугольника Дика с кратностями 71 §4. 7. Задачи... ... ... ... ... ... ... ... ... ... ... ... . 72 Глава .