Читать онлайн «Четыре лекции по комбинаторике: Методические указания»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИСТЕТ А. С. СЕМЕНОВ ЧЕТЫРЕ ЛЕКЦИИ ПО КОМБИНАТОРИКЕ Методические указания Ульяновск 2005 3 УДК 519. 1 (076) ББК 22. 141 я 7 С30 Рецензент д-р техн. наук, профессор Семушин И. В. Одобрено секцией методических пособий научно-методического совета УлГТУ Семенов А. С. С30 Четыре лекции по комбинаторике: методические указания. – Ульяновск: УлГТУ, 2005. - 20 с. Методические указания написаны в соответствии с программами курса высшей математики для высших учебных заведений и предназначены для самостоятельной работы студентов всех форм обучения Ульяновского государственного технического университета, изучающих теорию веро- ятностей и математическую статистику. Цель пособия – познакомить чи- тателей с основными понятиями комбинаторики и методами решения комбинаторных задач. Оно может оказаться полезным лицам, занимаю- щимся математической логикой, вычислительной техникой, кибернети- кой, целочисленным программированием и т. п. Работа подготовлена на кафедре «Высшая математика». УДК 519. 1 (076) ББК 22. 141. я 7 © А. С. Семенов, 2005 © Оформление, УлГТУ, 2005 4 ЛЕКЦИЯ 1 Введение Комбинаторика или теория конечных множеств является одним из разделов математики, имеющим большое значение в связи с применением его в теории веро- ятностей, математической логике, вычислительной технике, кибернетике, целочис- ленном программировании и т. п. Цель лекций познакомить читателей с основными понятиями комбинаторики и методами решения комбинаторных задач. При составлении лекций использовалась следующая литература 1. Виленкин Н. Я. Комбинаторика - М. : Наука, 1979. 2. Ежов И. И. , Скороход А. В. , Ядренко М. М. Элементы комбинаторики - М. : Наука, 1977. Лекции предназначены, прежде всего, для студентов, изучающих теорию ве- роятностей. Они могут оказаться полезными и лицам, которые знакомы с определе- ниями и свойствами основных операций над множествами и занимаются комбина- торными расчетами. § 1. Принцип математической индукции Широко распространенный метод доказательства утверждений - это метод математической индукции, основанный на принципе математической индукции. До- кажем его. Теорема 1 (принцип математической индукции) Пусть имеется некоторое утверждение P (n), которое формулируется для ка- ждого натурального числа n, и пусть известно, что: 1) утверждение P (1) верно; 2) из того, что P (n) верно при n = k , следует, что P (k + 1) верно. Тогда утверждение P (n) верно для любого значения n ( ∀n ∈ N . ).