close

Вход

Забыли?

вход по аккаунту

?

Popv Mikhailov

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ДИСКРЕТНАЯ МАТЕМАТИКА.
МНОЖЕСТВА. КОМБИНАТОРИКА.
Методические указания для студентов заочной
формы обучения
Санкт-Петербург
2014
Составители: доцент, канд.техн.наук В.П.Попов, профессор, д-р
техн.наук В.В.Михайлов
Рецензент: доцент, канд. техн. наук, Н.В.Соловьев
Методические указания по дисциплине «Дискретная математика« включают разделы «Теория множеств» и «Комбинаторика» с вариантами заданий для самоконтроля.
Предназначены для студентов заочной формы обучения
по направлению 230100.62 «Информатика и вычислительная
техника» Ивангородского гуманитарно-технического института (филиала) ФГАОУ ВПО «Санкт-Петербургский государственный университет
аэрокосмического приборостроения».
Подготовлено на кафедре прикладной математики и информатики Ивангородского гуманитарно-технического института
(филиала) ФГАОУ ВПО «Санкт-Петербургский государственный университет аэрокосмического приборостроения».
В авторской редакции
Компьютерная верстка Ю.А. Гайнутдинова
Подписано к печати 14.03.14. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 2,33.
Тираж 100 экз. Заказ № 126.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2014
ПРЕДИСЛОВИЕ
Разделы дискретной математики – теория множеств и комбинаторика тесно связаны друг с другом. Первый раздел учебно-методического издания посвящен представлениям в области классической
теории множеств, которая является основой таких областей математики как комбинаторика, теория групп, отображения, перестановки, преобразования, топология, общая алгебра и др. Определённые представления в области теории множеств позволяют лучше
усвоить второй раздел пособия – комбинаторику. Комбинаторика
ориентирована на решение задач выбора и расположения элементов
некоторых множеств. Во втором разделе рассмотрены задачи традиционной комбинаторики – размещения, перестановки, сочетания,
раскладки, разбиения. Отдельные (весьма немногочисленные) примеры могут вызвать некоторые затруднения, но они будут преодолены если не при первом, то при повторном чтении данного учебнометодического издания. Учебно-методическое издание подготовлено в соответствии с требованиями ФГОС и программой дисциплины
«Дискретная математика «, разработанной в ГУАП.
3
1. Элементы теории множеств
1.1. Понятие множества
В математике часто интересуются не отдельными объектами,
а целыми классами объектов, например:
− совокупность всех целых чисел;
− совокупность всех натуральных чисел;
− совокупность всех простых чисел;
− совокупность всех треугольников;
− совокупность всех букв и т.д.
Иногда, такие совокупности состоят из бесконечного
(беcчисленного) множества отдельных элементов. Математики всегда интересовались понятием бесконечности. Но первые попытки изучения бесконечности привели к многочисленным парадоксам. Например, парадоксы Зенона (греческий философ). Первый парадокс –
парадокс летящей стрелы (невозможность движения): чтобы стрела
пролетела какой-то путь, сначала она должна преодолеть половину
пути. Но прежде чем преодолеть полпути, надо преодолеть четверть
пути, восьмую часть пути, шестнадцатую часть и т.д. Так как процесс деления пополам никогда не кончится (вот она бесконечность),
то стрела никогда не сможет сдвинуться с места. Второй парадокс –
сможет ли Ахиллес догнать Черепаху?
Прежде чем знакомиться со свойствами множеств, надо определить :
а) что такое множество;
б) какие действия можно выполнить над ними.
К сожалению, основному понятию теории множеств – понятию
«множества» – дать точное, строгое определение не возможно.
Понятия «элементы» и «множество» считаются общеизвестными и не определяются. Разумеется, можно было бы сказать, что
«множество» это:
а) – «совокупность» элементов (тогда надо дать определение «совокупности»). Например, «совокупность» – это набор элементов, что
в свою очередь потребует определения термина «набор» и т.д. Такие
вложенные определения будут повторяться до бесконечности.
б) – «собрание» элементов – те же проблемы.
в) – «система», «класс» – те же проблемы.
Это всё не математические определения, а использование словарного богатства русского языка (его избыточности). Чтобы определить
4
какое–либо понятие, надо указать, частным случаем какого, более
широкого понятия является определяемое понятие. Для понятия
множества это не возможно, т.к. оно само является наиболее широким и не в каких других понятиях не содержится. Точно таким
же неопределяемым понятием является термин «элемент«. Часто,
некоторые объекты объединены некоторым общим признаком, например:
– множество стульев в комнате,
– множество всех клеток человеческого тела,
– множество картофелин в данном мешке,
– множество студентов конкретной группы.
Для того ,что бы указать ,что данное множество M состоит из элементов а обычно пишут :
M = {а}.
Здесь фигурные скобки { } обозначают, что элементы а объединены в одно целое – множество M. Например, а – каждый студент
конкретной группы, M – множество студентов конкретной группы.
Факт принадлежности элемента а множеству M записывают
с помощью символа ∈, т.е. а∈M.
Читается эта запись т.о. «элемент а принадлежит множеству M».
Если же элемент b не принадлежит множеству M ,то пишут либо
b Ï M, либо b Î M.
Например, M – множество четных чисел, тогда 4∈M, а 3 Ï M.
Основатель теории множеств – немецкий математик Георг Кантор, создал её приблизительно в 1870 г.
Если множество содержит конечное число элементов, его именуют конечным, а если в нем бесконечно много элементов, то именуют бесконечным. Например, множество деревьев парка – конечное,
а множество точек на окружности – бесконечно.
Мощность множества M – это число его элементов. Обозначается
мощность |M|.
1.2. Способы задания множества
Как задают множества? Существуют различные способы задания множеств.
Один из них – дать полный список элементов, входящих в множество. Но этот способ применим только к конечным множествам
(да и то не ко всем).
5
Примеры задания множеств:
1) Первый способ – задать множество перечислением его элементов (самый простейший способ). Например, множество студентов данной группы определяется их списком в групповом журнале:
а,b,с,d,е∈M, множество стран на земном шаре определяется их списком в географическом атласе мира, множество элементов таблицы
Менделеева.
Перечислительный, или явный способ задания множеств, неудобен в случае, когда элементов множества очень много, и совсем
непригоден для задания бесконечных множеств. Кроме того, даже
в тех случаях, когда явное задание множества является возможным
и легким, но оно затуманивает сам смысл рассматриваемого множества, и скрывает причины, побудившие нас объединить в одно множество именно эти, а не другие элементы. Гораздо более распространен иной, неявный или описательный способ задания множеств.
2) Второй способ задания множеств, когда множество нельзя задать списком, – указать некоторое характеристическое свойство, которым обладают элементы множества, т.е. сформулировать правило
определения принадлежности элемента множеству. Например:
– множество синтаксических ошибок в тексте программы;
– множество натуральных чисел (числа целые, положительные
и 0) Z + ;
– множество целых чисел Z;
– множество всех действительных чисел R.
По второму способу, в приведённых примерах, мы задали все
множества общими свойствами их элементов. Другие примеры задания множеств по второму способу:
а) множество M – это решения тригонометрического уравнения вида
π
sin x = 1 ® x = + 2πn,
2
где n – произвольный элемент множества Z (множества целых чисел);
б) множество групп первого курса какого либо факультета MГ.
Каждый элемент множества MГ является множеством конкретных
студентов, т.е. MГ является множеством множеств.
Бесконечные множества можно задавать только описательным
способом.
Любая совокупность элементов некоторого множества M
именуется подмножеством. Это же понятие возникает каждый раз,
6
когда приходится рассматривать множество не как самостоятельное,
а как часть другого, более широкого множества. Если множество
В является подмножеством другого множества А, т.е. каждый
элемент х из множества В является и элементом множества А, то
в этом случае пишут B Ì A или A É B.
Эти два соотношения имеют один и тот же смысл: множество А
содержит множество В в качестве своей части. Чисто внешне, эти
соотношения близки к записям и В < А и А > В.
1.3. Основные операции над множествами
В приложениях дискретной математики часто приходится из нескольких множеств образовывать новое множество. Операции, выполняемые над множествами, следующие:
1) объединение (сумма) множеств – это образование единого (целого) множества из нескольких множеств. Объединением (суммой)
нескольких множеств А, В, … называют новое множество, состоящие из тех и только тех элементов, которые входят хотя бы в одно
из слагаемых множеств. Символ объединения множеств  или + ,
соответственно объединение (сумму) множеств А и В, обозначают
A  B или А + В.
Следует отметить, что отдельные элементы могут входить не
только в одно, а в несколько объединяемых (слагаемых) множеств.
В этом случае всё равно они входят в сумму только один раз. Поэтому, для конечных множеств число элементов суммы может оказаться меньше, чем сумма числа элементов слагаемых множеств.
Это можно представить геометрически
(рис. 1). Пусть множество А состоит из точек фигуры, заштрихованной горизонA
тальными линиями, а множество В состоит из точек фигуры заштрихованной
B
наклонными линиями, тогда множество
А + В или A  B, т.е. их объединение, составляет вся заштрихованная фигура.
Рис. 1
Очевидно, что операция объединения
(сложения) множеств обладает многими
свойствами сложения чисел. Так, выполняются:
а) переместительный закон (коммутативный)
А + В = В + А;
7
б) сочетательный закон (ассоциативный)
А + (В + С) = (А + В) + С.
Множества А + (В + С) или (А + В) + С можно обозначить и без
скобок:
А + В + С,
т.к. сумма их представляет объединение всех трёх множеств А,B
и С. Геометрически это выглядит т.о. (рис. 2),т.е. объединение множеств А,В и С – это вся заштрихованная область.
В алгебре множеств есть особые множества:
– пустое множество;
A
– множество – единица.
Пустое множество обозначается букB
вой Æ , похожей по написанию на число ноль 0 (именуется оно иногда нульC
множеством). Пустое множество такое,
сложение (объединение) с которым не
должно изменять ни одного множества.
Это означает, что множество Æ не содерРис. 2
жит ни одного элемента, т.е. является пустым.
Иногда появляется мысль вовсе исключить из рассмотрения подобное пустое множество: ведь если оно не содержит элементов, то
это вообще не множество (и нечего о нём говорить). Однако, поступать так, было бы подобным исключению числа 0 из совокупности
чисел: ведь набор из нуля предметов так же является пустым набором и говорить о числе предметов, содержащихся в этом наборе, как
будто бессмысленно. Но на самом деле это совсем не бессмысленно,
а очень даже осмысленно. Если бы мы не имели числа 0 ,то не могли
бы вычесть одно из другого любую пару чисел, например 3-3. При
отсутствии числа 0 эта разность вообще бы ничему не равнялась.
Нам было бы трудно записывать в позиционной десятичной системе
счисления, скажем, число 10810 – одна сотня, восемь единиц и совсем никаких десятков.
И ещё многое мы не смогли бы сделать, поэтому идея возникновения
нуля считается одним из выдающихся (замечательных) событий во
8
всей истории арифметики. Поэтому, если множество Æ – пустое
множество, то для любого множества А: А + Æ = А.
Несколько сложнее обстоит дело с «множеством-единицей». Это
множество будем обозначать буквой I, похожей по написанию на число 1. Множество-единица – это универсальное множество, его смысл
аналогичен роли единицы. Значение этого множества мы оценим после того, как рассмотрим операцию пересечения (произведения) множеств. Рассмотрим несколько примеров объединения множеств. Пусть
два множества имеют элементы M1 = {a,b,c,d}, M2 = {b,c,e,p}.
Их объединение будет множество M3, элементы которого: M3 =
= M1 + M2 или M3 = M1  M2 = {a b,c,d,e,p}.
Пусть – M1, множество студентов (юношей) группы, – M2 множество студеток (девушек) группы.
Тогда M1  M2 будет множество всех обучающихся в этой группе.
2) Вторая операция над множествами – пересечение (произведение, умножение) множеств. Пересечением множеств А и В называют новое множество, содержащее те и только те элементы, которые
входят в каждое из множеств А и В. т.е. пересечение множеств – это
общая часть этих множеств. Обозначение пересечения множеств –
символ  или A∙B (как в алгебре).
Геометрический смысл этой операции (рис. 3) следующий: если
множество А состоит из точек фигуры заштрихованной горизонтальными линиями, а множество В – состоит из точек фигуры ,заштрихованной наклонными линиями ,то пересечением этих множеств А∙В или А  В будет фигура из горизонтальных и наклонных
линий (т.е. покрытая решеткой).
Кстати, название операции «пересечение» происходит от того
,что при пересечении двух геометрических фигур, получают множество точек пересечения обоих фигур в самом обычном смысле
этого слова. Т.к. пересечением множеств является новое множество,
элементами которого будут элементы, принадлежащие одновременно как одному, так и другому множеству, то для множеств M1 и M2 предидущего примера M4 = M1  M2, или M4 =
M1∙M2, или M4 = {b,c}.
À
Если имеются два множества M1 =
B
= {a,b,c,d,e} и В = {1,2,3}, то их пересечение
не содержит ни одного общего элемента,
Рис. 3
9
точнее содержит пустое множество элементов, и это будет записываться
так: M1  B = Æ .
Например, пусть А – множество умеющих играть в шахматы
в студенческой группе, а В – множество пловцов (умеющих плавать)
в этой же группе, тогда А∙В или А  В есть множество тех шахматистов, которые умеют плавать.
Для пересечения (умножения) множеств выполняются:
а) переместительный (коммутативный) закон А∙В = В∙А или А  В=
= В  А,
т.е. понятно ,что «множество А∙В это множество шахматистов,
которые умеют плавать», и «множество плавцов, которые умеют
играть в шахматы» – это одно и тоже множество.
б) столь же очевидно, что для пересечения (умножения) множеств справедлив сочетательный (ассоциативный) закон, т.е. для
любых трёх множеств А, В, и С: (А∙В)∙С = А∙(В∙С), любое из этих множеств можно обозначить просто А∙В∙С.
Геометрически (рис. 4) это означает, что при пересечении трёх
множеств А,В,С, множество А∙В∙С покрыто тройной штриховкой.
в) для любых трёх множеств А,В и С выполняется также распределительный (первый дистрибутивный) закон: (А + В)∙С = А∙С + В∙С.
Вернёмся к особым множествам – пустое множество и множество-единица. Если бы не причислять к числу множеств пустое
множество Æ , то мы не смогли бы указать пересечения любых двух
множеств, например таких, как представлено на рис. 5.
Пересечение множеств А и В пустое, как например множество
студентов в группе и множество слонов. Вот почему мы писали
А + Æ = А.
A
B
C
Рис. 4
10
À
B
Рис. 5
Вернёмся к множеству-единице I.
Это множество такое ,что пересечение
(произведение) его и любого множества
А совпадает с А. Это множество I должно
содержать вообще все элементы всех
множеств. В таком случае под I будем
Рис. 6
понимать «самое большое множество»,
содержащее все рассматриваемые нами
элементы (предметы) в предыдущих множествах (множество студентов
в группе, множество всех элементов в таблице Менделеева, множество
всех точек квадрата). Это особое множество I (рис. 6) в алгебре множеств
называется единичным или универсальным множеством.
Очевидно ,что для любого множества из «меньших множеств»,
например А (даже если А совпадает с I), мы будем иметь: А∙I = А
и А + I = I.
В этом глубокое отличие единичного множества от числа 1. Какое
бы множество А мы не сложили (объединили) с единичным, получим
тоже множество I, т.к. по определению множество I является «самым
большим» и поэтому увеличить ещё его уже невозможно. В заключение отметим ещё два закона алгебры множеств, противоречащих представлениям, полученным при изучении элементарной алгебры. Очевидно ,что каким бы ни было множество А, объединение его со вторым
таким же множеством, совпадает с исходным множеством А. Точно также, пересечение множества А с самим собой, тоже совпадает с исходным множеством А, т.е. А + А= = А. Эти два последних равенства называют идемпотентным законом (законом идемпотентности).
Как мы видим, в алгебре множеств действуют законы во многом
похожие на знакомые нам из курса школьной математики законы
алгебры, относящиеся к числам, но они не дублируют полностью
числовые законы. т.е. в алгебре множеств, как мы увидим, имеют
место почти все основные законы, справедливые для чисел, но вместе с ними в ней выполняются и другие законы, которые вероятно
могут показаться необычными. Например, в алгебре чисел а + 1≠1,
а в алгебре множеств всегда А + I = I, А∙I = А.
Совершенно новыми для нас являются законы идемпотенции,
т.е. А + А = А, А∙А = А. Эти законы иногда выражают в виде утверждения о том, что в алгебре множеств нет ни показателей степени, ни
коэффициентов:
À × À ×
À
× À ×¼.×
À = À,
À + À + À + À +¼. + À = À, 

