Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Перейдем к рассмотрению третьей задачи. Она содержит три пункта, каждый из которых проанализируем отдельно. Прежде всего заметим, что во всех трех случаях не имеет значения порядок выбора открыток, поэтому речь здесь идет о сочетаниях.
В пункте «а» задачи возможны повторяющиеся элементы.
Следовательно, искомое количество наборов равно числу сочетаний с повторениями из десяти по пять.
По условию пункта «б» все открытки должны быть различными.
Поэтому интересующее нас число наборов выражается числом сочетаний без повторений из десяти по пять.
В пункте «в» задачи речь идет о выборе пятнадцати произвольных открыток. Здесь повторяющиеся элементы неизбежны, поскольку видов открыток всего десять. Требуемое количество наборов находим как число сочетаний с повторениями из десяти по пятнадцать.
Слайд 49
Обратимся к четвертому примеру. В данном случае для нас важен порядок и повторений быть не может. Значит, будем использовать размещения без повторяющихся элементов.
В задаче есть ограничение, согласно которому лица одного пола не должны сидеть рядом. Так как в один ряд сажают троих мужчин и двух женщин, то требуемая ситуация возможна только в том случае, когда первым в ряду будет мужчина.
Для выбора мужчины на первое место имеем восемь возможностей.
Далее выбираем женщину, и для этого есть шесть различных вариантов.
Затем опять выбираем мужчину одним из семи возможных способов. Для дальнейшего выбора женщины на четвертое место имеется пять вариантов.
Наконец, мужчину на пятое место можно выбрать шестью различными способами. Окончательный ответ получаем с помощью правила произведения, перемножая пять указанных выше чисел.

Перейдем к рассмотрению пятой задачи. Принимая во внимание, что порядок при выборе группы людей неважен, мы приходим к выводу, что речь идет о сочетаниях. Из условия задачи ясно, что повторений здесь быть не может.
Согласно присутствующему в задаче ограничению должно быть выбрано не менее двух женщин, а значит, или две, или три, или четыре.
Таким образом, искомое число будет складываться из трех слагаемых.
Необходимо выбрать всего шесть человек. Если мы выбираем двух женщин, то затем надо выбрать четверых мужчин. При выборе трех женщин остальные трое будут мужчины. Наконец, если мы выбираем четырех женщин, то остается выбрать двух мужчин. Для нахождения каждого из трех слагаемых воспользуемся правилом произведения.
В первом случае из трех нами обозначенных сомножителями являются число сочетаний из четырех по два и число сочетаний из семи по четыре. Во втором случае мы считаем произведение числа сочетаний из четырех по три и числа сочетаний из семи по три. В последнем случае мы должны перемножить число сочетаний из четырех по четыре и число сочетаний из семи по два. Складывая три полученных произведения, приходим к окончательному результату.
Слайд 50
Обратимся к шестому примеру. В данной задаче мы имеем дело с перестановками с повторениями. Но при этом существует ограничение: три буквы «е» не должны идти подряд. В рассматриваемой ситуации проще найти число таких перестановок букв слова «перемет», в которых все буквы
«е» стоят рядом. Для ответа на вопрос задачи это число нужно будет вычесть из общего числа перестановок.
Всего в нашем слове семь букв, при этом буква «е» встречается три раза, а остальные буквы – по одному разу. По формуле для перестановок с

