Читать онлайн «Дискретная математика. Комбинаторика: Учебное пособие»

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА. КОМБИНАТОРИКА Учебное пособие Ñàíêò-Ïåòåðáóðã 2001 УДК 512. 54 E78 ББК 22. 1 Ерош И. Л. Е78 Дискретная математика. Комбинаторика: Учеб. пособие/ СПбГУАП. СПб. , 2001. 37 c. В учебном пособии кратко изложены основные положения раздела дискретной математики «Комбинаторика». Приведено много задач для самостоятельного решения. Перед каждым набором задач разбираются примеры. В заключение приведены примеры использования комбина- торных методов в других разделах дискретной математики и в технических приложениях. Пособие ориентировано на студентов 1-го курса технических универ- ситетов, аспирантов и преподавателей дисциплины “Дискретная матема- тика”. Рецензенты: кафедра радиосистем Санкт-Петербургского электротехнического университета; кандидат технических наук доцент В. Н. Сасковец Óòâåðæäåíî ðåäàêöèîííî-èçäàòåëüñêèì ñîâåòîì óíèâåðñèòåòà â êà÷åñòâå ó÷åáíîãî ïîñîáèå © СПбГУАП, 2001 © И. Л. Ерош, 2001 2  ВВЕДЕНИЕ Комбинаторика является разделом дискретной математики, ориен- тированным на решение задач выбора и расположения элементов неко- торого множества в соответствии с заданными правилами и ограниче- ниями. Каждое такое правило определяет способ построения некоторой комбинаторной конфигурации, поэтому комбинаторный анализ (комби- наторика) занимается изучением свойств комбинаторных конфигураций, условиями их существования, алгоритмами построения и оптимизацией этих алгоритмов. Этот раздел математики тесно связан с рядом других разделов дис- кретной математики: теорией вероятностей, теорией графов, теорией чисел, теорией групп и т. д. Первые параграфы настоящего пособия посвящены элементам клас- сической комбинаторики: размещениям, перестановкам и сочетаниям. В последующих параграфах рассматриваются некоторые классы наи- более часто встречающихся задач: комбинаторные задачи с ограниче- ниями, комбинаторные задачи раскладок и разбиений, комбинаторные задачи, решаемые с помощью рекуррентных соотношений. Настоящее учебное пособие содержит большое число примеров, заимствованных из книг известного российского математика и прекрас- ного популяризатора математических идей Н. Я. Виленкина. К сожале- нию, его книги “Комбинаторика” и “Популярная комбинаторика” прак- тически невозможно найти в библиотеках технических вузов, в особен- ности в библиотеках периферийных вузов. Только это, а также потреб- ность в более сжатом изложении материала и привязки его к задачам вычислительной техники побудило автора написать это учебное посо- бие. 3  1.