Лупаренко_ Комбинаторика
.pdfПриазовский государственный технический университет Кафедра высшей математики
ЛУПАРЕНКО Е.В.
КОНСПЕКТ ЛЕКЦИЙ по дисциплине: «ДИСКРЕТНАЯ МАТЕМАТИКА»
раздел «КОМБИНАТОРИКА» для студентов специальности 6.040301
«Прикладная математика»
Мариуполь 2011
УДК 519.1
Конспект лекций по дисциплине «Дискретная математика» раздел «Комбинаторика» для студентов специальности 6.040301 «Прикладная математика» / Сост. Е.В. Лупаренко. - Мариуполь, 2011.- 59 с.
В данном пособии содержатся сведения по основным вопросам классической комбинаторики. Рассматриваются некоторые классы наиболее часто встречающихся задач: комбинаторные задачи с ограничениями, комбинаторные задачи раскладок и разбиений, комбинаторные задачи, решаемые с помощью рекуррентных соотношений.
Материал изложен в объеме, необходимом для изучения курса «Дискретная математика» раздел «Комбинаторика» для студентов специальности 6.040301 «Прикладная математика». Приведены решения многих типовых задач с подробными объяснениями. Данное пособие может быть использовано для самостоятельного изучения курса, а также для дистанционного обучения.
Рецензент: С.П. Десятский, к.ф-м.н., доцент,
Составитель: |
Е.В. Лупаренко, к.т.н., доцент |
Отв. за выпуск: |
зав. кафедрой Буланчук Г.Г. |
|
к.ф-м.н., доцент |
Утверждено на заседании кафедры высшей математики
Протокол № от " " |
2011 г. |
Рекомендовано учебно-методической комиссией факультета информационных технологий
Протокол № от " " |
2011 г. |
2
ВВЕДЕНИЕ.
Дискретная математика – это раздел математики, который зародился еще в древности, порядка 2000 лет назад, но бурное развитие получил только в 20 веке.
Математика, как наука, естественно, от рождения делится на
дискретную и континуальную (непрерывную) математику. К континуальной математике мы относим все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное – дискретная математика:
−арифметика;
−алгебра;
−теория множеств;
−математическая логика;
−комбинаторный анализ;
−теория алгоритмов и многое другое.
Современный период развития дискретной математики – является самым интенсивным: очень быстро расширяется сфера приложений, увеличиваются объемы новой информации и число новых результатов. Если сравнительно недавно эта наука была сферой интересов лишь узкого круга специалистов, то сегодня она превратилась в научную дисциплину, очень важную и нужную во многих сферах. Массовое использование вычислительной техники значительно расширяет сферу прикладных исследований, в которых все больше применяется аппарат дискретной математики.
Роль и место дискретной математики в современной науке определяется тремя факторами:
1.дискретную математику можно рассматривать как теоретические основы компьютерной математики;
2.модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках, включая химию, биологию, генетику, физику, психологию, экологию и др.;
3.язык дискретной математики чрезвычайно удобен и стал
фактически метаязыком всей современной математики. Достаточным и необходимым для изучения дискретной математики
является знание школьного курса математики.
Полученные знания будут полезны при изучении таких фундаментальных курсов, как: математический анализ, алгебра, теория вероятностей, функциональный анализ и все предметы компьютерного цикла дисциплин.
3
Комбинаторика является разделом дискретной математики, ориентированным на решение задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами и ограничениями. Каждое такое правило определяет способ построения некоторой комбинаторной конфигурации, поэтому комбинаторный анализ (комбинаторика) занимается изучением свойств комбинаторных конфигураций, условиями их существования, алгоритмами построения и оптимизацией этих алгоритмов.
Этот раздел математики тесно связан с рядом других разделов дискретной математики: теорией вероятностей, теорией графов, теорией чисел, теорией групп и т.д.
В данном конспекте лекций рассматриваются вопросы классической комбинаторики: размещения, перестановки, сочетания; рассматриваются некоторые классы наиболее часто встречающихся задач: комбинаторные задачи с ограничениями, комбинаторные задачи раскладок и разбиений, комбинаторные задачи, решаемые с помощью рекуррентных соотношений.
4
ЛЕКЦИЯ 1.
ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА.
Общая характеристика комбинаторных задач. Правило произведения. Правило суммы. Перестановки. Сочетания. Размещения.
Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия.
Например:
-сколькими способами можно расположить в очереди 50 человек; -сколькими способами могут распределиться золотая, серебреная и
бронзовая медали на чемпионате мира по футболу; -сколько существует способов составления расписания занятий для
группы КМ на понедельник.
Задачи такого типа называются комбинаторными, а наука их решающая – комбинаторика.
Комбинаторика – это раздел дискретной математики, который изучает комбинации и перестановку предметов, взаимное размещение частей конечных множеств предметов произвольного происхождения, а также бесконечных множеств, которые удовлетворяют некоторым условиям.
С комбинаторными вычислениями приходится иметь дело представителям многих специальностей:
−ученому-химику при рассмотрении различных возможных типов связей атомов в молекулах;
−биологу при изучении различных возможных последовательностей
чередования аминокислот в белковых соединениях;
−агроному, рассматривавшему различные возможные способы посевов на нескольких участках;
−диспетчеру при составлении графика движения;
−кибернетику при решении задач кодирования и построения вычислительных устройств; -математику – при решении множества разнообразных задач,
особенно в теории вероятностей и т.п.
Бытует мнение, что комбинаторные задачи элементарны.
Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что, несмотря на заманчивую простоту постановки комбинаторные задачи в большинстве очень трудны;
5
многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся:
1.Задачи на размещения: задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия.
2.Задачи о покрытиях и заполнениях: например, задачи о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров.
3.Задачи о маршрутах – задачи оптимального плана, например, задачи на отыскание кратчайшего пути и т.п.
4.Комбинаторные задачи теории графов – задачи сетевого планирования, например, задачи транспортных и электрических сетей.
5.Перечислительные задачи – в которых речь идет о числе предметов, составленных из данного набора элементов при соблюдении определенных правил.
Взадачах комбинаторного анализа исследуются дискретные множества, в основном конечные. Особенность комбинаторных задач заключается в том, что в них преимущественное внимание уделяется двум видам операций: отбору подмножеств и упорядочению элементов. Эти две операции и являются основными – комбинаторными.
Основные правила комбинаторики. Правило произведения.
Рассмотрим следующую задачу:
Задача: Из Киева до Донецка можно добраться поездом, самолетом, автобусом, а из Донецка до Мариуполя можно добраться автобусом и поездом. Сколькими способами можно осуществить
путешествие по маршруту Киев-Донецк-Мариуполь? |
|
|
|
|||
|
|
Решение: |
|
|
|
|
|
|
|
3 2 = 6 , т.к. |
выбрав один |
||
K |
D |
M |
из возможных |
способов |
||
путешествия |
от |
Киева |
до |
|||
|
|
|
Донецка |
имеем |
два |
|
|
Рис.1.1 |
|
возможных |
|
способа |
|
|
|
путешествия от Донецка до |
||||
|
|
|
Мариуполя. |
|
|
|
Соображения, которые приведены при решении задачи, доказывают справедливость следующего простого утверждения, которое называют
основным правилом комбинаторики.
6
Правило умножения (основное правило комбинаторики).
Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить n1 способами, второе действие - n2
способами, третье действие - n3 способами и так до k -го действия,
которое можно выполнить nk способами, то все k действий вместе могут быть выполнены
N = n1 n2 n3 ... nk
способами.
В этом правиле важную роль играет союз «и», который объединяет разные действия в одно.
Например:
1. Сколькими способами на первенстве мира по футболу могут
распределиться медали, если в финальной части играют 24 команды?
Решение: 24 23 22 =12144 .
2. Сколько трехзначных чисел можно составить из цифр 0, 1, 2, 3, 4,
5, если:
а) цифры могут повторяться:
5 6 6 =180
б) ни одна из цифр не повторяется дважды:
5 6 4 =100
в) цифры нечетные и могут повторяться.
3 3 3 = 27 .
3. На дежурство в общежитие выбираются 2 студента – один из трех, проживающих в комнате №1, и один из четырех, проживающих в комнате №2. Сколько существует возможных способов формирования
разных пар из двух студентов для дежурства?
Решение: 3 4 =12 .
Правило суммы.
Если необходимо выполнить некоторое действие n1 , n 2 или nk
способами, то количество возможных способов выполнения этого действия будет равно:
N = n1 +n2 +...nk .
Особенностью этого правила есть то, что оно использует союз «или», который противопоставляет разные действия одно другому.
7
Например:
1. На дежурство в общежитии может пойти или студент из комнаты №1, где проживают 3 студента, или студент из комнаты №2, где проживают 4 студента. Сколькими способами можно выбрать одного
студента на дежурство.
Решение: 3+4=7.
2. Алфавит племени состоит из трех букв А, Б, С. Словом считается любая комбинация из этих букв длиной от 1 до 4. Каков
словарный запас племени.
Решение: Слов из одной буквы: 3. Слов из двух букв: 3 3 =9 . Слово из трёх букв: 3 3 3 = 27 .
Слово из четырёх букв: 3 3 3 3 =81 .
Тогда согласно правилу суммы словарный запас племени составляет
N =3 +9 +27 +81 =120 слов.
Одной из задач комбинаторики является задача отбора подмножеств данного множества. С этой операцией связано понятие выборки.
Определение: подмножество из k элементов, выбранное из множества Sn , состоящего из n элементов, называется выборкой объема k
из n элементов.
Различают выборки с повторением и без повторения,
упорядоченные и неупорядоченные.
Если выборки из k элементов множества Sn рассматриваются с учетом порядка элементов в них, то они называются размещениями. Обозначают Ank . Если же порядок элементов в выбранных подмножеств не важен, то соответствующие выборки называют сочетаниями. Обозначают
Cnk .
В выборках могут допускаться и не допускаться повторения элементов. Упорядоченная выборка из k элементов множества Sn , в которой элементы могут повторяться, называется размещением с повторением из n
элементов по k . Обозначают |
k |
Если все элементы упорядоченной |
An . |
выборки попарно различны, то такая выборка называется размещением без повторения. Обозначают Ank . Аналогично для сочетаний обозначают Cɶnk .
Если рассматривается выборка из n элементов множества Sn , то такие выборки называют перестановками. Обозначают Pn .
Например: Пусть A ={a;b; c}, k = 2. Указать все упорядоченные и
неупорядоченные выборки с повторениями и без повторений из трех элементов по 2.
8
Решение:
1. aa, ab, ac, ba,bb,bc, cc, ca, cb |
2 |
=9 . |
- 9 размещений с повторением: A3 |
2.ab, ac, ba, bc, ca, cb - 6 размещений без повторений: A32 =6 .
3.ab, ac, bc - три сочетания без повторений: C32 =3 .
сочетаний с повторениями 2 =
4. aa, bb, cc, ab, ac,bc - 6 : C3 6 .
Формулы для расчета числа размещений, перестановок и сочетаний без повторений.
Размещением – из n по k называется любая последовательность длины k составленная из неповторяющихся элементов.
Найдем число всех возможных размещений без повторений из n элементов по k . Задача сводится к последовательному применению правила произведения. В самом деле в множестве Sn объема n имеется n
возможностей для выбора первого элемента; для выбора второго элемента остается n −1 возможность, т.к. речь идет о перестановках без повторений и один раз выбранный элемент уже не участвует в дальнейшем выборе. Аналогично рассуждая, получаем, что для выбора k -го элемента остается n −k +1 возможность. Тогда
|
|
|
Ak |
= n |
( |
n −1 ... |
( |
n −k +1 |
= |
|
n! |
(1.1) |
|||
|
|
||||||||||||||
|
|
|
n |
|
) |
|
|
) |
(n −k )! |
||||||
|
Действительно, |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
n! |
= |
1 2 3 ... (n −k )(n −k +1) ... n |
= n (n −1) ... (n −k +1) |
|||||||||||
|
|
|
|
|
|||||||||||
(n −k )! |
1 2 3 ... (n −k) |
|
|
|
|
|
|||||||||
|
Здесь принято, что 0! =1! =1 |
|
|
|
|
|
|
|
|
|
|||||
|
Таким образом, доказана теорема. |
|
|
|
|
|
|||||||||
|
Теорема 1.1. Число упорядоченных выборок k |
элементов из n без |
|||||||||||||
повторения, т.е. число размещений без повторения, равно: |
|||||||||||||||
|
|
|
|
|
|
Ak = |
|
|
n! |
|
|
|
|
|
|
|
|
|
|
|
|
(n −k)! |
|
|
|
|
|
||||
|
|
|
|
|
|
n |
|
|
|
|
|
Например:
∙ Сколькими способами можно расставить 4 книги на полке, содержащей 25 мест?
Решение: A254 = 25 24 23 22 =303600 .
∙ Учащемуся необходимо сдать 4 экзамена на протяжении 8 дней. Сколькими способами это можно сделать?
Решение: A84 =8 7 6 5 =1680 .
9
Если известно, что последний экзамен будет сдаваться на 8-ой день,
то A73 4 =7 6 5 4 =840 .
Перестановки.
Определение. Перестановкой из n элементов множества Sn называется всякое размещение этого множества по n элементов.
Ann = Pn .
Например. Рассмотрим трехэлементное множество A ={1; 2;3}.
Записать все перестановки этого множества.
Решение.
(1, 2,3); (1, 3, 2); (2,1,3); (2, 3,1); (3,1, 2); (3, 2,1). Таким образом P3 =6 .
Теорема 1.2. Число всех перестановок n - элементного множества
равно:
|
|
Pn = n! |
(1.2) |
|
Доказательство. |
||||
По определению перестановки: |
|
|
||
P = An = n |
n −1 ... 1 = n! |
|||
n |
n |
( |
|
) |
Например:
∙ Сколькими способами можно разместить 5 книг на полке?
Решение: число способов расстановки книг равно числу способов упорядочения множества, состоящего из 5 элементов, т.е.
P5 =5!=1 2 3 4 5 =120 .
∙ Сколькими способами можно упорядочить множество {1, 2,..., 2n} так, чтобы каждое четное число имело четный номер?
Решение: четные числа можно расставить на местах с четными номерами (таких мест n ) n! способами; каждому способу размещения четных чисел на местах с четными номерами соответствует n! способов размещения нечетных чисел на местах с нечетными номерами. Значит, общее число способов
N = n! n! =(n!)2 .
Сочетания.
Определение. Неупорядоченная выборка k элементов из множества Sn , содержащего n элементов называют сочетаниями (всякое k - элементное подмножество множества из n элементов).
10