Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Калмыцкий государственный университет»

Е.О. Басангоеа

ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ

И КОМБИНАТОРИКУ

Учебное пособие

Рекомендовано Учебно-методическим советом по математике и механике УМО по классическому университетскому образованию РФ в качестве учебного пособия для студентов высших учебных заведений, обучающихся по группе математических и механических направлений и специальностей Элиста 2007 ББК В126(2Рос.Калм)я73+В141(2Рос.Калм)я73 Б 270 Басангова, Е.О.

Введение в теорию множеств и комбинаторику [Текст]: учебное посо­ бие / Е.О. Басангова. - Элиста, 2007. - 88 с.

Пособие содержит теоретический и практический курс по основам теории множеств и комбинаторики. Состоит из двух частей. Разделы каж­ дой части содержат упражнения, снабженные ответами. В конце обеих час­ тей подобран комплект задач по всем темам.

Предназначается для студентов университета специальности «Математика».

Печатается по решению редакционно-издательского совета КГУ.

Рецензенты: зав. кафедрой прикладной математики и программирования ЮФУ, д-р физ.-мат. наук Г.А. Угольницкий;

проф. кафедры алгебры и дискретной математики ЮФУ, д-р физ.-мат. наук Я.М. Ерусалимский © Издательство Калмыцкого университета, 2007 г.

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

1.1. Определение множества 1.2 Способы задания множеств 1.3. Сравнение множеств 1.4 Операции над множествами 1.5 Свойства операций над множествами 1.6. Счетные множества 1.7. Разбиения и покрытия 1.8. Формула включений и исключений 1.9. Произведение множеств 1.10. Бинарные отношения 1.11. Обратные отношения и композиции отношений 1.12. Свойства отношений 1.13. Приложение. Системы управления базами данных 1.14. Функции 1.15. Обратные функции и композиция функций 1.16. Принцип Дирихле

ЗАДАЧИ ПО ТЕОРИИ МНОЖЕСТВ

2. КОМБИНАТОРИКА 2.1. Правило суммы и произведения 2.2. Размещения, перестановки, сочетания 2.2.1 Размещения с повторениями 2.2.2 Размещения без повторений 2.2.3 Перестановки без повторений 2.2.4 Сочетания без повторений 2.2.5 Перестановки с повторениями 2.2.6 Сочетания с повторениями 2.2.7 Биномиальные коэффициенты 2.3. Комбинаторика разбиений

ЗАДАЧИ ПО КОМБИНАТОРИКЕ

ЛИТЕРАТУРА

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

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

Георг Кантор (1845 - 1918) - основатель теории множеств - сказал:

«Множество - есть многое, мыслимое как единое».

Множество состоит из элементов. Например, число 14 является эле­ ментом множества целых чисел, а число 7.3 - не является элементом мно­ жества целых чисел.

Обычно множества обозначаются латинскими прописными буквами:

А, В, С, D,..., X, Y, Z, а элементы - строчными буквами а, Ь, с, d,..., x,y,z.

Если объект а является элементом множества А, то пишут: аеА (а принад­ лежит множеству А), иначе - пишут: а^А (а не принадлежит множеству А).

Так, 14eZ (Z - множество целых чисел), 7.3^N.

Пустое множество - это множество, не содержащее элементов, такое множество обозначают 0. Кроме пустого множества, стандартные назва­ ния и обозначения имеют следующие множества:

N={1, 2, 3,...} - множество натуральных чисел;

Z={0, ±1, ±2, ±3,...} - множество целых чисел;

Q={ — : р, qeZ, q^O} - множество рациональных чисел;

R={Bce десятичные дроби} - множество вещественных чисел.

Мощность множества А - это число элементов этого множества, обо­ значают \А\. Например, если А - множество однозначных натуральных чи­ сел: 1, 2, 3, 4, 5, 6, 7, 8, 9, то | А | = 9. Для пустого множества | 0 | =0, но l{0}l=i.

Множество А конечно, если содержит конечное число эле ментов.

Примером конечного множества является множество стран мира, бесконеч­ ного - множество натуральных чисел, или множество вещественных чисел из интервала (0, 1).

1. Является ли бесконечным множество всех атомов Солнечной системы?

2. Старейший математик среди шахматистов и старейший шахматист среди математиков - это один или тот же человек или (возможно) разные?

