Шапорев С.Д. Дискретная математика - файл n1.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n1.doc





Дискретная математика.

Глава 1. Комбинаторика.
§ 1.1. Множества и действия над ними.
Первичным понятием теории множеств является понятие самого множества.

Множество - это совокупность некоторых (произвольных) объектов, объединенных по какому-либо признаку. Элементы множества при этом должны быть различными. Множество обозначается парой скобок , внутри которых либо просто перечисляются элементы, либо описываются их свойства. Например, - множество натуральных чисел, удовлетворяющих условию , очевидно, пусто. сложение, умножение - множество основных арифметических операций. Если необходимо указать, что объект является элементом множества , то пишут ( принадлежит ), наоборот запись говорит о том, что не принадлежит .

Если каждый элемент множества является элементом множества , то пишут или и говорят, что множество является подмножеством множества . Множества, состоящие из одних и тех же элементов, называются равными, то есть , в противном случае . Очевидно,

;

итак, Если , , то множество называется собственным подмножеством множества . Подмножества  - пустое и множества называются несобственными. С помощью скобок и операций над множествами можно построить новые множества, более сложные чем исходные.

1). Объединение. Эта операция над множествами обозначается , определяется как . Все операции над множествами можно иллюстрировать с помощью диаграмм Эйлера- Венна. Если за некоторое универсальное множество, содержащее как подмножества все другие множества, обозначить

(или ) и изобразить его в виде

всей плоскости, то любое множество

можно изобразить в виде части

плоскости, то есть в виде некоторой

фигуры, лежащей на плоскости. объ-

единение множеств и , на ри-

сунке заштриховано. .

2). Пересечением двух множеств называется такое множество , которое со-

















Леонард Эйлер (1707-1783 г.г.) - швейцарский математик.

Джон Венн (1834-1923 г.г.) - английский математик и логик.

стоит из элементов, принадлежащим одновременно обоим множествам, то есть . Пересечение множеств и заштриховано и изображено на левом рисунке, лежащем выше. На правом рисунке изображена разность двух множеств и .

3). Разностью двух множеств и называется множество , состоящее из тех и только тех элементов, которые входят в и одновременно не входят в , то есть Если, в частности, подмножество , то разность обозначается и называется дополнением множества . Если

и , то пару элементов на-

зывают упорядоченной парой, причем пары

и равны тогда и только тогда,

когда

4). Множество, элементами которого явля-

ются все упорядоченные пары , ,

называется прямым или декартовым произведением множеств и и обозначается Например, а Таким образом, декартово произведение не подчиняется коммутативному закону и справедливо, если Произведение называется декартовым квадратом.

Основные законы алгебры множеств.

1). Коммутативный:

2). Ассоциативный:

3). Дистрибутивный:

4). Законы поглощения:

5). Законы де Моргана (двойственности):

6). Закон двойного отрицания:

7). Закон включения:

8). Закон равенства:

Конечно, этим кратким перечнем количество законов алгебры множеств не исчерпывается. Другие соотношения между множествами могут быть выведены на основе вышеприведенных по правилом алгебры логики.
§ 1.2. Некоторые свойства множеств.
Множества и называются эквивалентными , если между элементами этих множеств можно установить взаимно однозначное соответствие, то есть каждому элементу множества сопоставить один и только один элемент множества так, что всем элементам множества будут сопоставлены различные элементы множества и все элементы множества будут сопоставлены некоторым элементам множества . Определение эквивалентности обладает следующими свойствами:



Огастес де Морган (1806-1871 г.г.) - шотладский математик и логик.
1). рефлексивности ;

2). симметричности ;

3). транзитивности .

Множество называется конечным, если такое, что . Говорят, что имеет мощность, равную. Если , то множества и имеют одинаковую мощность.

Множество называется счетным, если , множество называется несчетным, если его мощность больше мощности множества . Из теории чисел, например, известно, что множество всех рациональных чисел счетно, а множество всех действительных чисел несчетно.

Множество называется множеством мощности континиума, если .

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

Пример 1. Доказать включения

Легче всего сделать это по диаграмме Эйлера - Венна.

















Пример 2. Пусть Из каких элементов состоит множество ?

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

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

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

3). задачи о маршрутах. К ним относятся задачи на отыскание кратчайшего пути и тому подобное. Это задачи оптимального плана;

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

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

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

С операцией отбора множеств связано понятие выборки. С этим понятием можно связать как осуществление операции отбора, так и ее результат - само выбранное подмножество.