I
n ðàç
n ðàç
11
каким бы не было множество А и число n. Поэтому, например, если
В – подмножество в А, т.е. В Ì А, то справедливы равенства В∙А = В
и В + А = А.
Весьма своеобразно «раскрытие скобок» в алгебре множеств – об
этом говорит второй дистрибутивный закон – в алгебре множеств,
всегда (т.е. при любых множествах А,В, и С) имеет место равенство
А∙В + С = (А + С)∙(В + С),
хотя с точки зрения чисел это равенство неправильное («неполное»).
Приведем графическую иллюстрацию второго дистрибутивного закона. На рис. 7 штриховкой с правым наклоном покрыто пересечение
А∙В множеств А и В, а штриховкой с левым наклоном множество С. Вся
заштрихованная фигура (с левыми и правыми наклоном) изображает множество А∙В + С.
На рис. 8 горизонтальными линиями заштриховано объединение
двух множеств А и С, т.е. А + С, а вертикальными линиями заштриховано объединение двух множеств В и С, т.е. В + С.
«Cеткой» покрыто на рис. 8 пересечение (А + С)∙(В + С) этих двух
объединений. Легко увидеть, что фигура покрытая на рис. 8 сеткой
(из горизонтальных и вертикальных линий) в точности совпадает
с заштрихованной на рис. 7 ,что и доказывает второй дистрибутивный закон. Примеры действия этих двух законов.
Пример 1.
B
B
А
А
С
С
Рис. 7
12
Рис. 8
À×
À + Ñ )× ( Â + Ñ )
(


= À × ( À × Â + Ñ) =
âòîðîé äèñòðèáóòèâíûé çàêîí
=
À× À

× Â + À × Ñ = À × Â + À × Ñ. èäåìïîòåíòíîñòü
Пример 2. А∙(А + В) = А∙А + А∙В = А + А∙В = А∙I + A∙B = A∙(I + B) = A∙I = A.
Пример 3. А∙В + А = А∙В + А∙I = А∙(В + I) = А∙I = А.
Именно это отличие законов алгебры множеств от законов алгебры чисел, во многих учебниках по дискретной математике стало
причиной того, что объединение (сложение) множеств и пересечение
(умножение) множеств обозначаются не обычными алгебраическими знаками «+» и «∙», а совершенно иначе (т.е. другой символикой):
– объединение множеств А и В обозначают A  B,
– пересечение множеств А и В – через A  B.
1.4. Разбиение множеств
Часто некоторое множество является суммой своих подмножеств, но никакие два из этих подмножеств не имеют общих
элементов (т.е. эти подмножества не пересекаются). В этом случае говорят, что множество А разбито на непересекающиеся подмножества. Разбиение на такие подмножества часто полезно для
классификации объектов. Например, составляют каталог книг
(множество книг) в библиотеке. Сначала книги разбиваются на
подмножества:
– художественная литература;
– книги по общественно политическим наукам;
– книги по естественным наукам;
– книги по техническим наукам и т.д.
После этого подмножества разбиваются на более мелкие подмножества:
– художественную литературу разбивают на прозу и поэзию;
– книги по общественным наукам – на книги по философии, политической экономии, культурологии и т.д.;
– книги по естественным наукам – на книги по физике, математике и т.д.
Такое разбиение позволяет быстро найти нужную книгу. Очевидно, что одно и то же множество можно разбивать на подмноже13
ства разными способами. Например, для одного и того же множества книг в библиотеке составляется алфавитный каталог, т.е. множество книг разбивается на подмножество книг, авторы которых
имеют фамилии начинающиеся на букву А, на подмножество книг,
фамилии авторов которых начинаются на букву Б и т.д. После этого
каждое полученное подмножество разбивают в соответствии со второй буквой фамилии и т.д.
При разбиении множества на подмножества часто используют понятие эквивалентности элементов. Для этого определяют,
что значит «элемент х эквивалентен элементу у», после чего объединяют эквивалентные элементы в одно подмножество. Для понятия эквивалентности должны выполняться три следующих
условия:
а) каждый элемент сам себе эквивалентен;
б) если элемент х эквивалентен элементу у, то элемент у эквивалентен элементу х;
в) если х эквивалентен у и у эквивалентен z, то элемент х эквивалентен z.
1.5. Вычитание множеств
Там где есть сложение (объединение), обычно существует и вычитание. Не являются в этом смысле исключением и множества.
Разностью множеств А и В называют новое множество А–В, в которое входят все элементы множества А, не принадлежащие множеству В. На рис. 9 разность А–В это множество точек заштрихованной области (серповидной фигуры) без дуги MN, А–В = А–А∙В.
При этом совсем не обязательно, чтобы множество В было частью множества А. Если В не является частью А, то вычитание В из А
сводится к удалению из А общей чаM
сти А и В. Например:
.
А – множество всех обучающихся
в группе,
B
В – множество студенток в этой
A
группе,
.
А–В – множество студентов (юноN
шей) в группе.
В том случае, если множество В
Рис. 9
является частью множества А, то
14
А–В называют дополнением к множеству В
Bʹ
в А. Условно обозначается это таким образом
BA′.
AB
Например:
– дополнением множества четных чисел
в множество всех целых чисел является множество нечетных чисел;
– дополнением множества студенток В
Рис. 10
в группе в множество А всех обучающихся
в этой же группе, является BA, т.е. число студентов – юношей.
Дополнение множества В в универсальное единичное множество I
(рис. 10), вместо BI′ пишут просто B′.
Следует обратить внимание на то, что некоторые формулы алгебры
чисел перестают быть верными для вычитания множеств. Так, например, в алгебре множеств (A + B) – – C≠A + (B – C) Почему? В самом деле, если все три множества совпадают, т.е. А = В = С, то левая часть
является пустым множеством, а правая часть – множество А, и Æ ≠А.
1.6. Прямое произведение множеств
Прямым произведением множеств А и В (обозначается произведение AxB) являются множество всех пар a∙b, где a ∈ A, b ∈ B.
Например,
A = {a,b,c} и B = {1,2}.
Элементами прямого произведения этих множеств будут
AxB = {a∙1,a∙2,b∙1,b∙2,c∙1,c∙2}
Пусть А – конечное множество, элементами которого являются
символы (буквы, цифры, знаки препинания, знаки операций). Такое множество символов называется алфавитом. Элементы множества An именуются словами длиной n в алфавите А (т.е. число символов n в слове – длина слова). Всё множество слов в алфавите А может
быть односимвольными словами – A1, двухсимвольными словами –
A2 и т.д. Поэтому, множество всех слов в алфавите А – это множество, являющееся объединением A1  A2  A3  … An.
Рассмотрим две полезные теоремы:
1) пусть A1,A2,A3,A4…,An – конечные множества, каждое из которых имеет свою мощность |Ai| = Mi.
Тогда мощность прямого произведения A1∙A2 ∙A3∙∙ … ∙ An равна произведению мощностей этих множеств M1∙M2∙M3∙…∙Mn, для n = 1 это
утверждение очевидно.
15
2) если для конечного множества А, его мощность |A| = n, то число
всех подмножеств множества А равно 2n. Например, для множества
A = {a,b,c} его мощность |A| = 3. Подмножества, т.е. слова в этом алфавите, будут следующие:
– {Æ }
– {a}
– {b}
– {c}
– {a∙b}
– {a∙c}
– {b∙c}
– {a∙b∙c}
т.е. 23 = 8.
Слова единичной длины отождествляются с буквами алфавита.
Все подмножества включают слова положительной длины (т.е. состоящие не менее чем из одной буквы) а так же и пустое слово – не
содержащее ни одной буквы
16
2. Алгебра множеств
2.1. Основные законы алгебры множеств
Мы познакомились с действиями над множествами и некоторыми свойствами (иногда необычными) этих действий. Приведём
в виде таблицы (табл. 1) список всех основных свойств действий над
множествами, и в этом списке, как и ранее, обозначим через Æ – пустое множество, I – единичное (универсальное) множество, А′ – дополнение множества А в универсальное множество I.
Таблица 1
Номер
свойства
Свойства действий над множествами
Примечания
1
A⊂A
А содержит множество А
2
3
4
если A ⊂ B и B ⊂ A, то A = B
если A ⊂ B и B ⊂ C, то А ⊂ С
5
6
A⊂I
A+B=B+A
7
A∙B = B∙A
8
A + (B + C) = (A + B) + C
9
A∙(B∙C) = (A∙B)∙C = (A∙C)∙B
10
A+A=A
11
A∙A = A
12
A∙ (B + C) = A∙B + A∙C
13
A + B∙C = (A + B) (A + C)
Æ⊂A
Коммутативный закон для
сложения (объединения) множеств
Коммутативный закон для
умножения (пересечения)
множеств
Ассоциативный закон для
сложения (объединения) множеств
Ассоциативный закон для
умножения (пересечения)
множеств
Идемпотентный закон для
сложения (объединения) множеств
Идемпотентный закон для
умножения (пересечения)
множеств
Первый дистрибутивный закон для множеств
Второй дистрибутивный закон
для множеств
17
Окончание табл. 1
Номер
свойства
Свойства действий над множествами
Примечания
14
Свойство пустого множества
15
A+ Æ =A
A∙I = A
16
A+I=I
17
A∙ Æ = Æ
Если А ⊂ B (A подмножество
в B), то A + B = B и A∙B = A
18
19
20
A + A′ = I
21
Æ′=I
22
I′= Æ
(A′)′ = A
Соотношение A ⊂ B (множество A содержится в B)
эквивалентно B ′⊂ A′
(A + B) ′ = A ′∙ B′
(A∙B)′ = A ′ + B ′
Свойство единичного множества
Свойство единичного множества
Свойство пустого множества
Смотри рис. 11
A∙A′ = Æ
23
24
25
26
Смотри рис. 12
С помощью свойств 1…26 (табл. 1) можно выполнять действия
над множествами аналогично тому, как в алгебре выполняют действия над числами.
Полезно знать:
1) А∙В = (A′ + B′)′, по свойству 26.
Bʹ
B
A
Aʹ
B
A
Рис. 11
18
Рис. 12
2) (A′ + B′)′ + (A′ + B)′ = A, т.к. (A′ + B′)′ = A∙B и (A′ + B)′ = (A′)′∙B′,
тогда A∙B + A∙B′ = A∙(B + B′) = A∙I = А. Все эти свойства (табл. 1) можно легко доказать через две операции над множествами – сложение
(объединение) и образование дополнения.
2.2. Упражнения
Доказать следующие равенства, в которых большими буквами
обозначены множества (буква Æ всегда обозначает пустое множество, а буква I – единичное множество):
1. (A + B)∙(A + C) (B + D)∙(C + D) = A∙D + B∙C
2. A∙(A + B) = A
3. A∙B + A = A
4. A∙(A + C)∙(B + C) = A∙B + A∙C
5. A∙(A + I)∙(B + Æ ) = A∙B
6. (A + B)∙(B + C)∙(C + A) = A∙B + B∙C + C∙A
7. (A + D)∙(B + D) ∙ (C + D) = A∙B∙C + D
8. (A + B)∙(B + C)∙(C + D) = A∙C + B∙C + B∙D
9. (A + B)∙(A + I) + (A + B)∙(B + Æ ) = A + B
10. (A + B)∙(B + I)∙(A + Æ ) = A
11. (A + B + C)∙(B + C + D)∙(C + D + A) = A∙B + A∙D + B∙D + C
19
3. Элементы комбинаторики
Комбинаторика – раздел математики, посвященный способам
подсчета элементов в конечных множествах. Эти множества обычно
называют комбинаторными конфигурациями или выборками. Проблема подсчета комбинаторных конфигураций широко используется в приложениях – в теории сложности вычислений, при решении
задач теории вероятностей, кодировании, в математической логике,
теории автоматов. Каждая из таких задач требует ответа на вопрос –
сколько имеется заданных комбинаторных конфигураций? Важными задачами комбинаторики являются задачи разработки алгоритмов построения комбинаторных конфигураций, а также нахождения конфигураций, характеризующихся экстремальным значением некоторых параметров. Основная проблема в решении комбинаторных задач заключается в нахождении типовых формул, законов
и правил комбинаторики, которые подходили бы к условию задачи –
к чему сводится задача, к какому закону или правилу. При этом может потребоваться декомпозиция исходной задачи, чтобы к частным
задачам могли быть применены известные формулы. Предлагаемые
в методических указаниях задачи, в большинстве сводятся к типовым формулам и правилам (правило включения-исключения, декартово произведение, перестановки и т.п.). Рассмотрим примеры решения задач с применением тех или иных формул и правил.
3.1. Основные понятия и формулы комбинаторики
При решении задач комбинаторики важную роль играют два правила. Первое – правило умножения. Пусть требуется выполнить одно за другим два действия, причем первое можно выполнить n способами, а второе – k способами. Тогда общее количество способов, которыми можно выполнить эти действия равно n∙k. В общем случае
при m действиях, первое из которых можно выполнить k1 способом,
второе – k2 и т. д., общее количество способов, которыми можно совершить m действий равно:
m
Nm = Õ ki .
i=1
Правило умножения соответствует введенной ранее операции
прямого произведения множеств, если элементы множеств
отождествить со способами выполнения действий. Эта операция
20
называется также декартовым произведением множеств, а если
множества имеют одинаковую мощность – то декартовой степенью.
Пример 1. Имеется 4 города: А, В, С, и D. Из города А в В ведут
3 дороги, из В в С – 5 дорог, из С в D – только 2 дороги. Сколькими
путями можно проехать из города А в город D? Для решения данной
задачи можно использовать правило умножения. Действительно,
выбрав одну из 3-х дорог на пути из А в В мы затем последовательно
сталкиваемся с выбором дороги из В в С и из С в D. Общее количество вариантов проезда будет равно N = 3x5x2 = 30.
Пример 2. Определить количество вариантов S для N последовательных выборок карт из колоды. Количество вариантов для первой
выборки (количество элементов множества) равно 52, Если карта
возвращается в колоду, то для всех последующих выборок количество вариантов 52, если карта не возвращается, то вариантов 51, 50
и т.д. Величина S равна произведению мощности множеств всех N
последовательных выборок.
Второе правило – правило сложения. Зададим два действия, первое из которых можно выполнить n способами, второе – k способами. Тогда общее количество способов, которыми можно совершить
действия, равно n + k. В общем случае при m действиях, первое из
которых можно выполнить k1 способом, второе – k2 и т. д., общее количество способов, которыми можно совершить m действий равно:
m
Nm = å ki .
i=1
Правило сложения можно отождествить с правилом объединения
непересекающихся конечных множеств, если элементами множеств
являются способы выполнения действий.
Пример 3. Рассмотрим условие предыдущей задачи, но сформулируем вопрос так: какое количество вариантов выбора путей будет у
водителя, следующего из города А в D через города В и С? Задача решается с использованием правила сложения. При выезде из города
А водитель должен выбрать одну из 3 дорог, из города В – одну из 5,
из города С – одну из 2-х. Ни одна из дорог не совпадает с другой. Общее количество вариантов выбора равно N = 3 + 5 + 2 = 10.
Помимо прямого использования, правила умножения и сложения позволяют правильно организовать решение комплексных задач комбинаторики в соответствии с особенностями взаимосвязи отдельных частных задач. Эти частные задачи будут служить аргументами указанных операций.
21
3.1.1. Правило суммы
Пусть А и В – конечные непересекающиеся множества, тогда
мощность их объединения равна:
|А È В| = |А| + |В|.
Для n непересекающихся конечных множеств А1,А2,...,Аn мощность объединения:
n
|А1 È А2 È … È Аn| =
å
i =1
Ai .
Если в множествах А и В имеются общие элементы, т. е. множества пересекаются, то мощность их объединения равна:
|А È В| = |А| + |В|– |А Ç В|.
В общем случае мощность объединения n конечных множеств
А1, А2, …., Аn определяется по формуле, называемой в комбинаторике формулой включения-исключения:
|А1 È A2 È ,… È Аn| = (|А1| + |А2| + … + |Аn|) – (|А1 Ç A2| + |А1 Ç A3|+
+ … + |Аn–1 Ç An|) + (|А1 Ç A2 Ç A3| + ….. + |An–2 Ç Аn–1 Ç An|) – …. +
+ (–1)n–1 |А1 Ç A2 Ç A3 Ç … Ç An|.
Пример 4. В студенческой группе 20 человек (множество А). 12 из
них изучают английский язык (множество А1), 8 – немецкий (множество А2), 5 – испанский (множество А3), 6 изучают английский
и немецкий, 3 – английский и испанский, один – все 3 языка. Есть
ли в группе студенты (множество А4), которые не изучают данные
европейские языки? Поскольку в группе есть студенты, изучающие
сразу несколько языков, то для решения задачи будем использовать
формулу включения-исключения. Мощность объединения множеств А1,А2,А3,А4 равна количеству студентов в группе и по формуле включения-исключения:
|А| = |A1 È A2 È A3 È A4| = (|A1| + |A2| + |A3| + A4|)–(|A1 Ç A2| + |A1 Ç A3|) +
+ |A1| Ç |A2| Ç |A3|, т.е.
20 = 12 + 8 + 5 + A4–(6 + 3) + 1, A4 = 3. Три человека не изучают
указанные языки.
3.1.2. Перестановки
Пусть задано конечное множество А, состоящее из n – элементов.
Последовательность из n элементов множества с учетом их поряд22
ка называется перестановкой. Таким образом, отдельные перестановки отличаются друг от друга только порядком входящих в них
элементов. Перестановки обозначаются символом Р (от английского
Permutation – перестановки).
Число перестановок элементов множества А равно:
Рn = 1∙2∙3 ∙.. . ∙ n = n!.
Пример 5. Пусть число элементов множества А равно 5 (это может
быть множество разных книг, которые можно расставить на полке,
количество сидящих на скамейке студентов, количество независимо выполняемых работ и т. п.). Определить количество последовательностей элементов множества А, отличающихся положением хотя бы одного элемента. Это задача на перестановки. Число перестановок Р5 = 1∙2∙3∙4∙5 = 120. Отметим, что любые две перестановки различаются положением не менее чем 2-х элементов.
Пример 6. Переставляя буквы алфавита можно получить любое
слово, если все входящие в него буквы различны. В каком количестве вариантов перестановок встретится заданное слово? Зафиксируем появление слова в начале строки букв алфавита. Количество
вариантов появления слова будет равно числу перестановок не вошедших в него букв алфавита. Остается учесть тот факт, что слово
может стоять в любом месте строки букв алфавита.
Пример 7. Определить, сколько существует вариантов перестановок букв в слове Андрей, в которых гласные расположены в алфавитном порядке. Общее число перестановок равно 6!, число перестановок гласных равно 2!, из которых только в одной буквы расположены в алфавитном порядке. Искомое число перестановок N = 6!/2!.
А если расположить в алфавитном порядке согласные? А если все
буквы слова?
Перестановка 1, 2, 3, …,n – называется начальной или основной.
Насколько та или иная перестановка отстоит от основной, зависит
от количества инверсий. Количество инверсий в перестановке – это
количество пар элементов, в которых следующий элемент имеет
меньший номер, чем предыдущий.
Подсчет количества инверсий выполняется следующим образом.
Считается количество элементов, левее 1, удаляется 1, затем считается количество элементов левее 2, удаляется 2 и т. д. Просуммировав найденные числа, получим количество инверсий в перестановке.
Пример 8. В перестановке 43152 левее 1 находится 2 элемента,
в ряду 4352 левее 2 – 3 элемента, в ряду 435 левее 3 – один элемент,
в ряду 45 инверсии отсутствуют. Общее число инверсий равно 6.
23
Транспозицией называется операция замены двух элементов местами. Транспозиция является элементарной, если меняются местами два соседних элемента. Элементарная транспозиция меняет
количество инверсий на единицу. Перестановка является четной,
если она становится основной после четного количества транспозиций и нечетной, если после нечетного количества. Любая перестановка является четной или нечетной, но ни той, ни другой одновременно. Таким образом, перестановки разбиваются на два непересекающихся класса – нечетные и четные. Количество четных и нечетных перестановок одинаково и равно n!/2.
Пример 9. Для множества А из трех элементов число перестановок
равно 6. Это 123, 132, 213, 231, 312, 321. Перестановка 132 приводится
к основной после одной транспозиции (замены местами элементов 3 и 2),
перестановка 213 – также после одной, перестановка 321 – после трех
(321 – 231– 213 – 123). Перестановки 231 и 312 приводятся к основной
после 2-х транспозиций. Таким образом, класс четных перестановок:
(123, 231, 312), класс нечетных перестановок: (132, 213, 321).
Кроме линейной упорядоченности существует упорядоченность элементов по кругу. При этом последний и первый элементы перестановки
считаются взаимосвязанными и следующими друг за другом. Упорядоченность по кругу содержит перестановки, в которых взаимное расположение элементов различается. Число таких перестановок равно (n–1)!.
Каждая из них порождает n циклических перестановок, получающихся
путем сдвига порождающей перестановки на 1, 2, …, n позиций.
Пример 10. При n = 4 множество порождающих перестановок
при упорядочении по кругу: 1234, 1243, 1324, 1342, 1423, 1432.
Первая из них порождает класс циклических перестановок: 1234,
4123, 3412, 2341. Вторая порождает свой класс циклических перестановок, не пересекающихся с первым и т.д. Заметим, что в качестве порождающей может использоваться любая перестановка соответствующего циклического класса. Так, вместо перестановки 1234
можно взять 2341, 3412 или 4123.
Перестановки с неподвижной точкой. Множество перестановок,
в каждой из которых i элемент сохраняет свое место, называется
множеством перестановок с неподвижной точкой. Так, перестановки (1,2,3) и (3,2,1) имеют неподвижную точку 2.
Число перестановок, имеющих хотя бы одну неподвижную точку, определяется формулой:
n
F (Pn ) = å (-1)i+1 Cni (n - i)!
i=1
24
Число перестановок, имеющих одну неподвижную точку, определяется формулой:
n
G (Pn) = å (-1)i+1 Cni i (n - i)!
i=1
Пример 11. За столом сидят три мушкетера: Атос, Портос и Арамис.
Определить количество вариантов размещения группы, если точно 1
человек сохраняет свое место за столом (первый случай) и если свои
места сохраняют не менее одного человека (второй случай). В первом
случае варианты перестановок 132, 321, 213. В первой перестановке сохраняет свое место Атос, во второй – Портос, в третьей – Арамис.
Количество вариантов:
3
G (P3 ) = å (-1)i+1 C3i i (3 - i)! = 3 ×1× 2 !- 3 × 2 ×1!+ 1× 3 × 0 ! = 6 - 6 + 3 = 3.
i=1
Во втором случае варианты перестановок: 123, 132, 213, 321.
В первой перестановке все сохраняют свое место, во второй – сохраняет свое место Атос, в третьей – Арамис, в четвертой – Портос.
Количество вариантов:
3
F (P3 ) = å (-1)i+1 C3i (3 - i)! = 3 × 2 !- 3 ×1!+ 1× 0 ! = 6 - 3 + 1 = 4.
i=1
3.1.3. Размещеня
Размещением из n элементов по k элементам 0≤k≤n называется перестановка k элементов, выбранных из множества А, состоящего из n элементов. Иными словами, это любой упорядоченный набор различных
элементов множества А, состоящий из k элементов. Размещения обозначаются символом А (от английского Arranging – размещение).
Число размещений определяется формулой:
Cnk =
n!
.
(n - k)!
Пример 12. Сколько вариантов выбора 4 человек для участия
в эстафете на 1, 2, 3 и 4 этапах из группы спортсменов в 20 человек?
Выборка упорядоченная, т.к. надо распределить людей по этапам
эстафеты. Задача на размещения, количество вариантов равно:
4
C20
=
20 !
= 11628.
(20 - 4)!
25
Пример 13. В скольких N-разрядных десятичных числах все
цифры различны (N≤10)? Каждое число – упорядоченная выборка
из 10 различных цифр. Общее количество чисел равно количеству
размещений из 10 по N.
3.1.4. Сочетания
Сочетанием из n – элементов по k элементам 0 ≤ k ≤ n называется
подмножество из k элементов, выбранное из множества А, состоящего из n элементов. Сочетания обозначаются символом С (от английского Combination – сочетание).
Число сочетаний определяется формулой:
C
k
n
n!
.
k !(n - k)!
=
Пример14. Сколько вариантов выбрать M человек из группы в N
человек для участия в марафоне? Выборка не упорядочена, поскольку старт у спортсменов общий, задача на сочетания. Количество вариантов равно:
M
CN
=
N !
.
M !(N - M) !
Свойства сочетаний:
C
k
n
=C
k-1
k
n-1 + C n-1,
C
k
n
=C
n-k
n .
Cnk называется биномиальным коэффициентом, поскольку оно
входит в формулу бинома Ньютона:
n
( p + q)n =
å Cnk pn-kq k .
k=0
3.1.5 Разбиения
Разбиением из n элементов по k1, k2,…,k m элементов, где
"ki ³ 0,
m
å ki = n,
i=1
называется представление множества А из n элементов в виде
суммы из m непересекающихся множеств, в каждом из которых содержится k1, k2,…,k m элементов.
26
Разбиения является обобщением сочетаний и обозначаются тем
же символом С. Количество разбиений подсчитывается по формуле:
n!
Cn (k1, k2 ,..., km ) =
.
m
Õ ki !
i=1
Пример 15. В общежитии имеется две четырехместных комнаты
и одна двухместная, в которых должны поселиться 10 студентов.
Сколько имеется вариантов размещения студентов по комнатам?
Задача состоит в делении общего количества претендентов на 3 непересекающихся подмножества, содержащих 4, 4 и 2 человека. Количество вариантов определяется по формуле разбиений:
C10 (4,4,2) =
10 !
3
= 10.
Õ ki !
i=1
3.1.6. Операции на множествах с повторениями
В классическом определении множеств (см. раздел 1) все элементы множества различны. По правилам идемпотентности множество
с элементами (1,1,2,3,3,3,5) эквивалентно множеству с элементами
(1,2,3,5). Но в комбинаторике такие множества различаются. Множество с повторениями – множество А, содержащее k1 элементов 1–
го типа, k2 – второго, … km элементов типа m. Общее количество элеm
ментов множества n = å ki .
i=1
Перестановки с повторениями. Перестановки с повторениями
есть перестановки элементов множества с повторениями, в которых
элементы одного типа неразличимы. Можно использовать обычное
множество, разрешив использовать любой его элемент в перестановке произвольное число раз. Число перестановок с повторениями
определяется формулой:
P(k1, k2 ,...km ) =
n!
,
k1 !× k2 ! × ...× km !
m
å ki = n.
i=1
Отметим, что задачи на перестановки с повторениями могут интерпретироваться как задачи на разбиения.
27
Пример 16. В лифт 9-этажного дома на первом этаже сели 4 человека А, В, С и D. Сколько существует вариантов разгрузки лифта,
если на любом этаже может выйти только 1 человек? Разгрузка происходит на 8 этажах дома. При любом варианте разгрузки 4 этажа
остаются свободными от разгрузки. Таким образом, множество элементов перестановок будет содержать 4 различных идентифицируемых разгрузочных элемента (А,В,С,D) и четыре повторяющихся пустых элемента. Это задача на перестановки с повторениями. Общее
число перестановок:
5
8!
P(4 !, 1!,1!,1!,1!) =
= 1680, å ki = 8.
4 !×1!×1!×1!×1!
i=1
Если севшие в лифт люди неразличимы, то множество будет содержать 4 неразличимых разгрузочных элемента и 4 пустых, число
перестановок:
2
8!
P(4 !, 4 !) =
= 70, å ki = 8.
4 !×4 !
i=1
Размещения с повторениями. В отличие от перестановок с повторениями, размещения с повторениями могут строиться по различным схемам.
1) Можно взять множество с повторениями, а выбор элементов
проводить в соответствии с общим определением размещения.
2) Можно взять обычное множество и при выборе элементов из
него разрешить выбирать одинаковые.
3) Можно взять множество с повторениями и при выборе элементов из него также разрешить выбирать одинаковые.
Размещения с повторениями по схеме 1 – это перестановки из k
элементов любого подмножества исходного множества с повторениями.
Размещения с повторениями по схемам 2 и 3 – перестановки из k
элементов, где на каждом шаге допускается выбор любого элемента
исходного множества.
Число размещений с повторениями по схемам 2 и 3 определяется
формулой:
A nk (rep) = nk , k ³ 0.
Отметим, что задачи на размещения с повторениями по схемам 2 или
3 могут интерпретироваться как задачи на декартову степень.
Для схемы 1 не существует общей формулы и необходимо вручную
строить алгоритмы для подсчета количества вариантов размещений.
28
Пример 17. Определить количество 5-разрядных чисел в троичной системе счисления. Это задача на размещения с повторениями
по схеме 2, поскольку исходным является простое множество, содержащее 3 элемента – цифры 0, 1, 2, и любая цифра может повторяться произвольное количество раз. Общее количество чисел будет
равно: A
5(r e p)
3
= 3 5 = 2 4 3.
Пример 18. Задано множество цифр с повторениями (2,2,2,3,5,5).
Сколько различных 3-х разрядных чисел может быть построено?
Это задача на размещения по схеме 1. Не существует общей формулы для решения такой задачи. Для подсчета количества чисел должен быть разработан специальный алгоритм.
Сочетания с повторениями. Сочетания с повторениями также могут
строиться по схемам 1-3. Сочетание с повторениями по схеме 1 – любое
подмножество из k элементов исходного множества с повторениями.
Сочетание с повторениями по схемам 2 и 3 – любое подмножество
из k элементов множества (обычного или с повторениями), когда после выбора элемента исходное множество восстанавливается. Иными словами, любой элемент исходного множества может повторяться в выборке произвольное число раз.
Число сочетаний с повторениями по схемам 2 и 3 определяется
формулой:
-1
Cnk(rep) = Cnk+
k-1 =
(n + k -1)!
, k ³ 0.
n !(k -1)!
Для схемы 1 не существует общей формулы и необходимо вручную
строить алгоритмы для подсчета количества вариантов сочетаний.
Пример 19. Имеется 4 типа грузов, причем количество ni каждого
типа грузов конечно, но достаточно велико, во всяком случае, ni≥5.
Сколько существует вариантов загрузки автомашины, которая может перевести одновременно 5 грузов? В этой задаче исходное множество является конечным множеством с повторениями. Однако
число грузов любого типа в множестве больше количества грузов,
помещающихся в машине. Поэтому задача сводится к задаче на сочетания с повторениями по схеме 2. Число вариантов определяется
по формуле:
8!
1
C 54 ( r e p) = C 54= 70.
+5-1 =
4 !× 4 !
29
Если количество грузов n1 = 1, n2 = 3, n3 = 5, n4 = 8, то это задача
на сочетания с повторениями по схеме 1. Общая формула решения
отсутствует, количество вариантов определяется путем перебора.
Пример 20. Сколько N разрядных десятичных чисел содержат
ровно К различных цифр (K≤10). Первоначально, с помощью формулы для сочетаний, определяем количество различных комбинаций
из 10 цифр по К. Для каждой комбинации количество различных
N-разрядных чисел вычисляем по формуле размещений с повторениями (размещения по схеме 2).
3.1.7. Комбинаторные задачи с ограничениями
Во многих случаях решение комбинаторных задач выполняется при наличие ограничений. Запрещенные комбинации должны
быть удалены из общего решения, полученного путем применения
известных формул. В более сложных случаях требуется разработка
специального алгоритма решения подобных задач.
Пример 21. Разложить 10 различных монеток по трём карманам
так, чтобы ни один карман не остался пустым. При отсутствии ограничений любая монетка может попасть в любой карман, количество
вариантов рассчитывается по формуле декартового произведения
(декартовой степени): N3 = mk = 310. Теперь нужно удалить запрещенные комбинации, в которых один или два кармана остались пустыми. Количество комбинаций с одним пустым карманом сводится к задаче раскладывания монеток по двум карманам: N2 = 210. Поскольку пустым может быть любой из трёх карманов, то общее число запрещенных комбинаций равно 3∙N2. В число этих комбинаций
входят и варианты с двумя пустыми карманами. Причем варианты
с двумя пустыми карманами будут повторяться (в первом случае пустыми могут быть 1 и 2 или 1 и 3 карманы, во втором случае 1 и 2
или 2 и 3, в третьем – 1 и 3 или 2 и 3). Общее количество вариантов
с двумя пустыми карманами равно 3∙N1 = 3∙110 = 3. Таким образом,
число вариантов решения исходной задачи с ограничениями равно
N3–3∙N2 + 3∙N1 = 59045–1024 + 3 = 58028.
А сколько вариантов разложить 10 одинаковых монет по трем
карманам? Это задача на декартово произведение с повторениями.
Общая формула для нахождения числа комбинаций отсутствует.
Запишем возможные комбинации расположения монет. Если в первый карман попала 1 монета, то множество комбинаций раскладки
монет: 118, 127, 136, 145, 154, 163, 172, 181. Если 1 монета попала
30
во второй карман: 118, 217, 316, 415, 514, 613, 712, 811, если в третий: 181, 171, 361, 461, 541, 631, 721, 811. Комбинации 118, 181 и 811
встречаются дважды. Таким образом, общее количество различных комбинаций равно 8∙3–3 = 21. Затем записываем комбинации,
в которых 2 монеты попадают в первый, второй или третий карман.
Удаляем дважды встречающиеся варианты во всем множестве комбинаций и т.д. Задача решается методом перебора, общее количество вариантов разложения монет равно 36.
Пример 22. Задача на расстановку (выборку) предметов с ограничениями. Пусть за круглым столом сидят 10 мужчин. Требуется
рассадить 7 женщин так, чтобы их соседями были мужчины. Для
решения задачи первоначально рассадим мужчин с промежутками
(получим 10 промежутков). Семь из них займут женщины, остальные промежутки уберем. Общее количество вариантов по формуле
7
сочетаний будет равно C10
=
10 !
= 120.
7 !× (10 - 7)!
Пример 23. Определить количество вариантов выбора 3-х не расположенных рядом книг из 8 стоящих на полке. Представленная
здесь задача обратна задаче примера 22. Отличие в том, книги на
полке образуют разомкнутое исходное множество, в отличие от циклического в предыдущем примере. Соответственно, первая и последняя книги всегда не соседние и количество допустимых положений оказывается на единицу больше. Количество вариантов выбора определяется формулой:
C
k
n-k+1 =
6!
= 20,
3 !× (6 - 3)!
где n – общее число книг на полке, k – количество выбираемых книг.
3.2. Mетод решет
3.2.1. Общий случай формулы включения – исключения
Зададим конечное множество А и выделим в нем подмножество A1.
Обозначим символом A1 дополнение А1 в множество А (универсальном для А1):
A1 Ì A, A1 Ì A, A1 È A1 = Æ,
A1 È A = A,
A = A1 + A1 ,
A1 = A - A1 .
31
Зададим два подмножества А1 и А2:
A1 Ì A, A2 Ì A.
( A1 È A2) È ( A1 È A2) = A, A1 È A2 = A1 Ç A2 ,
A1 È A2 = A1 + A2 - A1 Ç A2 ,
A1 È A2 = A - A1 - A2 + A1 Ç A2 ,
A1 Ç A2 = A - A1 - A2 + A1 Ç A2 .
В общем случае множество элементов из А, которые не принадлежат подмножествам А1,…,Аn рассчитывается по формуле:
A Ç A2 Ç .. Ç An = A - A1 - A2 - ... - An + A1 Ç A2 + ... + An-1 Ç An - ... + (-1)n-1 A1 Ç A2 Ç ... Ç An .
Образно говоря, мы «просеиваем» элементы множества А через
решета, задерживающие элементы, принадлежащие подмножествам А1,…,Аn.
3.2.2. Решето Сильва–Сильверста
Рассмотрим другой вид формулы включения-исключения:
A1 Ç A2 Ç ... Ç Ak Ç Ak+1 Ç .... Ç An =
= A - A Ç Ak+1 - A Ç Ak+2 - ... - A Ç An +
+ A Ç Ak+1 Ç Ak+2 + ... A Ç An-1 Ç An -... + (-1)n-k A Ç Ak Ç Ak+1 Ç ... Ç An ,
где A = A1 Ç A2 Ç ... Ç Ak .
Пусть каждое подмножество Ai обладает свойством Pi, тогда:
A1 Ç A2 Ç ... Ak Ç Ak+1 Ç ... Ç An
обладает свойствами Р1, Р2,…,Рк и не обладает свойствами Рк
…,Рn или:
P1 & P2 &…& Pk & Pk+1 &…& Pn .
32
+ 1,
Этот вид формулы включения-исключения также описывает последовательный процесс «просеивания» или «пропускания через
решето»
Пример 24. Дано множество А = {0, 1, 2, ….,10} и его подмножества А1, А2, А3, обладающие свойствами:
А1 – свойство Р1 аi Î A, ai – четное, A1 = {0, 2, 4, 6, 8, 10}.
А2 – свойство Р2 аj Î A, aj > 6, А2 = {7, 8, 9, 10}.
A3 – свойство Р3 аtÎ A, 2 < at <8, A3 = {3, 4, 5, 6, 7}.
Подсчитаем число элементов А, которое обладает свойствами
&
P1 P2 & P3 :
A1 Ç A2 Ç A3 = A1 - A1 Ç A2 - A1 Ç A3 + A1 Ç A2 Ç A3 .
1) «Просеиваем» А через Р1 : A1 = 6.
2) «Просеиваем» А1 через Р2 и Р3 : A1 Ç A2 = 2, A1 Ç A3 = 2.
3) «Просеиваем» A1 Ç A2 через Р3 : A1 Ç A2 Ç A3 = 0
В результате получаем: A1 Ç A2 Ç A3 = 6 - 2 - 2 = 2.
Действительно: A1 Ç A2 = {0, 2, 4, 6}, ( A1 Ç A2 ) Ç A3 = {0, 2} .
3.2.3. Решето Эратосфена
Решето Эратосфена является способом нахождения простых чисел pi, pi £ n и состоит в следующем. Вычисляется e = éêë n ùúû , где запись [A] означает «наибольшее целое, меньшее или равное числу А».
Из последовательности 2, 3, ….,n вычеркиваются все числа, кратные 2,
затем кратные 3, …, кратные e. Оставшиеся числа и есть множество
простых чисел n £ pi £ n.
Пример 25. Пусть n = 30, исходная последовательность следующая:
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,
28,29,30}, e = éê 30 ùú = 5 , множество делителей {2, 3, 4, 5}.
ë
û
Удалив из исходной последовательности числа, кратные делителям,
получим множество простых чисел {7, 11, 13, 17, 19, 23, 29}.
Продолжим процедуру, взяв в качестве сокращенной
последовательности множество делителей {2, 3, 4, 5}.
e1 = éê 5 ùú = 2. Удалив из последовательности числа, кратные 2 получим
ë û
множество простых чисел {3, 5}.
Сокращенная последовательность будет содержать одно число {2},
которое является простым, т.к. не имеет делителей.
Таким образом, для исходной последовательности полное
множество простых чисел это: {2,3,5,7,11,13,17,19,23,29}.
33
3.2.4. Использование метода решет в теории чисел
1) Нахождение делителей.
Теорема 1. Пусть А = {1, 2, …n}, a1, a2, … ar – взаимно простые
числа (ai,aj) = 1. Количество q целых чисел kj таких, что 0 < kj = <n,
ai – не являются делителями kj, (ai, kj) = 1, равно:
r é ù
é n ù
é
ù
n
n
ú - ... + (-1)r ê
ú.
q = n - å ê ú + å êê
ú
êa ú
ê a a ...a ú
a .a
rû
ë 1 2
i=1 ë i û ïî âñåì i,j êë i j úû
i¹ j
Пример 26. A = {1, 2, …, 35}, a = {3, 7, 8} – множество взаимно простых чисел. Тогда
3 é ù
é n ù é
ù
æé ù é ù é ùö
n
n
ú-ê
ú = 35 - çç ê 35 ú + ê 35 ú + ê 35 ú÷÷ +
q = n - å ê ú + å êê
÷
ú
ç
êa ú
ê
ú
çê
a ×a
a ×a ×a
è ë 3 úû êë 7 úû êë 8 úû ÷ø
i=1 ë i û ïî âñåì i,j êë i j úû ë 1 2 3 û
i¹ j
æ é 35 ù é 35 ù é 35 ù ö÷ é 35 ù
ú+ê
ú+ê
ú ÷÷ - ê
ú = 35 - (11 + 5 + 4) + (1 + 1 + 0) - 0 = 17.
+ççç ê
çê
è ë 3 × 7 úû êë 3 × 8 úû êë 7 × 8 úû ÷ø êë 3 × 7 × 8 úû
2) Определение функции Эйлера.
Напомним, что количество k простых чисел таких, что 0 < k < n
обозначается ϕ(n) и называется функцией Эйлера.
Теорема 2. Пусть n Î {1, 2, 3,......} тогда функция Эйлера
æ
1ö
ϕ(n) = n ´Õççç1 - ÷÷÷,
çè ai ø÷
i
где произведения берутся по всем простым делителям ai числа n.
Докажем это. Поскольку все ai делят n и взаимно просты, то
é
ù
n
n
ê
ú=
, отсюда по результатам предыдущей теоê a × a ××× a ú a × a ××× a
rû
1 2
r
ë 1 2
ремы получим:
ϕ(n) = n × (1 -
1
1
1
) × (1 - ) ××× (1 - ).
a1
a2
ar
Пример 27. Пусть n = 84, простые делители 2, 3, 7, тогда:
34
1
1
1
ϕ(84) = 84 × (1 - ) × (1 - ) × (1 - ) = 24.
2
3
7
1
При n = 8, простой делитель 2, ϕ(8) = 8 × (1 - ) = 4.
2
Используя теорему 1 можно получить формулу для подсчета количества простых чисел pi таких, что n £ pi £ n :
r é ù
é n ù
é
ù
n
n
ú - ... + (-1)r ê
ú,
M (n) = -1 + n - å ê ú + å êê
ú
êp ú
ê
ú
p .p
ë p1 p2 ... pr û
i=1 ë i û ïî âñåì i, j êë i j úû
i¹ j
Первое слагаемое –1 добавляется, т.к. 1 – по определению не
простое число.
Пример 28. При
é 30 ù é 30 ù é 30 ù é 30 ù é 30 ù é 30 ù é 30 ù
ú+ê
ú+ê
ú-ê
ú=
Ì (30) = -1 + 30 - ê ú - ê ú - ê ú + ê
êë 2 úû êë 3 úû êë 5 úû êë 2 × 3 úû êë 2 × 5 úû êë 3 × 5 úû êë 2 × 3 × 5 úû
= -1 + 30 -15 -10 - 6 + 5 + 3 + 2 -1 = 7.
3.3.2. Mетод перебора
Метод перебора используется для декомпозиции задачи, если
к ней нельзя непосредственно применить то или иное правило или
формулу. Например, при нахождении чисел меньше К, которые
можно построить с использованием M цифр, первоначально все числа делятся на числа с максимальным числом разрядов меньших К,
затем числа, содержащие на разряд меньше и далее до одноразрядных чисел. Количество чисел в каждой группе подсчитывается с использованием формулы размещений.
Задача о произвольной разгрузке лифта от неидентифицированных пассажиров – первоначально находятся все возможные
комбинации выхода пассажиров. Количество вариантов разгрузки лифта для каждой комбинации находится с использованием
формулы перестановок. Так, для 3 человек возможные комбинации: выход одного человека на одном этаже, выход 2 человек на
одном этаже и 1 на каком-то другом, выход всех 3 человек на одном этаже.
Перебор и перестановки используются для подсчета вариантов
размещения одинаковых монет по ряду карманов.
35
Недостаток метода перебора состоит в большом количестве вариантов, возникающих в процессе такой декомпозиции задачи.
3.4. Упражнения
1. В спортклубе 25 человек. Требуется составить команду из 4-х
человек для участия в беге на 100м. Сколькими способами это можно сделать? А если требуется составить команду из 4-х человек для
участия в эстафете 100 + 200 + 400 + 800м?
2. В скольких 7 разрядных числах все цифры различны?
3. Сколько чисел от 1 до 900 не делится ни на 3, ни на 7, ни на 11?
4. На загородную прогулку выехали 92 человека. Бутерброды
с колбасой взяли 48 человек, с сыром – 38, с ветчиной – 42, с сыром
и колбасой – 28, с колбасой и ветчиной – 31, с сыром и ветчиной – 26.
25 человек взяли с собой все три вида бутербродов. Остальные взяли
пирожки. Сколько человек взяли пирожки?
5. Сколько разных делителей кратных 10 имеет число 3350?
6. На прямой взяты p точек, а на параллельной ей прямой еще g
точек. Сколько существует треугольников, вершинами которых являются эти точки?
7. В каком числе перестановок из 33 букв русского алфавита
не встречаются слова студент, декан, институт?
8. 4 волчка с 3, 5, 11 и 4 гранями соответственно запускаются
и останавливаются в некоторых положениях. Сколькими различными способами они могут упасть? А если известно, что, по крайней
мере, 3 из них остановились на цифре 2?
9. У мамы 3 яблока, 4 груши и 4 апельсина. Каждый день в течение 11 дней подряд она выдает дочери по 1 фрукту. Сколькими способами она это может сделать?
10. Имеется 4 утки, 3 курицы и 2 гуся. Сколькими способами
можно выбрать из них несколько птиц так, чтобы среди выбранных
были и утки и куры и гуси?
11. Найдите и выпишите все перестановки их букв X,Y,Z при которых ни одна буква не остается на своем месте. А сколько существует перестановок из букв a,b,c,d,e при которых ровно одна из них
на своем месте?
12. Из колоды в 52 карты двое игроков выбирают по 4 карты
каждый. Сколько существует различных вариантов выбора? В
скольких случаях один из игроков получает 4 туза, а другой 4 короля?
36
13. Сколько 6 разрядных чисел содержат ровно 3 различных
цифры? Сколько n разрядных чисел содержат ровно k различных
цифры?
14. Сколько чисел меньших миллиона можно записать с помощью цифр 9,8,7. А с помощью цифр 9,8,0, если число не может начинаться с 0?
15. Сколькими способами можно переставить буквы слова «Юпитер»
так, чтобы гласные шли в алфавитном порядке?
16. На собрании должно выступить пять человек A,B,C,D,E.
Сколькими способами можно составить списки выступающих при
условии, что B не должен выступать до тех пор, пока не выступит A?
Решите ту же задачу при условии, что A должен выступить непосредственно перед B.
17. Сколькими способами можно переставить буквы слова «каракули» так, чтобы никакие две гласные не стояли рядом?
18. Сколько разных делителей, кратных 21 имеет число 525?
19. Сколько разных списков для выступлений можно составить
для 20 депутатов, если депутаты З и Ж и Я уже обеспечили себе места соответственно 7 и 11и 13 ?
20. Сколько разных делителей имеет число 6350?
21. В каком числе перестановок из 33 букв русского алфавита
встречаются слова спорт, профессор, качели?
22. Из 25 человек работающих в отделе, 14 имеют диплом инженера,8 диплом техника, 7 диплом экономиста, 5 одновременно диплом инженера и техника, 4 диплом инженера и экономиста, 6 диплом техника и экономиста, 2 имеют все три вида дипломов. Руководство решило уволить сотрудников без дипломов. Сколько может
быть уволено сотрудников?
23. На книжной полке 15 книг. Сколько существует способов
взять с полки 7 книг, которые не стояли рядом? А 12 книг?
37
Список использованных источников
1. Виленкин Н. Я. Популярная комбинаторика / М.: Наука, 1975. 208 с.
2. Виленкин Н. Я. Рассказы о множествах / М.: Наука, 1965. 128 с.
3. Риордан Дж. Введение в комбинаторный анализ /Дж. Риордан;
пер. с англ. М.: Иностранная литература, 1963. 287 с.
4. Холл М. Комбинаторика / пер. с англ. М.: Мир, 1970. 424 с.
5. Теория вероятности и математическая статистика на базе MATLAB:
учеб. пособие / Харьковский НТУ «ХПИ»; сост. С.П. Иглин. Харьков,
2006. 612 с.
6. Элементы дискретной математики : учеб. пособие / Санкт-Петербургский
гос.ун-т аэрокосмического приборостроения: сост. И.Л. Ерош, В.В Михайлов.
СПб., 2008. 104 с.
7. Дискретная математика: учеб. пособие / Санкт-Петербургский гос.ун-т аэрокосмического приборостроения: сост. И.Л Ерош, М.Б. Сергеев, Н.В. Соловьев.
СПб., 2008. 144 с.
38
Содержание
Предисловие................................................................... 1. Элементы теории множеств........................................ 1.1. Понятие множества ........................................... 1.3. Основные операции над множествами................... 2. Алгебра множеств........................................................ 3. Элементы комбинаторики.............................................. 3.2. Mетод решет...................................................... 3.4. Упражнения...................................................... Список использованных источников............................... 3
4
4
7
17
20
31
36
38
39
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 904 Кб
Теги
mikhailov, popv
1/--страниц
Пожаловаться на содержимое документа