Конспект лекций. Оглавление
 Скачать 1.11 Mb.
|
|
Доля П.Г. Харьковский Национальный Университет механико – математический факультет кафедра геометрии им. А.В. Погорелова Дискретная математика. Конспект лекций. Оглавление 6. Комбинаторика. 6.1 Основные комбинаторные принципы. 1 6.2 Модельные схемы .......................................................................................... 7 6.3 Бином Ньютона ............................................................................................ 17 6.4 Принцип включений – исключений. 21 6.5 Метод рекуррентных соотношений .......................................................... Упражнения. Комбинаторика представляет собой раздел математики, изучающий способы подсчета количества элементов конечных множеств. 6.1 Основные комбинаторные принципы Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых правилами суммы и произведения. Правило суммы. Если X 1 и X 2 – непересекающиеся конечные множества, содержащие n 1 и n 2 элементов соответственно, то объединение содержит n 1 + n 2 элементов. 2 1 X X Сформулированное правило можно распространить на случай произвольного числа слагаемых если множества X 1 ,X 2 ,…,X k образуют разбиение множества X, то n = n 1 + n 2 +…+ n k , где n=|X| – число элементов множества X, а n i =|X i | – число элементов (мощность) множества X i , i = 1, 2,…, k. Напомним, что разбиением множества X называется набор его непересекающихся подмножеств, объединение которых дает все исходное множество X. Правило суммы можно приспособить и для подсчета числа элементов объединения двух множеств с непустым пересечением (1) В самом деле, множества X 1 \X 2 и X 1 ∩X 2 образуют разбиение множества X 1 , поэтому 1 Аналогично Кроме того, множества X 1 \X 2 , X 2 \X 1 и X 1 ∩X 2 образуют разбиение множества X 1 U X 2 , так что Подставляя сюда выражения 1 1 1 2 1 \ X X X X X I − = , и 1 1 2 1 2 \ X X X X X I − = , приходим к утверждению (1). Пример. Найдем количество положительных целых чисел, меньше или раных 1000, которые делятся на 3 или на 5. Количество элементов множества S положительных целых чисел, меньших 1000, которые делятся на 3, равно ⎥⎦ ⎤ ⎢⎣ ⎡ 3 1000 или 333. Количество элементов множества Т положительных целых чисел, меньших 1000, которые делятся на 5, равно ⎥⎦ ⎤ ⎢⎣ ⎡ 5 1000 или 200. Элементами множества S∩T являются целые числа, меньшие 1000, которые делятся на 5 и на 3, и поэтому делятся на 15. Следовательно, 66 15 1000 = ⎥⎦ ⎤ ⎢⎣ ⎡ = T S I . Значит 467 66 200 Пример. Предположим, что на курсе из 100 студентов 60 человек изучают математику, 75 — историю, а 45 человек — и то, и другое. а) Сколько студентов изучают математику или историю Пусть универсум U — группа из 100 студентов, М — множество студентов, изучающих математику, Н — множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю, равно 90 45 75 б) Сколько студентов не изучают ни математику, ни историю Количество студентов, не изучающих ни математику, ни историю, равно H M I . Но H M H M U I = , поэтому 10 90 Существует альтернативный метод решения приведенных выше задачи, который является более информативным. Рассмотрим его наследующем примере. Пример. Предположим, что из 100 студентов курса 50 изучают химию, 53 — математику, 42 — физику, 15 — химию и физику, 20 занимаются физикой 2 и математикой, 25 — математикой и химией и 5 студентов изучают все три предмета. а) Сколько студентов изучают хотя бы один из трех перечисленных предметов б) Сколько студентов не изучают ни один из трех перечисленных предметов в) Сколько студентов изучают только математику г) Сколько студентов изучают физику или химию, ноне изучают математику д) Сколько студентов не изучают ни математику, ни химию Поскольку 5 человек изучают все три предмета, а 15 человек — химию и физику, остаются 10 человек, изучающих химию и физику, ноне изучающих математику. Аналогично, 25 — 5 = 20 человек занимаются математикой и химией, ноне физикой, и 20 — 5 = 15 человек изучают математику и физику, ноне изучают химию. Данную ситуацию изображает диаграмма Эйлера, приведенная наследующем рисунке слева Поскольку 50 студентов изучают химию и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой и 40 из них уже учтены. Поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику. а) Суммируя количество людей, принадлежащих семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов. б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 100- 90 = 10 человек не изучают ни один из этих трех предметов. в) Из диаграммы Эйлера следует, что 13 человек изучают только математику. г) Тридцать семь студентов занимаются химией или физикой, ноне изучают математику. д) Из диаграммы Эйлера, изображенной на предыдущем рисунке справа, следует, что 75 человек изучают математику или физику. Поэтому 100 — 75 = 25 студентов не изучают ни математику, ни физику. Пример. Сколько имеется путей из вершины a в вершину b в сети, показанной наследующем рисунке (движение возможно только вправо или вверх 3 Обозначим множество всех путей изв через L ab и разобьем его на два непересекающихся подмножества L acb – пути, проходящие через вершину c; L adb – пути, проходящие через вершину d. Имеем adb acb ab L L L + = . Очевидно, что интересующее нас количество путей зависит только от размеров решетки, поэтому обозначим через l m,n количество путей в сети, имеющей m горизонтальных и n вертикальных вершин. Тогда последнее равенство можно записать в виде 4 , 4 5 , 3 5 , 4 l l l + = . И вообще, . Пользуясь этим соотношением, подсчитаем количество путей на рисунке 1 , , 1 , − − + = n m n m n m l l l ( ) ( ) = ⋅ + = + + + = + = 4 , 3 5 , 2 3 , 4 4 , 3 4 , 3 5 , 2 4 , 4 5 , 3 5 , 4 3 l l l l l l l l l ( ) ( ) = ⋅ + ⋅ + = + + + = 3 , 3 4 , 2 5 , 1 3 , 3 4 , 2 4 , 2 5 , 1 3 4 3 l l l l l l l ( ) ( ) = + + = + + + + = 3 , 2 4 , 1 5 , 1 2 , 3 3 , 2 3 , 2 4 , 1 5 , 1 10 4 3 4 l l l l l l l l 35 3 10 поскольку , 1 5 , 1 = l 3 , 1 3 , 2 4 , 1 = = Другое фундаментальное правило дает, доказанная ранее Теорема. Мощность декартового произведения двух конечных множеств равна произведению их мощностей Обобщение ее на декартово произведение n множеств называется правилом произведения. Рассмотрим упорядоченные наборы (a 1 , a 2 ,…, a k ) заданной длины k. Предположим, что элемент a 1 из множества X 1 может быть выбран n 1 способами, те. 1 1 n X = . При уже выбранном элементе a 1 , элемент a 2 из множества X 2 может быть выбран n 2 способами, те. 2 2 n X = . При фиксированных a 1 и a 2 элемент a 3 из множества X 3 может быть выбран n 3 способами, те. 3 3 n X = и т.д. При фиксированных a 1 , a 2 ,…, a k–1 элемент a k из множества X k может быть выбран n k способами. Тогда число различных упорядоченных наборов равно произведению k n n n × × × 2 1 . Это означает, что Это правило часто называют комбинаторным принципом умножения. Доказательство. Будем доказывать теорему методом математической индукции. Базис индукции. Пусть n=2. В этом случае все элементы 4 множества Х х Х, те. упорядоченные пары (х, х, можно расположить в виде прямоугольной таблицы со строками — элементами Хи столбцами — элементами Х. В этой таблице, очевидно, будет |X 1 | x |X 2 | элементов. Индуктивный переход. Предположим справедливость утверждения теоремы для n. Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что В случае, когда X 1 =X 2 =…=X k эта формула принимает вид k k X X = . В этом случае множество X называется алфавитом, его элементы – буквами, а элементы декартова произведения X k , те. упорядоченные пары из k букв (x 1 ,x 2 ,…,x k ) называют словами в алфавите X. Число k называется длиной слова. Пусть |X|=m, тогда формулу k k X X = можно сформулировать следующим образом число слов длины k в алфавите из m букв равно Пример. Битовая строка – это строка, состоящая из элементов множества {0, 1}, те. каждый из элементов имеет значение 0 или 1. Сколько существует битовых строк длины 5? Сколько существует битовых строк длины k? Поскольку каждый символ строки может иметь значение 1 или 0, то существует два варианта выбора для каждой позиции. Следовательно, существует 2 x 2 x 2 x 2 x 2 = 2 5 битовых строк длины 5. По аналогичным соображениям, имеется 2 k битовых строк длины k. Пример. Используя правило произведения и правило суммы, найдем число различных трехзначных чисел, не содержащих одинаковых цифр, и число различных трехзначных чисел, содержащих хотя бы две одинаковые цифры Пусть a 1 , a 2 , a 3 – цифры трехзначного числа. Первую цифру a 1 можно выбрать девятью способами (в качестве нее можно взять любую цифру, кроме нуля при фиксированной первой цифре вторую цифру a 2 можно выбрать также девятью способами (в качестве нее можно взять любую цифру, кроме a 1 ); наконец, при фиксированных первой и второй цифрах третью цифру можно выбрать восемью способами. По правилу произведения число трехзначных чисел, не содержащих одинаковых цифр, равно 9 · 9 · 8=648. Всего имеется 900 различных трехзначных чисел (от 100 до 999). Каждое из них либо содержит две одинаковые цифры, либо нет. Следовательно, имеется 900 – 648 = 252 различных трехзначных числа, содержащих хотя бы две одинаковые цифры. □ 5 Третьим важным принципом является правило взаимно однозначного соответствия (правило биекции или правило равенства множества A и B имеют одинаковое количество элементов | A | = | B | тогда и только тогда, когда между ними можно установить взаимно однозначное соответствие. В качестве примера применения этого принципа подсчитаем количество всевозможных подмножеств множества M, состоящего из n элементов. Так это количество не зависит от природы элементов множества М, возьмем M={1,2,…,n}. Произвольному подмножеству M A ⊆ поставим в соответствие двоичное слово n α α α 2 1 последующему правилу ⎩ ⎨ ⎧ ∉ ∈ = A i если A i если i , 0 , 1 α Это соответствие взаимно однозначное. Отсюда число всех подмножеств n – элементного множества равно числу двоичных слов длины n, те. равно Пример. Сколькими способами можно разложить 10 монет разной стоимости по двум карманам Формализуя задачу, отметим, что два кармана дадут два подмножества 10 – элементного множества объединение множеств монет, лежащих в этих двух карманах, дает все множество пересечение этих множеств пусто. Это значит, что те монеты, которые лежат водном кармане, полностью определяют содержимое второго кармана. Используя правило биекции, можем сказать, что требуемых способов столько, сколько подмножеств в 10 – элементном множестве. То. можем написать ответ 2 10 =1024. Напомним также принцип Дирихле, который мы формулировали следующим образом. Пусть f : А —> В — функция, причем как A, таки В — конечные множества. Предположим, что А состоит из n элементов a 1 , а. Принцип Дирихле гласит, что если |А|>|В|, то по крайней мере одно значение f встретится более одного раза. Проще говоря, найдется пара элементов , для которых j i a a ≠ ( ) ( Пример. Показать, что если в прямоугольнике со сторонами 6 и 8 сантиметров помещены пять точек, то существуют две точки, расстояние между которыми не более 5 сантиметров. Разделим исходный прямоугольник на четыре прямоугольника, размером 3 на 4 сантиметра каждый. Поскольку пять точек должны находиться либо внутри, либо на границах четырех прямоугольников, то хотя бы две точки должны быть либо внутри, либо на границе одного итого же прямоугольника размерах. Но любые такие точки находятся на расстоянии не более 5 сантиметров. □ 6 6.2 Модельные схемы Задачи, ответы к которым часто используются, называют модельными. Они часто касаются конкретных вещей – карточных наборов, размещение шаров в урнах, множества дорог на карте и т.д. Поскольку природа множества при подсчете количества его элементов несущественна, то обычно ограничиваются объектами какой-нибудь одинаковой природы. Ответы к модельным задачам называются комбинаторными числами. Используя взаимно однозначное соответствие между элементами исследуемого множества и элементами модельного множества, устанавливается количество элементов того множества, которое требуется сосчитать. Дадим некоторые определения. Пусть задано множество X. Последовательная запись нескольких элементов изв которой каждый элемент может встретиться только один рази порядок записи элементов существенный, называется упорядоченным подмножеством в X. Пусть { n x x x X ,..., , 2 1 } = – конечное множество. Любой упорядоченный набор ( ) n i i i x x x ,..., , 2 1 из n различных элементов множества X называется перестановкой элементов множества X. Любое упорядоченное подмножество ( ) m i i i x x x ,..., , 2 1 из m различных элементов множества X называется размещением из n элементов по m. В частности, для n=m размещение будет перестановкой. Количество m – элементных упорядоченных подмножеств в n – элементном множестве обозначается через и называется количеством размещений из n по m. Если m=n, то эту величину называют количеством перестановок из n элементов и обозначают Когда речь идет про подсчет количеств, слово размещение понимаем как синоним словосочетания упорядоченное множество. Также слово перестановка понимается как размещение всех элементов множества в определенном порядке. Любой неупорядоченный набор, те. подмножество ( ) m i i i x x x ,..., , 2 1 из m, различных элементов множества X называется сочетанием m элементов из n , а их количество обозначается . Это количество еще называют количеством комбинаций m элементов из n. В контексте вычислений слово подмножество и комбинация являются синонимами. Если в размещении и сочетании из n элементов по m убрать требование различия элементов и разрешить повторение элементов из множества X, то такие размещение и сочетание называются с повторениями. Основными модельными являются следующие комбинаторные задачи. Найти − число Р всех перестановок из n элементов − число m n A всех размещений m элементов из n элементов 7 − число ⎟⎟ всех сочетаний m элементов из n элементов ⎠ ⎞ ⎜⎜ ⎝ ⎛ = m n C m n − число m n A всех размещений m элементов из n с повторениями − число m n C всех сочетаний m элементов из n элементов с повторениями Во всех формулах будет встречаться факториал целого неотрицательного числа. Напомним, что факториалом целого положительного числа n обозначение n!) называется произведение 1 · 2 · · n. По определению считается, что 0! = 1. Перестановки. Переставляя объекты некоторого множества, мы обычно располагаем их в различном порядке. В этом смысле перестановка — это переупорядочение элементов множества. Исследуем, сколько существует способов переупорядочения элементов множества. Рассмотрим количество возможных способов формирования числа, переставляя цифры 1, 2, 3, 4 и 5. Варианты возможных перестановок — это, например, числа 12345, 15342, 32415 и 32415. Для нахождения количества возможных перестановок заметим, что первую цифру можно выбрать пятью способами, вторую — четырьмя способами, третью — тремя способами, четвертую — двумя, и только один вариант остается для выбора пятой цифры. Поэтому существует 5! возможных перестановок. Точно также, если необходимо переупорядочить n объектов, то для этого существует n! способов. Таким образом получена Теорема число перестановок P n равно ! n P n = Доказательство. На первое место в перестановке можно поставить любой из n элементов множества X, на второе место — уже любой из n-1 оставшихся и т. д. На последнее место остается только один элемент. Тем самым всего будет Р = n(n—1)... 1 = n! перестановок. В перестановках важен порядок. Числа 51342 и 32415, образованные перестановкой цифр 1, 2, 3, 4 и 5, не совпадают. Кроме того, поскольку перестановки рассматриваются как переупорядочения, то каждый элемент множества можно использовать только один раз. Если бы повтор цифр допускался, то при формировании числа для каждой цифры существовало бы пять вариантов выбора, поэтому существовало бы 5 5 возможных чисел. Перестановки элементов 1,2,…,n записываются в матричной форме ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = n n π π π π 2 1 2 1 , где верхняя строка – это порядковые номера 1,2,…,n позиций элементов в перестановке нижняя строка — тот же набор чисел 1,2,..., n, взятых в каком- каком-либо порядке j π — номер элемента нам месте перестановки. Порядок столбцов в перестановках, записанных в матричной форме, не является существенным, так как в этом случае номер позиции каждого 8 элемента в перестановке указывается явно в верхней строке. Например, перестановка (3,2,4,1) из четырех элементов может быть записана по-разному Пример. Задача оладьях. Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они не били друг друга Решение. Условие не могли бить означает, что на каждой горизонтали и вертикали может стоять лишь одна ладья. Ввиду этого, каждому расположению ладей на доске соответствует перестановка ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = 8 2 1 8 2 Верхняя строка перестановки — это номер горизонталей, нижняя — вертикалей, пересечение которых определяет положение ладей на доске. Следовательно, число расстановок ладей равно числу перестановок Риз элементов. Размещения без повторений. Можно рассматривать перестановки, когда объектов больше, чем мест для их размещения. Предположим, например, что в организации – 20 человек и из них требуется выбрать президента, вице- президента, секретаря и казначея. Имеются 20 вариантов выбора президента, 19 вариантов выбора вице-президента, 18 способов выбора секретаря и 17 – казначея. Таким образом, получаем 20 x 19 x 18 x 17 способов выбора должностных лиц. Отметим, что порядок все еще остается существенным. Предположим, имеется n человек. Требуется выбрать r из них и расположить в определенном порядке. Существует n способов выбрать первого человека, n – 1 способов выбора второго, n–2 способов выбора третьего, n–j+1 способов выбора j – г и n–r+l способов выбора r – го человека. Следовательно, существует способов выбрать r человек из n. Но Сформулируем вышесказанное в виде следующей теоремы. Теорема. Количество способов выбрать r объектов с учетом порядка из n объектов равно Число ( ) ! ! r n n A r n − = называется числом размещений r элементов из n элементов или размещением без повторений. Заметим, что если выбирать все n объектов и размещать их в определенном порядке, то r = n и, поскольку 0! = 1, имеем 9 Приходим к уже известному результату для перестановок n элементов. Пример. В турнире мисс факультет участвуют 17 девушек. Разыгрываются призы за первое, второе и третье места. Сколькими способами могут быть распределены места Решение девушек претендуют на 3 места. Тогда тройку призеров можно выбрать способами. 4080 15 16 17 Пример. Сколько различных четырехзначных чисел можно образовать из цифр 1, 2, 3, ..., 9, если все цифры в каждом четырехзначном числе различны Для формирования каждого четырехзначного числа выбираем четыре цифры из девяти, поэтому существует ( ) 3024 ! 5 ! 9 ! 4 9 ! 9 таких различных чисел. Пример. Сколькими способами можно рассадить 10 человек за круглым столом, если имеет значение только порядок соседей. Существует несколько вариантов решения данной задачи. Первым делом, отметим, что вращение людей вокруг стола не меняет их взаимного расположения, поскольку соседи справа и слева остаются прежними. Предположим, что место за столом уникально. Тогда существует 10! способов рассадить людей за столом. Считаем, что при вращении места остаются теми же, так как соседи не меняются. Существует десять таких вращений, поэтому делим 10! на 10, что дает 9! способов расположить людей за столом, если имеет значение только порядок соседей. Иной подход к решению задачи состоит в том, чтобы сначала усадить одного человека. Этим исключается вращение, а оставшихся 9 человек можно рассадить 9! способами. Сочетания. В тех случаях, когда нас не интересует порядок элементов в размещении, а интересует лишь ее состав, то говорят о сочетаниях. То. сейчас нас интересуют k – элементные подмножества исходного n – элементного множества. Их называют сочетаниями. Сочетаниями из n различных элементов по k называют всевозможные размещения длины k, образованные из этих элементов и отличающиеся друг от друга составом, ноне порядком элементов. Общее число сочетаний обозначают через или Составим все сочетания из n по k. Затем переставим в каждом сочетании элементы всеми возможными способами. Теперь мы получили все размещения. Они отличаются либо составом, либо порядком, те. это все размещения без повторений из n по k. Их число равно . Учитывая, что k n A 10 каждое сочетание дает k! перестановок, то по правилу произведения можно записать . Тогда k n k n A k C = × ! ( ) ( ) ( ) ! ! ! ! 1 Отсюда также видно, что . То. получаем теорему количество способов выбора r объектов из n объектов без учета порядка равно Число называется числом сочетаний из n объектов по r. Обратите внимание, что в случае сочетаний, как ив случае перестановок и размещений, при выборе r объектов каждый объект может быть выбран не более одного раза. Пример. Если множество содержит десять элементов, то сколько оно имеет трехэлементных подмножеств Поскольку множество не упорядочено, выбираются три элемента из десяти, поэтому всего имеется 120 ! 3 ! 7 ! 10 различных подмножеств. Пример. Сколько строк длины девять содержат ровно 5 единиц и 4 нуля В строке имеется девять мест для размещения 1 и 0. Можно выбрать любые пять из девяти мест для размещения единицы. Поэтому имеется 126 ! 4 ! 5 ! 9 5 9 = = C мест для размещения единицы. Как только единицы вставлены, остальные места заполняются нулями. Пример. Сколько существует вариантов выбора 5 карт из стандартной колоды, содержащей 52 карты Поскольку порядок карт не имеет значения, речь идет о выборе 5 объектов из 52, поэтому существует 2598960 ! 47 ! 5 ! 52 5 52 = = C возможных комбинаций. Пример. Задача о прямоугольниках. Сколько различных прямоугольников можно вырезать из клеток доски, размер которой m х n? Решение. Прямоугольник однозначно определяется положением его сторон. Горизонтальные стороны могут занимать любое из m+1 положения. Тогда число способов их выбора равно (порядок сторон – какая верхняя, 2 1 + m C 11 а какая нижняя несущественен. Вертикальные стороны можно выбрать способами. По правилу прямого произведения заключаем, что количество прямоугольников равно 2 1 + n C 2 1 2 Пример. Сколько всего партий играется в шахматном турнире с n участниками Ответ , так как каждая партия однозначно определяется двумя ее участниками. Пример. Вернемся еще раз к примеру с подсчетом количества путей из вершины |