Подмножество из элементов, выбранное из множества , состоящего из элементов, называется - выборкой, а - объемом этой выборки.

Если - выборки рассматриваются с учетом порядка элементов в них, то они называются - перестановками. Если же порядок элементов в выбранных подмножествах не важен, то соответствующие выборки называются - сочетаниями.

Число элементов множества называется кардинальным числом множества и обозначается

В выборках могут допускаться и не допускаться повторения элементов.

Упорядоченная - выборка, в которой элементы могут повторяться, называется перестановкой с повторениями из элементов по или - перестановкой с повторениями.

Если элементы упорядоченной - выборки попарно различны, то она называется - перестановкой без повторений. Число - перестановок обозначается символом или , а число перестановок с повторениями или . - первая буква французского слова Permutation - перестановка. До сих пор во многих учебниках - перестановки называются размещениями и обозначаются символом , собственно же перестановками называются упорядоченные - выборки. - первая буква французского слова Arrangement - размещение, приведение в порядок.

Неупорядоченная - выборка, в которой элементы могут повторяться, называется сочетанием с повторениями из элементов по .

Число сочетаний без повторений обозначается символами , с повторениями или . - первая буква французского слова Combination - сочетание. Наиболее употребительным является обозначение .


Символ называется символом Аппеля.

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

1). - девять перестановок с повторениями,

2). - шесть перестановок без повторений,

3). - три сочетания без повторений,

4). - шесть сочетаний с повторениями,
§ 1.4. Правило суммы и правило произведения.
Основной комбинаторной задачей является подсчет числа - выборок при различных условиях. Опыт выполнения комбинаторных операций отбора подмножеств привел к следующим двум логическим правилам.

1). Правило суммы.

Если из множества подмножество (которое может состоять и из одного элемента) можно выбрать способами, а подмножество , отличное от , способами, и при этом выборы и таковы, что взаимно исключают друг друга и не могут быть получены одновременно, то выбор из множества множества можно получить способами.

Прокомментируем это правило подробнее. Если , то и называются непересекающимися множествами, в частности, если  при всех то называется разбиением множества на непересекающиеся подмножества или просто разбиением. Правило суммы можно сформулировать и в терминах теории множеств: если даны - множество и - множество , то при  объединение будет - множеством. Если дано разбиение , где , и если есть - множество , то множество есть - множество.

2). Правило произведения.

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

В терминах теории множеств это правило соответствует понятию декартова произведения множеств: если является - множеством, а - множеством, то окажется - множеством.

Пусть суть - множества, . Построим множества: Тогда будет множеством.

При решении практических задач правило произведения часто употребляется при подсчете числа вариантов при проведении - выборок. В этом случае его формулировка может выглядеть, например, так.



Поль Эмиль Аппель (1855-1930 г.г.) - французский математик.

Пусть требуется выполнить одно за другим действий. Если первое действие можно выполнить способами, второе действие - способами и так до -го действия, которое можно выполнить способами, то все действий вместе могут быть выполнены способами.

Рассмотрим теперь три вида отображения множеств и .

Отображением множества в множество называется соответствие между ними, при котором каждому элементу сопоставлен единственный элемент Элемент называется образом элемента при отображении . Два отображения и равны, если для всех .

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

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

Пример 1. В классе изучают 10 предметов. В понедельник шесть уроков, причем все уроки различные. Сколькими способами можно составить расписание на понедельник?

Речь в задаче идет о 6 - перестановках без повторения из 10 элементов. Первый урок можно поставить в расписание десятью способами, второй девятью, третий - восемью и так далее. По правилу произведения число способов составления расписания будет равно

Пример 2. Сколько имеется пятизначных чисел, которые делятся на пять?

Вспомним признаки делимости. Число делится на пять, если оно оканчивается на нуль или на пять. В задаче речь идет о - перестановках с повторениями. Первая цифра может быть выбрана из множества 1,2,3,4,5,6,7,8,9. Нуль не может участвовать в выборке, ибо при его выборе число будет четырехзначным, а не пятизначным. Итого, девять вариантов выбора для первой цифры. Вторая, третья и четвертая цифры могут быть любыми из набора 0,1,2,3,4,5,6,7,8,9. Последняя пятая цифра выбирается только из 0 и 5. Таким образом,
§ 1.5. Формулы для расчета перестановок и сочетаний без повторений