3. Лучший математик среди шахматистов и лучший шахматист среди ма­ тематиков - это один или тот же человек или (возможно) разные?

4. Каждый десятый математик - шахматист, а каждый шестой шахматист математик. Кого больше - математиков или шахматистов - и во сколько 5. Пусть А - множество растений, растущих в Калмыкии, В - множество цветов, С - множество деревьев.

a) Назовите два элемента множества В, не являющихся элементами b) Назовите два элемента множества С, не являющихся элементами c) Существуют ли элементы, принадлежащие всем трем множествам?

6. Является ли множество, состоящее из числа 0, пустым множеством?

7. Пусть А - множество студентов вашей группы, какова его мощность?

1.2 Способы задания множеств Существует три способа задания множества.

1) Перечисление элементов.

Этот способ применим лишь для конечных элементов, таких как: мно­ жество всех континентов, множество гласных букв, множество отличников группы. Например, А={Европа, Азия, Америка, Африка, Австралия}, В={а, е, и, о, у, э, ю,я}.

2) С помощью характеристического свойства.

Характеристическое свойство множества - это свойство, которым обладают все элементы этого множества. Если множество А задано харак­ теристическим свойством Р, то это обозначают:

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

Например, множество целых чисел в диапазоне от m до п обозначают так: m..n, то есть тельных чисел, кроме 0. Если R 0 U R < I - множество всех действительных чисел.

Отметим, что объединение множеств А и В называют иногда суммой и обозначают А + В, а их пересечение - произведением и обозначают АВ.

Разностью множеств А и В называют множество, состоящее из всех тех и только тех элементов из А, которые не принадлежат В, и обозна­ чают:

Например, А={ 1,2,3}, В={3, 4, 5}. Тогда А\В={1, 2}.

Симметри ческая разность :

А А В=(АиВ) \ (АпВ)={х | (хеА & хВ) v (xA & хеВ)}.

Например, А={ 1,2, 3},В={3,4, 5}. Тогда А А В={1, 2, 4, 5}.

Дополнение множества А:

На рис.2 приведены диаграммы Эйлера, иллюстрирующие операции над множествами. Заданные множества изображаются кругами, а резуль­ тат выделяется штриховкой.

Операции пересечения и объединения допускают следующее обоб­ щение. Пусть I - некоторое множество, элементы которого используются как индексы, и пусть для любого i e l множество Ai известно. Тогда (J Ai= {x | существует iel, такое что xeAi}, р| Ai={x| для любого i e l xeAi}.

Пример 1.4.1. Изобразим с помощью кругов Эйлера множества (если АПВ*0, АПВПС*0):

a ) i n B, (рис.3) Ъ) А глВ, (рис.4), с) В\(АПС), (рис.5).

Пример 1.4.2. Задать множества А={х| xeN, x - делитель числа 20}, В={х| х кратно 5, хе[5, 30]}, С={х| х2-х-20=0} перечислением элементов.

Найти множества: АП(В1Ю), (А\С) ЦВ.

А={х| xeN, х - делитель числа 20} = {1, 2, 4, 5, 10, 20};

В={х| х кратно 5, хе[5,30]} = {5,10, 15,20,25,30};

С={х|х2-х-20=0} = {-4,5};

АП(В11С)={5, 10,20};

(А\С) U В = {1, 2, 4, 5, 10, 15, 20, 25, 30}.

Пересечение, объединение и разность подмножеств множества U (универсума) являются подмножествами множества U. Множество всех подмножеств множества с операциями пересечения, объединения, разности и дополнения образуют алгебру подмножеств множества U.

Пример 1.4.3. Построить множество точек плоскости, заданное не­ равенством =} x G A\(B(JC) 2 способ Преобразуем левую часть равенства к правой с помощью свойств операций над множествами:

A\(BUC)= Агл(В^С) = Агл(ВглС) = ( Л п В ) п С = 04\В)пС=(А\В)\С.

Изобразим обе части равенства с помощью кругов Эйлера (рис.9):

1. Доказать тождества:

