Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
ЧАСТЬ II. КОМБИНАТОРИКА 2.1. Основные определения комбинаторного анализа Бытуетмнение, что комбинаторные задачи элементарны. Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что, несмотря на заманчивую простоту постановки, комбинаторные задачи в большинстве очень трудны; многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся: 1) задачи на размещения. Это задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия; 2) задачи о покрытиях и заполнениях. Это задачи, например, о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров; 3) задачи о маршрутах. К ним относятся задачи на отыскание кратчайшего пути и тому подобное. Это задачи оптимального плана; 4) комбинаторные задачи теории графов. Это задачи сетевого планирования, например, задачи транспортных и электрических сетей, задачи об окрашивании графов, задачи о перечислении вершин и тому подобные задачи; 5) перечислительные задачи. В таких задачах речь идет о числе предметов, составляемых из данного набора элементов при соблюдении определенных правил. В задачах комбинаторного анализа исследуются дискретные множества, то есть множества, составленные из отдельных обособленных элементов. В большинстве случаев эти множества конечные, но не исключается и рассмотрение множеств, состоящих из бесконечного числа элементов. Особенностью комбинаторных задач является то, что в них преимущественное внимание уделяется двум видам операций: отбору подмножеств и упорядочению элементов. Эти две операции и являются основными комбинаторными. Стефан Банах (1892 – 1945) – польский математик. Альфред Тарский (1902 – 1983) – польский математик. 19 С операцией отбора множеств связано понятие выборки. С этим понятием можно связать как осуществление операции отбора, так и ее результат - само выбранное подмножество. Подмножество из r элементов, выбранное из множества n S , состоящего из n элементов, называется r n, - выборкой, а r - объемом этой выборки. Если r n, - выборки рассматриваются с учетом порядка элементов в них, то они называются r n, - перестановками. Если же порядок элементов в выбранных подмножествах не важен, то соответствующие выборки называются r n, - сочетаниями. В выборках могут допускаться и не допускаться повторения элементов. Упорядоченная r n, - выборка, в которой элементы могут повторяться, называется перестановкой с повторениями из n элементов по r или r n, - перестановкой с повторениями. Если элементы упорядоченной r n, - выборки попарно различны, то она называется r n, - перестановкой без повторений. Число r n, - перестановок обозначается символом r n P , или r n P , , а число перестановок с повторениями r n P , ˆ или r n P , ˆ P - первая буква французского слова Permutation - перестановка. До сих пор во многих учебниках r n, - перестановки называются размещениями и обозначаются символом r n A , собственно же перестановками называются упорядоченные n n, - выборки. A - первая буква французского слова Arrangement - размещение, приведение в порядок. Неупорядоченная r n, - выборка, в которой элементы могут повторяться, называется сочетанием с повторениями из n элементов по r Число сочетаний без повторений обозначается символами r n C r n C r n , , , , с повторениями r n C , ˆ или r n Cˆ . C - первая буква французского слова Combination - сочетание. Наиболее употребительным является обозначение r n C . Символ r n называется символом Аппеля Пример 1. Пусть 2. , , , r c b a A Указать все упорядоченные и неупорядоченные выборки с повторениями и без повторений из трех элементов по два. 1) cc cb ca bc bb ba ac ab aa , , , , , , , , - девять перестановок с повторениями, 9 ˆ 2 , 3 P 2) cb ca bc ba ac ab , , , , , - шесть перестановок без повторений, 6 2 , 3 P 3) bc ac ab , , - три сочетания без повторений, 3 2 3 C 4) cc bc bb ac ab aa , , , , , - шесть сочетаний с повторениями, 6 ˆ 2 3 C 2.2. Правило суммы и правило произведения Основной комбинаторной задачей является подсчет числа r n, - выборокпри различных условиях. Опыт выполнения комбинаторных операций отбора подмножеств привел к следующим двум логическим правилам. 1)Правило суммы. Если из множества S подмножество A (которое может состоять и из одного элемента) можно выбрать n способами, а подмножество B , отличное от A , m способами, и при этом выборы A и B таковы, что взаимно исключают друг друга и не могут быть получены одновременно, то выбор из множества S множества B A можно получить m n способами. Поль Эмиль Аппель (1855 - 1930) - французский математик. 20 Прокомментируем это правило подробнее. Если B A , то A и B называются непересекающимися множествами, в частности, если j i A A при всех , , ,..., 2 , 1 , j i r j i то r A A A S 2 1 называется разбиением множества S на непересекающиеся подмножества или просто разбиением. Правило суммы можно сформулировать и в терминах теории множеств: если даны n - множество A и m - множество B , то при B A объединение B A будет m n - множеством. Если дано разбиение r A A A S 2 1 , где J i A A , j i r j i , ,..., 2 , 1 , и если i A есть i n - множество r i ,..., 2 , 1 , то множество S есть r i i n 1 - множество. 2) Правило произведения. Если из множества S подмножество A может быть выбрано n способами, а после каждого такого выбора подмножество B можно выбрать m способами, то выбор A и B в указанном порядке можно осуществить m n способами. В терминах теории множеств это правило соответствует понятию декартова произведения множеств: если A является n -множеством, а B m - множеством, то B A окажется m n - множеством. Пусть i A суть i n - множества, r i ,..., 2 , 1 . Построим множества: , 1 1 A M ,..., , 1 3 2 3 2 1 2 1 2 r r r A M M A M M A M A A M Тогда r M будет r n n n 2 1 множеством. При решении практических задач правило произведения часто употребляется при подсчете числа вариантов при проведении r n, - выборок. В этом случае его формулировка может выглядеть, например, так. 2а) Правило произведения. Пусть требуется выполнить одно за другим r действий. Если первое действие можно выполнить 1 n способами, второе действие - 2 n способами и так до r -го действия, которое можно выполнить r n способами, то все r действий вместе могут быть выполнены r n n n 2 1 способами. Пример 1. В классе изучают 10 предметов. В понедельник шесть уроков, причем все уроки различные. Сколькими способами можно составить расписание на понедельник? Речь в задаче идет о 6 - перестановках без повторения из 10 элементов. Первый урок можно поставить в расписание десятью способами, второй девятью, третий - восемью и так далее. По правилу произведения число способов составления расписания будет равно 151200 5 6 7 8 9 10 6 10 A Пример 2. Сколько имеется пятизначных чисел, которые делятся на пять? Вспомним признаки делимости. Число делится на пять, если оно оканчивается на нуль или на пять. В задаче речь идет о r n, - перестановках с повторениями. Первая цифра может быть выбрана из множества 1,2,3,4,5,6,7,8,9. Нуль не может участвовать в выборке, ибо при его выборе число будет четырехзначным, а не пятизначным. Итого, девять вариантов выбора для первой цифры. Вторая, третья и четвертая цифры могут быть любыми из набора 0,1,2,3,4,5,6,7,8,9. Последняя пятая цифра выбирается только из 0 и 5. Таким образом, 18000 2 10 10 10 9 N 2.3. Формулы для расчета перестановок и сочетаний без повторений и с повторениями Найдем сначала число всех возможных r n, - перестановок, то есть размещений. Задача сводится к последовательному применению правила произведения. В самом деле, в n - множестве n S имеется n возможностей для выбора первого элемента r n, - перестановки; для выбора второго элемента останется 1 n возможностей, так как речь сейчас идет о перестановках без повторения, то есть один раз выбранный элемент уже не участвует в 21 дальнейшей выборке. Аналогично рассуждая, получим, что для выбора r -го элемента останется 1 r n возможностей. Тогда ! ! 1 2 1 r n n r n n n n A r n (2.3.1) Действительно, 1 1 3 2 1 1 1 3 2 1 ! ! n n r n r n n n r n r n r n n Здесь принято 1 ! 1 ! 0 Итак, доказана следующая теорема Теорема 2.1. Число упорядоченных r - элементных подмножеств множества n S , состоящего из n элементов равно ! ! r n n A r n В частном случае, когда r n , получаем ! ! 0 ! , n n P P A n n n n n Это число способов упорядочения n - элементного подмножества. Подсчитаем теперь число всех возможных r n, - перестановок с повторениями. В этом случае после выбора любого элемента r n, - перестановки остаются все те же n возможностей для выбора следующего элемента. Следовательно, по правилу произведения число r n, - перестановок с повторениями равно: ˆ раз r r r n n n n n A (2.3.2) Подсчитаем теперь число r n, - сочетаний. Пусть имеется ряд неупорядоченных r n, - выборок без повторения элементов. Обозначим количество элементов множества, состоящего из всех возможных r n, - сочетаний через r n C Сравним числа r n C и r n A r n A - число упорядоченных выборок из n элементов по r ; r n C - число неупорядоченных выборок из n элементов по r . Очевидно, что каждую неупорядоченную выборку объема r можно упорядочить ! r различными способами, то есть ! r n r n A C r Тогда ! ! ! ! r n r n r A C r n r n (2.3.3) Полученный результат формулируется в виде теоремы. Теорема 2.2. Число всех неупорядоченных r - элементных подмножеств множества n S , состоящего из n элементов равно ! ! ! r n r n C r n Рассмотримболее сложную задачу о числе k r r r ,..., , 2 1 - разбиений n - множества n S , то есть разбиений вида j i k n A A A A A S , 2 1 , , ,..., 2 , 1 , , k j i j i причем i A есть i r - подмножество множества n S . Очевидно, k i i n r 1 Рассуждаем аналогично тому, как это делалось при нахождении числа r n A . Для выбора 1 r - подмножества 1 A из n S имеется 1 r n C возможностей, после этого 2 r - подмножество 2 A можно выбирать только из оставшихся 1 r n элементов, так как 2 1 A A . Этот выбор можно осуществить 2 1 r r n C способами и так далее. Применяя правило произведения, получим, что искомое число k r r r ,..., , 2 1 - разбиений n - множества n S равно ! !... ! ! 2 1 1 1 3 2 1 2 1 1 k r r n r r r n r r n r n r r r n C C C C k k i i (2.3.4) Действительно, ! !... ! ! ! ! ! ! ! ! ! ! 2 1 2 1 1 2 1 2 1 2 1 1 1 k k k k r r r n r r r n r r r r n r r n r r n r n r n |