Лупаренко_ Комбинаторика

УДК 519.1

Конспект лекций по дисциплине «Дискретная математика» раздел «Комбинаторика» для студентов специальности 6.040301 «Прикладная математика» / Сост. Е.В. Лупаренко. - Мариуполь, 2011.- 59 с.

В данном пособии содержатся сведения по основным вопросам классической комбинаторики. Рассматриваются некоторые классы наиболее часто встречающихся задач: комбинаторные задачи с ограничениями, комбинаторные задачи раскладок и разбиений, комбинаторные задачи, решаемые с помощью рекуррентных соотношений.

Материал изложен в объеме, необходимом для изучения курса «Дискретная математика» раздел «Комбинаторика» для студентов специальности 6.040301 «Прикладная математика». Приведены решения многих типовых задач с подробными объяснениями. Данное пособие может быть использовано для самостоятельного изучения курса, а также для дистанционного обучения.

Рецензент: С.П. Десятский, к.ф-м.н., доцент,

Утверждено на заседании кафедры высшей математики

Рекомендовано учебно-методической комиссией факультета информационных технологий

2

ВВЕДЕНИЕ.

Дискретная математика – это раздел математики, который зародился еще в древности, порядка 2000 лет назад, но бурное развитие получил только в 20 веке.

Математика, как наука, естественно, от рождения делится на

дискретную и континуальную (непрерывную) математику. К континуальной математике мы относим все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное – дискретная математика:

−арифметика;

−алгебра;

−теория множеств;

−математическая логика;

−комбинаторный анализ;

−теория алгоритмов и многое другое.

Современный период развития дискретной математики – является самым интенсивным: очень быстро расширяется сфера приложений, увеличиваются объемы новой информации и число новых результатов. Если сравнительно недавно эта наука была сферой интересов лишь узкого круга специалистов, то сегодня она превратилась в научную дисциплину, очень важную и нужную во многих сферах. Массовое использование вычислительной техники значительно расширяет сферу прикладных исследований, в которых все больше применяется аппарат дискретной математики.

Роль и место дискретной математики в современной науке определяется тремя факторами:

1.дискретную математику можно рассматривать как теоретические основы компьютерной математики;

2.модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках, включая химию, биологию, генетику, физику, психологию, экологию и др.;

3.язык дискретной математики чрезвычайно удобен и стал

фактически метаязыком всей современной математики. Достаточным и необходимым для изучения дискретной математики

является знание школьного курса математики.

Полученные знания будут полезны при изучении таких фундаментальных курсов, как: математический анализ, алгебра, теория вероятностей, функциональный анализ и все предметы компьютерного цикла дисциплин.

3

Комбинаторика является разделом дискретной математики, ориентированным на решение задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами и ограничениями. Каждое такое правило определяет способ построения некоторой комбинаторной конфигурации, поэтому комбинаторный анализ (комбинаторика) занимается изучением свойств комбинаторных конфигураций, условиями их существования, алгоритмами построения и оптимизацией этих алгоритмов.

Этот раздел математики тесно связан с рядом других разделов дискретной математики: теорией вероятностей, теорией графов, теорией чисел, теорией групп и т.д.

В данном конспекте лекций рассматриваются вопросы классической комбинаторики: размещения, перестановки, сочетания; рассматриваются некоторые классы наиболее часто встречающихся задач: комбинаторные задачи с ограничениями, комбинаторные задачи раскладок и разбиений, комбинаторные задачи, решаемые с помощью рекуррентных соотношений.

4

ЛЕКЦИЯ 1.

ЭЛЕМЕНТЫ КОМБИНАТОРНОГО АНАЛИЗА.

Общая характеристика комбинаторных задач. Правило произведения. Правило суммы. Перестановки. Сочетания. Размещения.

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия.

Например:

-сколькими способами можно расположить в очереди 50 человек; -сколькими способами могут распределиться золотая, серебреная и

бронзовая медали на чемпионате мира по футболу; -сколько существует способов составления расписания занятий для

группы КМ на понедельник.

Задачи такого типа называются комбинаторными, а наука их решающая – комбинаторика.

Комбинаторика – это раздел дискретной математики, который изучает комбинации и перестановку предметов, взаимное размещение частей конечных множеств предметов произвольного происхождения, а также бесконечных множеств, которые удовлетворяют некоторым условиям.

С комбинаторными вычислениями приходится иметь дело представителям многих специальностей:

−ученому-химику при рассмотрении различных возможных типов связей атомов в молекулах;

−биологу при изучении различных возможных последовательностей

чередования аминокислот в белковых соединениях;

−агроному, рассматривавшему различные возможные способы посевов на нескольких участках;

−диспетчеру при составлении графика движения;

−кибернетику при решении задач кодирования и построения вычислительных устройств; -математику – при решении множества разнообразных задач,

особенно в теории вероятностей и т.п.

Бытует мнение, что комбинаторные задачи элементарны.

Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что, несмотря на заманчивую простоту постановки комбинаторные задачи в большинстве очень трудны;

5

многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся:

1.Задачи на размещения: задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия.

2.Задачи о покрытиях и заполнениях: например, задачи о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров.

3.Задачи о маршрутах – задачи оптимального плана, например, задачи на отыскание кратчайшего пути и т.п.

4.Комбинаторные задачи теории графов – задачи сетевого планирования, например, задачи транспортных и электрических сетей.

5.Перечислительные задачи – в которых речь идет о числе предметов, составленных из данного набора элементов при соблюдении определенных правил.

Взадачах комбинаторного анализа исследуются дискретные множества, в основном конечные. Особенность комбинаторных задач заключается в том, что в них преимущественное внимание уделяется двум видам операций: отбору подмножеств и упорядочению элементов. Эти две операции и являются основными – комбинаторными.

Основные правила комбинаторики. Правило произведения.

Рассмотрим следующую задачу:

Задача: Из Киева до Донецка можно добраться поездом, самолетом, автобусом, а из Донецка до Мариуполя можно добраться автобусом и поездом. Сколькими способами можно осуществить

Соображения, которые приведены при решении задачи, доказывают справедливость следующего простого утверждения, которое называют

основным правилом комбинаторики.

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

выборки попарно различны, то такая выборка называется размещением без повторения. Обозначают Ank . Аналогично для сочетаний обозначают Cɶnk .

Если рассматривается выборка из n элементов множества Sn , то такие выборки называют перестановками. Обозначают Pn .

Например: Пусть A ={a;b; c}, k = 2. Указать все упорядоченные и

неупорядоченные выборки с повторениями и без повторений из трех элементов по 2.

8

Решение:

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 возможность. Тогда

Например:

∙ Сколькими способами можно расставить 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 - элементного множества

равно:

Например:

∙ Сколькими способами можно разместить 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