повторениями общее количество перестановок равно произведению чисел 4,
5, 6 и 7.
Найдем число перестановок, в которых три буквы «е» идут подряд.
«Склеим» эти три буквы вместе и будем считать их за единый символ. При таком подходе нам нужно найти число перестановок пяти различных элементов. Это число есть пять факториал, или сто двадцать.
Находя разность двух указанных чисел, получаем искомый ответ.
Слайд 51
С помощью первого правила комбинаторики определяется количество элементов объединения двух непересекающихся множеств. Для определения числа элементов объединения произвольных множеств применяется формула включения и исключения. Для двух множеств ее вид представлен в формуле
(2.10).
Расположенная на слайде диаграмма Эйлера – Венна объединения двух множеств объясняет справедливость этой формулы. Когда мы суммируем мощности множеств A[a] и B[бэ], то число элементов, которые принадлежат каждому из этих множеств, мы учитываем два раза. Поэтому необходимо из этой суммы вычесть мощность пересечения данных множеств.
Для трех множеств принцип включения и исключения отображен в формуле (2.11). Для произвольного числа множеств принцип включения и исключения описывается формулой (2.12). Сначала суммируются мощности всех множеств, затем исключаются мощности всех возможных пересечений двух множеств, затем опять прибавляются мощности всех возможных пересечений трех множеств и т. д. Доказательство формулы (2.12) может быть проведено методом математической индукции.
Слайд 52
Рассмотрим примеры применения принципа включения и исключения.
Обратимся к задаче, представленной на слайде.

Введем три множества, соответствующих дням с плохой погодой, и четвертое множество D[дэ] дней с хорошей погодой.
Нам даны мощности каждого из множеств А[а], В[бэ], С[це], содержащих дни с плохой погодой, и мощности множеств всевозможных их пересечений. Это дает нам возможность вычислить мощность объединения этих трех множеств с помощью формулы включения и исключения.
Мощность объединения множеств А[а], В[бэ], С[це] равна количеству дней месяца с плохой погодой. В результате вычислений мы получаем, что число таких дней равно пятнадцати. Тогда количество хороших дней можно определить как разность числа всех дней месяца и количества ненастных дней. Окончательно получаем, что число дней с хорошей погодой равно пятнадцати.
Слайд 53
На слайде приведен еще один пример применения принципа включения и исключения. Нам надо вычислить количество чисел, которые не удовлетворяют сразу трем свойствам, т. е. не делятся ни на 3, ни на 5, ни на
7. Для этого из общего числа чисел, меньших тысячи, нужно вычесть количество чисел, которые обладают хотя бы одним из этих свойств.
Количество чисел, обладающих хотя бы одним из указанных свойств, равно мощности объединения трех множеств, образованных из чисел, не делящихся соответственно на 3, на 5, на 7. Как мы знаем, для определения мощности объединения пересекающихся множеств используется принцип включения и исключения.
Для применения этого принципа нужно вычислить мощности множеств, участвующих в формуле. Каждое третье число делится на три, поэтому, чтобы найти количество чисел, делящихся на три, надо взять целую часть от деления общего числа чисел на три. Аналогичным образом вычисляются мощности множества чисел, делящихся на пять, и множества чисел, делящихся на семь.

Если число делится на три и на пять, то оно делится на пятнадцать.
Мощность множества таких чисел равна целой части от деления общего числа чисел на пятнадцать. Таким же образом вычисляются мощности двух других множеств, представляющих собой попарные пересечения исходных множеств.
Число, делящееся на три, на пять и на семь, делится на сто пять.
Количество таких чисел равно целой части от деления общего числа чисел на сто пять.
Подставляя найденные числовые значения в формулу включения и исключения, находим искомое число.
Слайд 54
Во многих задачах возникает необходимость раскрытия скобок при вычислении значения выражения вида (2.13). В таких ситуациях применяется так называемая полиномиальная формула, позволяющая возвести в степень
n[эн] сумму k[ка] слагаемых.
Количество участвующих в формуле слагаемых определяется числом различных наборов неотрицательных значений показателей степеней, дающих в сумме число n[эн]. Последнее требование обозначено равенством
(2.15).
Вид каждого отдельного слагаемого представлен формулой (2.14).
Сама полиномиальная формула выражается равенством (2.16).
В частном случае, когда n[эн] и k[ка] равны двум, формула содержит три слагаемых и представляет собой известную из школьного курса математики формулу квадрата суммы двух слагаемых. В случае, когда k[ка] равно двум, а n[эн] равно трем, мы получаем формулу куба суммы двух слагаемых.

Слайд 55
На слайде приведен пример применения полиномиальной формулы для определения коэффициента при переменной х[икс] в тридцать четвертой степени.
В данном случае в пятнадцатую степень возводится сумма трех слагаемых. Два первых слагаемых содержат переменную х[икс], третье слагаемое является константой. Сначала мы записываем общий член разложения по полиномиальной формуле. Он представлен формулой (2.17).
Уравнение (2.18) выражает условие, которому должны удовлетворять показатели степеней m[эм], n[эн] и k[ка]. Вычисляя суммарный показатель степени переменной х[икс] в формуле (2.18) и приравнивая его к тридцати четырем, получаем уравнение (2.19).
Решаем уравнение (2.19) в целых неотрицательных числах. Требуемым условиям удовлетворяют значения n[эн], равные единице, двум, трем и четырем. По ним находим соответствующие значения показателя m[эм].
Получаем четыре возможных решения, которые представлены на слайде.
Слайд 56
Продолжим решение нашей задачи.
Для каждого найденного набора значений m[эм] и n[эн] определим соответствующее значение переменной k[ка]. Получим четыре набора значений, представленных на слайде.
По каждому набору значений показателей m[эм], n[эн] и k[ка] построим слагаемое полиномиальной формулы, содержащее х[икс] в тридцать четвертой степени. Эти слагаемые указаны на слайде.
Вычислим числовые коэффициенты найденных выражений и просуммируем их. В результате мы получим искомый коэффициент при
х[икс] в тридцать четвертой степени.
Алгоритм решения, использованный для данной задачи, применим для всех задач подобного вида. При этом неважно, сколько слагаемых

суммируется, в какую степень возводится сумма, какое количество слагаемых содержит переменную.
Слайд 57
Частным случаем полиномиальной формулы при k[ка], равном двум, является биномиальная формула (2.20). Выражение в левой части формулы
(2.20) называется биномом Ньютона.
Числа, участвующие в формуле бинома Ньютона, называются биномиальными коэффициентами.
На слайде представлены некоторые свойства биномиальных коэффициентов.
Первое свойство проверяется непосредственными вычислениями.
Второе свойство является обобщением первого. Для его доказательства достаточно сравнить дробные выражения для биномиальных коэффициентов с номерами k[ка] и n − k[эн минус ка].
Для обоснования третьего свойства нужно записать выражения для коэффициентов с номерами k[ка] и k − 1[ка минус один] и произвести сложение дробей.
Для доказательства первого равенства из четвертого свойства надо применить формулу биномиальную формулу к n-й[энной] степени суммы двух единиц. Для проверки второго равенства нужно применить ту же формулу к n-й[энной] степени разности двух единиц.
Из третьего свойства биномиальных коэффициентов вытекает эффективный способ рекуррентного вычисления значений биномиальных коэффициентов, который можно представить в графической форме, известной как треугольник Паскаля.
В этом равнобедренном треугольнике каждое число, кроме единиц на боковых сторонах, является суммой двух чисел, стоящих над ними.
Биномиальный коэффициент
[це из эн по ка] находится в (n + 1)-м
[
эн плюс первом
]
ряду на (k + 1)-м[ка плюс первом] месте.

Слайд 58
Рассмотрим пример применения биномиальной формулы. Обратимся к задаче, представленной на слайде.
Пусть наибольшим слагаемым является S
k
[эс катое]. Тогда оно больше
(k − 1)-го[ка минус первого] слагаемого и (k + 1)-го[ка плюс первого]. Таким образом, должны выполняться неравенства (2.21).
Подставляя в неравенства (2.21) выражения для S
k
[эс катых], получаем систему (2.22). Заменяя в системе (2.22) биномиальные коэффициенты на соответствующие дробные выражения, приходим к системе (2.23). Далее мы упрощаем полученную систему.
Каждое из неравенств системы (2.23) разделим на общие множители левой и правой частей. Ими являются факториалы и степени корня из десяти и трех целых двух десятых. После проведенных преобразований в каждой части обоих неравенств системы останется по одному вхождению k[ка].
Продолжение решения системы представлено на следующем слайде.
Слайд 59
Продолжим решение нашей задачи.
В результате упрощений мы получаем систему (2.24). Умножим обе части неравенств системы (2.24) на общие знаменатели участвующих в них дробей. В результате мы получим систему линейных относительно переменной k[ка] неравенств. Преобразуем эту систему так, чтобы переменная k[ка] содержалась лишь в одной части каждого из неравенств.
Полученная система равносильна двойному неравенству для переменной
k[ка]. Упростим данное неравенство, вычислив приближенные значения участвующих в нем дробей. Единственное целое значение k[ка], удовлетворяющее последнему неравенству, равно десяти.
Таким образом, мы определили номер наибольшего члена разложения бинома. Теперь мы можем записать его формулу. Для этого достаточно подставить в выражение для S
k
[эс катого] значение k[ка], равное десяти.

Слайд 60
Тема 3.1. Понятие графа. Смежность, инцидентность, степени вершин. Способы задания графов
Перейдем к изучению следующего раздела, а именно, рассмотрению теории графов. В терминах теории графов формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, электрических цепей, блок-схем программ, в экономике, статистике, химии, биологии и в других областях. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.
В отличие от других научных дисциплин, теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйлером, жившим в 1707–1783, была опубликована в 1736 году в Трудах Академии наук в Санкт-Петербурге.
Исследование Эйлера было проведено в связи с популярной в то время задачей о кёнигсбергских мостах. С этой задачей мы познакомимся позднее.
Однако результат, полученный Эйлером, более ста лет оставался единственным результатом теории графов. Развитие теории графов в конце
XIX и начале XX века было связано с распространением представлений о молекулярном строении вещества и становлением теории электрических цепей. К 50-м годам нашего века в теории графов сложились два различных направления: алгебраическое и оптимизационное.
Например, поиск ответа на поставленный в задаче о кёнигсбергских мостах вопрос относится к алгебраическому направлению теории графов.
Изменим эту задачу. Отличие полученной задачи состоит в том, что требуется найти маршрут, по которому житель, выйдя из дома, пройдет по каждому мосту хотя бы один раз и вернется домой, причем длина маршрута должна быть минимальной.
Задача поиска такого маршрута относится к оптимизационному направлению теории графов. Оптимизационное направление получило

широкое развитие благодаря появлению ЭВМ, так как для эффективного использования ЭВМ при решении прикладных задач с использованием теории графов необходимы эффективные алгоритмы решения графовых задач.
Слайд 61
Графом G[жэ] в широком смысле называется любая пара вида (V, E)[вэ е], где V[вэ] – непустое множество элементов произвольной природы, а E[е] – семейство пар элементов из V[вэ]. Причем допускаются пары вида (v, v)[вэ вэ] и повторяющиеся пары (u, v)[у вэ], где элементы u[у] и v[вэ] различны.
Если множества V[вэ] и E[е] конечны, то граф называется конечным. Мы будем рассматривать только конечные графы.
Если пары в V[вэ] рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным, или орграфом.
Элементы множества V[вэ] называются вершинами графа, а пары из
E[е] – его ребрами. Ребра орграфа называют также ориентированными ребрами, или дугами, а ребра неориентированного графа
– неориентированными ребрами. Пара вида (v, v)[вэ вэ] называется петлей в вершине v[вэ]. Если пара (u, v)[у вэ] встречается в E[е] более одного раза, то говорят, что (u, v)[у вэ] – кратное ребро. Говорят, что ребро (u, v)[у вэ] в неориентированном графе соединяет вершины u[у] и v[вэ], а в ориентированном графе дуга (u, v)[у вэ] идет из вершины u[у] в вершину
v[вэ].
Граф с петлями называют псевдографом. Граф с кратными ребрами, но без петель называют мультиграфом. Графом в узком смысле называется граф без петель и кратных ребер.
Договоримся изображать графы на плоскости следующим образом.
Вершины будем изображать точками, а каждое ребро (u, v)[у вэ] – линией,