2. Доказать, что если AUBczC, то Ас:С и Вс:С, и обратно (т.е. если Ас:С и ВсС, то AUBczC) 3. Даны множества A={XGR| Х -2Х-3 В задана формулой: f(x)=l + -, где А обозначает мноX жество вещественных чисел, отличных от 0, а В — множество вещест­ венных чисел без 1. Покажите, что f биективна и найдите обратную к ней функцию.

5. Функции f : R ^ R n g : R ^ R заданы следующим образом:

6. Сколькими способами можно переставить буквы слова «перешеек» так, чтобы 4 буквы «е» не шли подряд?

Ответ: Р(4,1,1,1,1)-5!=1560.

7. Сколькими способами можно переставлять буквы в слове «обороно­ способность» так, чтобы две буквы «о» не шли подряд?

Ответ: Р(3,2,2,1,1,1,1)-Ц2 способов.

8. Сколькими способами можно переставить буквы слова «каракули» так, чтобы никакие две гласные не стояли рядом?

Ответ: 5-12 =720 способов.

9. Сколькими способами можно переставить цифры числа 12 341 234 так, чтобы никакие две одинаковые цифры не шли друг за другом?

Ответ: Р(2,2,2,2)-4-Р(2,2,2,1)+6-Р(2,2,1,1)-4-Р(2,1,1,1)+Р(1,1,1,1)=864.

10. Найти коэффициент при х в разложении (1+х -х ).

Ответ: Р(2,2,2,2,1)+Р(3,3,2,1)=378.

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

Найдем число сочетаний с повторениями из п элементов по к.

Каждый состав сочетания задается последовательностью (к ь...,к п ), состоя­ щей из неотрицательных целых чисел, где ki показывает количество эле­ ментов первого вида, к2 - второго,..., кп - n-го вида. Таким образом, Сп, равно количеству числовых кортежей (k b...,k n ) длины п, для которых ki+k2+...+kn=k.

Итак, надо решить следующую задачу:

1. Найдем количество тех числовых кортежей (k b...,k n ) длины п, для кото­ рых ki+k2+... +kn=k.

Решение. Будем кодировать каждый кортеж (к ь...,кп) словом, составленным из единиц и нулей. С этой целью заменим в кортеже каждое число kj после­ довательностью из kj единиц (если kj=0, то единицы не пишутся), а каждую запятую заменим нулем. Получится кортеж из k!+...+kn=k единиц и п-1 ну­ лей (запятых в кортеже (k b...,k n ) на 1 меньше, чем чисел). Например, кор­ теж (4, 1,0,2) кодируется так: (1111010011). Обратно, каждому кортежу, составленному из к единиц и п-1 нуля, соответствует числовой кортеж (k b...,k n ), такой, что ki+...+kn=k. Поэтому искомое число кортежей вида (k b...,k n ) равно числу кортежей из к единиц и п-1 нуля. По формуле пере­ становок с повторениями число таких кортежей равно ^ „ ~^„ „„„„ г™.„„ С к+п-1 • Итак, мы доказали равенство:

Пример 2.2.21. Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта пирожных?

Решение. Выбор набора (2, 1, 3, 1), состоящего из 2 пирожных первого вида, одного пирожного второго вида, трех пирожных третьего вида и одного пирожного четвертого вида соответствует коду 1101011101. а код обозначает, что набор включает четыре пирожных первого вида и три пирож­ ных второго вида (третий и четвертый вид пирожных не выбраны).

можно составить 120 наборов.

Пример 2.2.22. Сколькими способами можно разложить к одинаковых ша­ ров по п различным ящикам?

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

1. Сколько можно построить различных параллелепипедов, длина каждо­ го ребра которых является целым числом от 1 до 10.

Ответ: 220.

2. Меню в китайском ресторане дает вам возможность выбрать ровно три из семи главных блюд. Сколькими способами можно сделать заказ?

3. В почтовом отделении продаются открытки 10 сортов. Сколькими спо­ собами можно купить в нем 12 открыток? 8 открыток? Сколькими спо­ собами можно купить 8 различных открыток?

Ответ: 293930: 24310: 45.

4. Сколько различных вариантов можно получить, бросая пять игральных Ответ: 252.

5. Сколько существует треугольников, длины сторон которых принимают одно из следующих значений: 4, 5, 6, 7 см?

2.2.7 Биномиальные коэффициенты Число сочетаний это число различных ^-элементных подмножеств n-элементного множества.

Числа С- „ также назьшают биномиальными коэффициентами в формуле бинома Ньютона:

Следствия из формулы (11):

Следствие 2.

Свойства биномиальных коэффициентов, вытекающие из основной формулы для числа сочетаний (10):

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

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