Файл: Учебника по курсу Основы дискретной математики и логики.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 205
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Слайд 35
Тема 2.1. Элементы комбинаторики
Комбинаторика позволяет вычислять количество возможных комбинаций объектов, удовлетворяющих определенным условиям.
Первоначально комбинаторика рассматривалась как раздел
«досуговой» математики. Впервые теоретическое исследование проблем комбинаторики было проведено в XVII веке[семнадцатом] Паскалем, Ферма́,
Лейбницем и в XVIII веке[восемнадцатом веке] Якобом Берну́лли, Эйлером.
Тогда же сложилась и принятая в комбинаторике терминология – сочетания, размещения, перестановки и т. п. К началу ХХ [двадцатого] века комбинаторика считалась в основном завершенным разделом математики, лежащим вне основного русла развития математики и ее приложений. В ХХ веке комбинаторику стали рассматривать как раздел теории множеств, в котором изучаются различные проблемы, возникающие при исследовании конечных множеств. Такая точка зрения привела к более естественной и последовательной классификации основных понятий и задач комбинаторики.
В связи с развитием компьютерных наук и технологий возросла роль комбинаторики как инструмента решения многих задач. В настоящее время комбинаторика является одним из наиболее интенсивно развивающихся разделов математики. Она как область математического знания входит в дискретную математику.
На грани дискретной математики и программирования появляются новые дисциплины, в частности, комбинаторные алгоритмы.
Cлайд 36
Рассмотрим основные правила комбинаторики. Их два, и первым их них является правило суммы. Это правило позволяет определить число элементов объединения непересекающихся множеств.
Так как множества не пересекаются, то у них нет общих элементов.
Элементы первого множества обозначим буквой a[а] с индексом. Индекс
последнего элемента показывает, что множество A[а] содержит n[эн] элементов. Аналогично элементы второго множества обозначим буквой
b[бэ], и индекс последнего из них означает, что это множество содержит
m[эм] элементов. Выпишем множество, равное объединению множеств A[а] и
B[бэ]. Сначала запишем все элементы множества A[а], затем – все элементы множества B[бэ]. Установленное взаимно однозначное соответствие показывает, что объединение данных множеств состоит из n + m[эн плюс эм] элементов.
Правило суммы можно интерпретировать следующим образом. Если элемент а[а] из множества A[а] можно выбрать n способами, а элемент b[бэ] из множества B[бэ] – m[эм] способами, то выбор элемента х[икс], принадлежащего их объединению, можно осуществить n + m[эн плюс эм] способами.
Слайд 37
На слайде представлены два примера применения правила суммы.
В первой задаче роль множеств A[а] и B[бэ] играют соответственно множество девочек и множество мальчиков одного класса. Мощность первого множества равна шестнадцати, мощность второго – пятнадцати.
Выбор старосты соответствует выбору одного элемента из объединения этих множеств, и по правилу суммы число способов для осуществления этого выбора равно сумме шестнадцати и пятнадцати, то есть тридцати одному.
Во второй задаче множество A[а] включает в себя все вопросы, относящиеся к теме «Пределы», множество B[бэ] – все вопросы по теме
«Производные». Мощность первого множества равна восьми, мощность второго – двенадцати. Объединение множеств A[а] и B[бэ] состоит из вопросов, каждый из которых относится либо к первой, либо ко второй теме.
Поскольку множества A[а] и B[бэ] не пересекаются, по правилу суммы мы получаем, что количество «счастливых» вопросов равно сумме восьми и двенадцати, то есть двадцати.
b[бэ], и индекс последнего из них означает, что это множество содержит
m[эм] элементов. Выпишем множество, равное объединению множеств A[а] и
B[бэ]. Сначала запишем все элементы множества A[а], затем – все элементы множества B[бэ]. Установленное взаимно однозначное соответствие показывает, что объединение данных множеств состоит из n + m[эн плюс эм] элементов.
Правило суммы можно интерпретировать следующим образом. Если элемент а[а] из множества A[а] можно выбрать n способами, а элемент b[бэ] из множества B[бэ] – m[эм] способами, то выбор элемента х[икс], принадлежащего их объединению, можно осуществить n + m[эн плюс эм] способами.
Слайд 37
На слайде представлены два примера применения правила суммы.
В первой задаче роль множеств A[а] и B[бэ] играют соответственно множество девочек и множество мальчиков одного класса. Мощность первого множества равна шестнадцати, мощность второго – пятнадцати.
Выбор старосты соответствует выбору одного элемента из объединения этих множеств, и по правилу суммы число способов для осуществления этого выбора равно сумме шестнадцати и пятнадцати, то есть тридцати одному.
Во второй задаче множество A[а] включает в себя все вопросы, относящиеся к теме «Пределы», множество B[бэ] – все вопросы по теме
«Производные». Мощность первого множества равна восьми, мощность второго – двенадцати. Объединение множеств A[а] и B[бэ] состоит из вопросов, каждый из которых относится либо к первой, либо ко второй теме.
Поскольку множества A[а] и B[бэ] не пересекаются, по правилу суммы мы получаем, что количество «счастливых» вопросов равно сумме восьми и двенадцати, то есть двадцати.
Слайд 38
Второе правило комбинаторики – это правило произведения. Данное правило позволяет определить, чему равно количество элементов декартова произведения двух множеств.
Для доказательства этого правила введем вспомогательные множества.
Эти множества построим следующим образом. На первое место в пары, образующие множества, будем ставить фиксированный элемент множества
A[а], а на второе место – всевозможные элементы множества B[бэ]. У элементов множества M
1
[эм один] на первое место поставим элемент a
1
[а один], на второе место будем поочередно ставить все элементы множества
B[бэ]. У элементов множества M
2
[эм два] на первое место поставим элемент
a
2
[а два], а на второе место будем поочередно ставить все элементы множества B[бэ] и т. д. При таком построении каждое множество M
i
[эм итое] состоит из m[эм] элементов, а количество таких множеств совпадает с мощностью множества A[а], т. е. равно n[эн]. Объединение этих введенных множеств M
i
[эм итое] дает декартово произведение множеств A[а] и B[бэ].
Применяя правило суммы к объединению множеств M
i
[эм итое], получаем требуемое утверждение.
Правило произведения можно интерпретировать следующим образом.
Если элемент а[а] из множества A[а] можно выбрать n[эн] способами и если после каждого такого выбора элемент b[бэ] из множества B[бэ] можно выбрать m[эм] способами, то выбор пары (а, b)[а бэ] из декартова произведения можно осуществить n
m[эн эм] способами. В этом случае говорят, что выбор элементов множества A[а] не зависит от способа выбора элементов множества B[бэ].
Слайд 39
Теперь рассмотрим пример применения правила произведения. Введем в рассмотрение два множества. Первое множество состоит из всевозможных дорог из M[эм] в K[ка], второе множество содержит всевозможные дороги из
K[ка] в N[эн]. Для того чтобы построить маршрут из пункта M[эм] в пункт
N[эн], необходимо сначала выбрать элемент из первого множества, а затем произвести выбор элемента из второго множества. Выбор элемента из первого множества можно осуществить пятью способами. При каждом варианте осуществления этого действия выбор элемента второго множества можно произвести тремя способами. Образуем все возможные пары из элементов этих двух множеств. Упорядоченные пары являются элементами декартова произведения. Значит, нам необходимо найти мощность декартова произведения введенных множеств.
Поскольку мощность первого множества равна пяти, а мощность второго множества трем, по правилу произведения получаем, что количество элементов декартова произведения равно пятнадцати.
Слайд 40
Теперь перейдем к рассмотрению основных комбинаторных схем, с помощью которых можно посчитать количество всевозможных комбинаций, которые получаются при выборе элементов из имеющихся.
Первая комбинаторная схема, с которой мы познакомимся, называется размещением с повторениями.
Задача формулируется следующим образом. Имеются элементы n различных видов, причем элементов каждого вида неограниченное количество. Из этих элементов составляют всевозможные упорядоченные наборы длины k[ка], в которых элементы одного вида могут повторяться.
Такие наборы называются размещениями с повторениями из n[эн]по k[ка].
Выведем формулу для количества размещений с повторениями из n[эн]
по k[ка]. На каждое из k[ка] мест элемент можно выбрать n[эн] способами. По правилу произведения получаем, что общее число размещений с повторениями из n[эн]по k[ка] равно n[эн] в степени k[ка].
На слайде приведен пример, в котором применяются приведенные выше рассуждения.
Слайд 41
Далее рассмотрим размещения без повторений. Задача формулируется следующим образом. Имеется n[эн] различных элементов. Из них составляют всевозможные упорядоченные наборы длины k[ка]. Такие наборы называются размещениями без повторений из n[эн]по k[ка].
Выведем формулу для количества размещений без повторений. При записи таких наборов на первое место можно поставить любой из имеющихся n[эн] элементов. Тогда на второе место можно выбрать только любой из n − 1[эн минус один] оставшихся. На третье место остается уже n −
2[эн минус два] претендента. И так далее. Наконец, на k-тое[катое] место можно поставить любой из n − k + 1[эн минус ка плюс один] оставшихся элементов. В результате по правилу произведения получаем, что общее число размещений без повторений из n[эн] по k[ка] равно произведению упомянутых выше чисел. Используя факториал, это произведение можно записать в виде дроби.
Рассмотрим пример, представленный на слайде. Так как в каждый день можно сдать только один экзамен и порядок сдачи экзаменов имеет значение, используем формулу размещения без повторений.
Если известно, что последний экзамен студент будет сдавать на восьмой день, то существует 4 варианта выбора экзамена на последний день и
[А из семи по три] вариантов распределения оставшихся трех экзаменов в течение семи дней.
Слайд 42
Далее рассмотрим перестановки без повторений. Пусть имеется n[эн] различных элементов. Будем образовывать из них всевозможные упорядоченные наборы длины n[эн]. Такие наборы называются перестановками из n[эн] элементов, а их общее число обозначается Р
n
[пэ с индексом эн]. Перестановки являются частным случаем размещений без повторений из n[эн] по k[ка], когда k[ка] совпадает с n[эн]. Поэтому для
вывода формулы общего числа перестановок используем формулу для размещений без повторений и получаем n[эн] факториал.
Рассмотрим пример, представленный на слайде. Так как в условии задачи есть требование, что четные числа должны стоять на четных местах, то эти числа можно переставлять только между собой и это можно сделать
n![эн факториал] способами; каждому такому способу расстановки четных чисел соответствует n![эн факториал] способов расстановки нечетных чисел на нечетных местах. Тогда общее число перестановок получаем с помощью правила произведения.
Слайд 43
Следующая комбинаторная схема называется сочетанием без повторений. Задача формулируется следующим способом. Пусть имеется
n[эн] различных элементов. Сочетаниями из n[эн]по k[ка]называются все возможные неупорядоченные наборы, состоящие из k[ка]элементов.
Выведем формулу общего числа сочетаний из n[эн] по k[ка]. Составим сначала все различные сочетания из n[эн] по k[ка]. После этого произведем всевозможные перестановки элементов для каждого из таких наборов. В результате этого действия мы получим все размещения без повторений из
n[эн] по k[ка], а их общее число отображено в формуле (2.1). Так как элементов в наборе k[ка], то из одного сочетания можно получить k![ка факториал] размещений. Тогда по правилу произведения можно записать формулу (2.2). Выразив из этой формулы число сочетаний, мы получим окончательный ответ, который отображается в формуле (2.3).
Для числа всех сочетаний без повторений из n[эн] по k[ка] используются также обозначения, записанные в формуле (2.4).
Слайд 44
Рассмотрим пример, представленный на слайде. Так как нам необходимо составить комиссию из трех человек, то порядок выбранных
Рассмотрим пример, представленный на слайде. Так как в условии задачи есть требование, что четные числа должны стоять на четных местах, то эти числа можно переставлять только между собой и это можно сделать
n![эн факториал] способами; каждому такому способу расстановки четных чисел соответствует n![эн факториал] способов расстановки нечетных чисел на нечетных местах. Тогда общее число перестановок получаем с помощью правила произведения.
Слайд 43
Следующая комбинаторная схема называется сочетанием без повторений. Задача формулируется следующим способом. Пусть имеется
n[эн] различных элементов. Сочетаниями из n[эн]по k[ка]называются все возможные неупорядоченные наборы, состоящие из k[ка]элементов.
Выведем формулу общего числа сочетаний из n[эн] по k[ка]. Составим сначала все различные сочетания из n[эн] по k[ка]. После этого произведем всевозможные перестановки элементов для каждого из таких наборов. В результате этого действия мы получим все размещения без повторений из
n[эн] по k[ка], а их общее число отображено в формуле (2.1). Так как элементов в наборе k[ка], то из одного сочетания можно получить k![ка факториал] размещений. Тогда по правилу произведения можно записать формулу (2.2). Выразив из этой формулы число сочетаний, мы получим окончательный ответ, который отображается в формуле (2.3).
Для числа всех сочетаний без повторений из n[эн] по k[ка] используются также обозначения, записанные в формуле (2.4).
Слайд 44
Рассмотрим пример, представленный на слайде. Так как нам необходимо составить комиссию из трех человек, то порядок выбранных
элементов не играет роли, а следовательно, мы имеем дело с сочетаниями без повторений.
В первом случае, если в комиссию входят любые трое из восьми человек, то число всех возможных комиссий равно числу сочетаний без повторений из восьми по три.
Рассмотрим теперь вторую ситуацию, когда в комиссию не входят члены одной семьи. Это означает, что в ней будут представлены три из четырех семей. Выбор семей, участвующих в комиссии, можно осуществить четырьмя способами. Предположим, что этот выбор уже сделан. В первой из отобранных семей можно двумя способами выбрать представителя – мужа или жену. Точно так же дело обстоит со второй и третьей семьями. По правилу произведения получаем, что число всех возможных комиссий равно тридцати двум.
Слайд 45
Пусть имеются предметы n[эн] различных типов. Сколькими способами можно составить из них комбинацию из k[ка] элементов, если не принимать во внимание порядок элементов в комбинации, но допускать, что предметы одного и того же типа могут повторяться? Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются сочетаниями с повторениями, а обозначение их общего числа записано в формуле (2.5). Рассмотрим следующий пример. Пусть имеется три элемента: a, b[а бэ] и c[це]. Из них можно составить шесть сочетаний с повторениями по два элемента: ab[а бэ],
ac[а це], bc[бэ це], aa[а а], bb[бэ бэ], cc[це це].
Таким образом, сочетание с повторениями из n[эн] элементов по k[ка], где k[ка] и n[эн] произвольные, может содержать любой элемент сколько угодно раз от 1 до k[ка] включительно или не содержать его совсем. Следует отметить, что если, например, две комбинации по k[ка] элементов отличаются друг от друга только порядком расположения элементов, то они
В первом случае, если в комиссию входят любые трое из восьми человек, то число всех возможных комиссий равно числу сочетаний без повторений из восьми по три.
Рассмотрим теперь вторую ситуацию, когда в комиссию не входят члены одной семьи. Это означает, что в ней будут представлены три из четырех семей. Выбор семей, участвующих в комиссии, можно осуществить четырьмя способами. Предположим, что этот выбор уже сделан. В первой из отобранных семей можно двумя способами выбрать представителя – мужа или жену. Точно так же дело обстоит со второй и третьей семьями. По правилу произведения получаем, что число всех возможных комиссий равно тридцати двум.
Слайд 45
Пусть имеются предметы n[эн] различных типов. Сколькими способами можно составить из них комбинацию из k[ка] элементов, если не принимать во внимание порядок элементов в комбинации, но допускать, что предметы одного и того же типа могут повторяться? Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются сочетаниями с повторениями, а обозначение их общего числа записано в формуле (2.5). Рассмотрим следующий пример. Пусть имеется три элемента: a, b[а бэ] и c[це]. Из них можно составить шесть сочетаний с повторениями по два элемента: ab[а бэ],
ac[а це], bc[бэ це], aa[а а], bb[бэ бэ], cc[це це].
Таким образом, сочетание с повторениями из n[эн] элементов по k[ка], где k[ка] и n[эн] произвольные, может содержать любой элемент сколько угодно раз от 1 до k[ка] включительно или не содержать его совсем. Следует отметить, что если, например, две комбинации по k[ка] элементов отличаются друг от друга только порядком расположения элементов, то они
не считаются различными сочетаниями. В схеме сочетаний с повторениями имеют дело не с элементами, а с их видами. При этом считается, что имеется неограниченное число элементов каждого вида, т. е. достаточное для выбора любого числа элементов. Формула (2.6) показывает, как можно определить число сочетаний с повторениями из n[эн] элементов по k[ка].
Рассмотрим примеры применения данной формулы. В первом примере
n[эн] равно четырем, поскольку мы имеем четыре сорта предметов – А, Т, Г,
Ц. Значение k[ка] равно трем. Поэтому мы находим число сочетаний с повторениями из четырех по три.
Обратимся ко второму примеру, представленному на слайде. Каждому способу деления яблок между ребятами поставим в соответствие сочетание с повторениями следующим образом. Типами элементов будут ребята, а элементами – яблоки. Таким образом, имеем три типа элементов, из которых предстоит составить различные наборы объема шестьдесят три. Наличие в наборе элемента определенного типа означает принадлежность данного яблока соответствующему мальчику. Применяя формулу для числа сочетаний с повторениями при n[эн], равном трем, и k[ка] равном четырем, получаем общее число способов распределения яблок между ребятами.
Слайд 46
И последней комбинаторной схемой являются перестановки с повторениями. Задача формируется следующим образом. Имеется n[эн] предметов, среди них n
1
[эн один] элементов первого вида, n
2
[эн два] элементов второго вида и т. д., n
k
[эн катое] элементов k-го[катого] вида, причем выполняется соотношение (2.7). Упорядоченные наборы длины n[эн], составленные из этих элементов, называются перестановками с повторениями. Обозначение общего числа перестановок с повторениями показано в формуле (2.8).
Поясним формулу для вычисления числа перестановок с повторениями.
Количество таких перестановок получается из общего числа перестановок
Рассмотрим примеры применения данной формулы. В первом примере
n[эн] равно четырем, поскольку мы имеем четыре сорта предметов – А, Т, Г,
Ц. Значение k[ка] равно трем. Поэтому мы находим число сочетаний с повторениями из четырех по три.
Обратимся ко второму примеру, представленному на слайде. Каждому способу деления яблок между ребятами поставим в соответствие сочетание с повторениями следующим образом. Типами элементов будут ребята, а элементами – яблоки. Таким образом, имеем три типа элементов, из которых предстоит составить различные наборы объема шестьдесят три. Наличие в наборе элемента определенного типа означает принадлежность данного яблока соответствующему мальчику. Применяя формулу для числа сочетаний с повторениями при n[эн], равном трем, и k[ка] равном четырем, получаем общее число способов распределения яблок между ребятами.
Слайд 46
И последней комбинаторной схемой являются перестановки с повторениями. Задача формируется следующим образом. Имеется n[эн] предметов, среди них n
1
[эн один] элементов первого вида, n
2
[эн два] элементов второго вида и т. д., n
k
[эн катое] элементов k-го[катого] вида, причем выполняется соотношение (2.7). Упорядоченные наборы длины n[эн], составленные из этих элементов, называются перестановками с повторениями. Обозначение общего числа перестановок с повторениями показано в формуле (2.8).
Поясним формулу для вычисления числа перестановок с повторениями.
Количество таких перестановок получается из общего числа перестановок
уменьшением во столько раз, сколько раз можно по-разному переставить сначала предметы первого вида, затем предметы второго вида и т. д., наконец, предметы k-го[катого] вида. В результате получаем формулу (2.9).
Рассмотрим следующий пример. В слове «Уссури» две буквы «у», две буквы «с», одна буква «р» и одна буква «и». Используя формулу для перестановок с повторениями, получаем, что общее число перестановок букв данного слова равно ста восьмидесяти.
Слайд 47
Подведем итог изучения всех комбинаторных схем.
Мы рассмотрели два основных вида схем – это размещения и сочетания. Перестановки являются частным случаем размещений, когда k[ка] равно n[эн]. Размещения характеризуются тем, что в них учитывается порядок расположения элементов. К сочетаниям относятся наборы, которые отличаются друг от друга только входящими в них элементами, а не их порядком.
Для правильного выбора комбинаторной схемы и формулы для решения задачи необходимо ответить на два ключевых вопроса. Они представлены на слайде. Если при ответе на первый вопрос мы говорим «да», то в задаче необходимо использовать размещения. В случае ответа «нет» – используем сочетания. В зависимости от ответа на второй вопрос мы применяем формулы для схем с повторением или без них.
Рассмотрим несколько примеров применения комбинаторных схем.
Первый из них представлен на слайде.
Для назначения патруля нам необходимо выбрать трех солдат из имеющихся тридцати, а затем одного офицера из трех. При каждом выборе для нас не имеет значения порядок и повторения, конечно же, здесь исключаются. Поэтому как в случае выбора солдат, так и в случае выбора офицера мы должны использовать формулу для сочетаний без повторений.
Рассмотрим следующий пример. В слове «Уссури» две буквы «у», две буквы «с», одна буква «р» и одна буква «и». Используя формулу для перестановок с повторениями, получаем, что общее число перестановок букв данного слова равно ста восьмидесяти.
Слайд 47
Подведем итог изучения всех комбинаторных схем.
Мы рассмотрели два основных вида схем – это размещения и сочетания. Перестановки являются частным случаем размещений, когда k[ка] равно n[эн]. Размещения характеризуются тем, что в них учитывается порядок расположения элементов. К сочетаниям относятся наборы, которые отличаются друг от друга только входящими в них элементами, а не их порядком.
Для правильного выбора комбинаторной схемы и формулы для решения задачи необходимо ответить на два ключевых вопроса. Они представлены на слайде. Если при ответе на первый вопрос мы говорим «да», то в задаче необходимо использовать размещения. В случае ответа «нет» – используем сочетания. В зависимости от ответа на второй вопрос мы применяем формулы для схем с повторением или без них.
Рассмотрим несколько примеров применения комбинаторных схем.
Первый из них представлен на слайде.
Для назначения патруля нам необходимо выбрать трех солдат из имеющихся тридцати, а затем одного офицера из трех. При каждом выборе для нас не имеет значения порядок и повторения, конечно же, здесь исключаются. Поэтому как в случае выбора солдат, так и в случае выбора офицера мы должны использовать формулу для сочетаний без повторений.
Число различных способов выбора солдат равно числу сочетаний из тридцати по три.
Количество вариантов выбора офицера равно числу сочетаний из трех по одному.
В соответствии с правилом произведения мы должны перемножить два указанных выше числа. Записывая соответствующие дробные выражения и проводя вычисления, мы получаем общее количество способов назначения патруля.
Слайд 48
Перейдем к рассмотрению второго примера. Текст задачи представлен на слайде.
Нам необходимо разбить восемь человек на две команды по четыре человека. Другими словами, нужно выбрать четыре человека в первую команду. Тогда четверо оставшихся автоматически попадут во вторую команду. В данном случае порядок нам неважен и повторений быть не может. Поэтому следует использовать формулу для сочетаний без повторений.
Необходимо учесть и ограничение, состоящее в том, что в каждой команде должно быть не менее одного юноши. Если в одной команде будет один юноша, то во вторую попадут двое других.
Таким образом, нам необходимо выбрать одного юношу и трех девушек. Можно, наоборот, выбрать двух юношей и двух девушек.
Результат, естественно, будет одинаковый. В решении, представленном на слайде, реализован первый случай. Число способов выбора одного юноши из трех равно числу сочетаний из трех по одному. Число вариантов выбора трех девушек из пяти равно числу сочетаний из пяти по три. Согласно правилу произведения мы перемножаем указанные числа и получаем требуемый результат.