и с повторениями.
Найдем сначала число всех возможных - перестановок, то есть размещений. Задача сводится к последовательному применению правила произведения. В самом деле, в - множестве имеется возможностей для выбора первого элемента - перестановки; для выбора второго элемента останется возможностей, так как речь сейчас идет о перестановках без повторения, то есть один раз выбранный элемент уже не участвует в дальнейшей выборке. Аналогично рассуждая, получим, что для выбора - го элемента останется возможностей. Тогда

(1.5.1)

Действительно,



Здесь принято Итак, доказана следующая теорема

Теорема 1. Число упорядоченных - элементных подмножеств множества , состоящего из элементов равно

В частом случае, когда , получаем Это число способов упорядочения - элементного подмножества.

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

(1.5.2)

Подсчитаем теперь число - сочетаний. Пусть имеется ряд неупорядоченных - выборок без повторения элементов. Обозначим количество элементов множества, состоящего из всех возможных - сочетаний через Сравним числа и . - число упорядоченных выборок из элементов по ; - число неупорядоченных выборок из элементов по . Очевидно, что каждую неупорядоченную выборку объема можно упорядочить различными способами, то есть Тогда (1.5.3)

Полученный результат формулируется в виде теоремы.

Теорема 2. Число всех неупорядоченных - элементных подмножеств множества , состоящего из элементов равно

Рассмотрим более сложную задачу о числе - разбиений - множества , то есть разбиений вида , причем есть - подмножество множества . Очевидно, Рассуждаем аналогично тому, как это делалось при нахождении числа . Для выбора - подмножества из имеется возможностей, после этого - подмножество можно выбирать только из оставшихся элементов, так как . Этот выбор можно осуществить способами и так далее. Применяя правило произведения, получим, что искомое число - разбиений - множества равно (1.5.4)

Действительно,

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

Пример. Найти число различных слов (бессмысленных), которое можно получить, переставляя буквы слова «математика».

Разные буквы слова математика представляют собой множества , на которые можно разбить исходное слово и различные объединения которых будут давать новые бессмысленные слова. Здесь , Отсюда Исходное множество Тогда по формуле (1.5.4)



Подсчитаем, наконец, число - сочетаний с повторениями из множества . Пусть элементы множества занумерованы числами Так как множество конечно или счетно, то эта операция всегда возможна. Тогда вместо - сочетаний множества можно рассматривать - сочетания из эквивалентного ему множества в силу взаимно однозначного соответствия.

Всякая - выборка из может быть записана в виде , где , причем равенство возможно в силу того, что рассматриваются выборки с повторениями. - выборке поставим в соответствие - множество , в котором все элементы, очевидно, различны. Соответствие между и опять взаимно однозначное, причем - множества являются - сочетаниями без повторений из - множества . По формуле (1.5.3) число - сочетаний без повторения равно . Тогда

(1.5.5)
§ 1.6. Бином Ньютона и полиномиальная теорема.

а). Бином Ньютона.

Исторически название «бином Ньютона» несправедливо, ибо формулу знали еще среднеазиатские математики, начиная с Омара Хайяма (около 1100 г.); в Европе до Ньютона ее знал Паскаль. Заслуга Ньютона в том, что он обобщил эту формулу для нецелого показателя . Итак,

(1.6.1)



Исаак Ньютон (1643-1727 г.г.) - английский физик, астроном и математик.

Гийас ад-Дин Абу-л-Фатх Омар ибн Ибрахим Хайям (около 1048-после 1122 г.г.) - иранский

математик, астроном и поэт.

Блез Паскаль (1623-1662 г.г.) - французский математик.

Формула (1.6.1) легко доказывается методом математической индукции. Действительно, при Далее, предположив, что формула верна для , получаем

Проведем замену индекса суммирования Тогда Отсюда Выровняем пределы изменения индексов суммирования в обеих суммах. Для этого введем дополнительно тогда Отсюда Для нецелого формула имеет вид

при

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

1). Получим Это число равно числу всех возможных неупорядоченных подмножеств множества , состоящего из элементов. Действительно, так как число - элементных подмножеств ( - сочетаний) множества , то сумма в левой части есть число всех подмножеств.

2). Отсюда Из этого равенства вытекает, что суммы биномиальных коэффициентов, стоящих на четных и на нечетных местах, равны между собой, и каждая равна

б) Полиномиальная теорема.

Эта теорема является обобщением формулы бинома на случай слагаемых.

, (1.6.2)

то есть выражение равно сумме всех возможных слагаемых вида , где

Дискретная математика
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации