Элементы теории множеств. Комбинаторика

математики МАТЕМАТИКА_2сем Часть 1. Элементы теории множеств. Комбинаторика Бодряков Владимир Юрьевич, д.ф.-м.н.,

проф. E-mail: Bodryakov_VYu@e1.ru

Екатеринбург
2013 - 2014

Кузнецова Л.В., Минаева С.С. Математика. Алгебра. Функции. Анализ данных. 8

класс: Учеб. для общеобразоват. учеб. заведений. – М.: Дрофа, 2002. – 304 с.
Виленкин Н.Я., Ивашев-Мусатов О.С., С.И. Шварцбурд. Алгебра и математический анализ. 11 кл.: Учеб. пособие для шк. и кл. с углубл. изуч. математики. – М.: Мнемозина, 2001. – 288 с.
Вернер А.Л., Карп А.П. Математика: Учеб. пособие для 11 кл. гуманит. профиля. – М.: Просвещение, 2002. – 191 с.
Никольский С.М., Потапов М.К., Решетников Н.Н., Шевкин А.В. Алгебра и начала анализа: Учеб. для 10 кл. общеобразоват. учреждений. - М.: Просвещение, 2003. – 383 с.
Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. пособие. – М.: Высшее образование, 2006. – 479 с.
Колмогоров А.Н. Основные понятия теории вероятностей. М.: Фазис, 1998. – 144 с.
http://http://wwwhttp://www.school.edu.ru
http://school-collection.edu.ru
Бунимович Е.А., Булычев В.А., Калманович В.В. Вероятность и статистика в школьном курсе математики (ИУМК). Методическое пособие для учителя. – М., 2008. – 139 с. – Режим доступа: http://school-collection.edu.rБунимович Е.А., Булычев В.А., Калманович В.В. Вероятность и статистика в школьном курсе математики (ИУМК). Методическое пособие для учителя. – М., 2008. – 139 с. – Режим доступа: http://school-collection.edu.ru

некоторые множества. Верно ли утверждение: если A∪B = C, то

A = C\B?

Задача 2. Пусть B и C – некоторые множества. Верно ли утверждение: если A = C\B, то A∪B = C?

утверждение неверно. Имеет место включение C\B ⊂ A. Равенство имеет

место лишь при условии A∩B = ∅ (см. рис.):



Ответ к задаче 2: В общем случае утверждение неверно. Имеет место включение C ⊂ A∪B. Равенство имеет место лишь при условии B ⊂ C (см. рис.):

A

B

B

C

множества.
Задача 3. Верно ли что: A∪(B\C) = (A∪B)\C?
Если равенство

в общем случае неверно, то в какую сторону имеет место включение? При каких условиях равенство все же справедливо? Результаты расчетов отобразить с помощью диаграмм Эйлера – Венна.
Задача 4. Верно ли что: (A\B)∩C = A\(B∩C)?
Если равенство в общем случае неверно, то в какую сторону имеет место включение? При каких условиях равенство все же справедливо? Результаты расчетов отобразить с помощью диаграмм Эйлера – Венна.

утверждение неверно. Имеет место включение A∪(B\C) ⊃ (A∪B)\C. Равенство имеет

место лишь при условии A∩С = ∅ (см. рис.):


Ответ к задаче 4: В общем случае утверждение неверно. Имеет место включение (A\B)∩C ⊂ A\(B∩C). Равенство имеет место лишь при условии A ⊂ C (см. рис.):

B

A

C

B

C

A

любой природы, объединенных по некоторому признаку. Множество считается заданным, если

о каждом элементе можно однозначно сказать, принадлежит он этому множеству или нет.
Замечание: Строго говоря, понятие «Множество» не определяется, а лишь иллюстрируется примерами.
Обычно множества обозначают прописными буквами латинского алфавита (A, B, C, … X, Y, Z), а их элементы – малыми (a, b, c, … x, y, z). Если элемент x принадлежит множеству X, то пишут x ∈ X; в противном случае пишут x ∉ X.
П р и м е р. Если X – множество русских слов из словаря В.И. Даля, а x1 = «семья»; x2 = «family», x3 = «ъ», то x1 ∈ X, а x2, x3 ∉ X.
Определение: Два множества называются равными, если они состоят из одних и тех же элементов. В этом случае пишут X = Y.
П р и м е р. Равными будут множества X = {1; 2; 3; 4} и Y – множество корней уравнения (x – 1)(x – 2)(x – 3)(x – 4) = 0.

обозначается символом ∅.
П р и м е р. Пустым будет

множество X действительных корней уравнения x2 + 1 = 0; в этом случае X = ∅.
Определение: Множество, содержащее конечное число элементов, называются конечным; множество содержащее бесконечное число элементов, называется бесконечным. (В последнем случае бесконечные множества подразделяются на счетные и несчетные).
Если множество конечно, то его можно задать указанием всех элементов, которые ему принадлежат. В этом случае пишут: A = {a1; a2; …; an} – множество A содержит n элементов a1; a2; …; an; тем самым задается список элементов множества. Два списка элементов одного и того же множества могут отличаться лишь порядком элементов в них.
Для большинства приложений порядок элементов в множестве оказывается несущественным, хотя возможно рассмотрение и упорядоченных множеств, список элементов в которых строится по заранее определенному принципу. Такими свойствами, например, обладает множество слов какого-либо языка, упорядоченных по лексикографическому (алфавитному) признаку.

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

этом случае пишут X = {x: P(x)}, где P(x) – характеристическое свойство, т.е. условие, которому удовлетворяют все элементы множества X. Иногда этот подход удобен и для задания конечных множеств.
П р и м е р. Множество A цифр десятичной системы исчисления конечно и может быть задано перечислением всех своих элементов: A = {0; 1; 2; 3; 4; 5; 6; 7; 8; 9}. Множество B учеников в классе конечно и может быть задано перечислением всех своих элементов, например, в виде списка в классном журнале. Множество равносторонних треугольников бесконечно и в этом случае указывают: Y = {ΔABC: AB = BC = CA}.

Эйлера – Венна. Здесь каждое множество символически изображается кругом (овалом)

(рис. 1).
  
 
Рис. 1
Определение: Если каждый элемент множества X является в то же время элементом множества Y, то X называется подмножеством множества Y. В этом случае говорят, что X включено в Y и пишут X ⊆ Y или, эквивалентно, Y ⊇ X. Если, сверх того, множество Y содержит элементы, которые не принадлежат множеству X, то включение является строгим: X ⊂ Y или, эквивалентно, Y ⊃ X (рис. 2).


Рис. 2

C = A∩B, состоящее из элементов, которые принадлежащих как множеству

A, так и множеству B. Это можно записать как C = A∩B = {x: x ∈ A и x ∈ B} (рис. 3).



Рис. 3

Замечание: Когда речь о двух множествах, то, в общем случае, каждое из них может содержать два типа элементов (два непересекающихся подмножества). А именно, i) собственные элементы, которые принадлежат исключительно данному множеству, и ii) элементы, общие с другим множеством:
A = {x: xA ∪ xAB}; B = {x: xB ∪ xAB}.
Здесь учтено, что {xAB} = {xBA}. В этих обозначениях пересечением множеств будет множество C = {x: xAB}.

C = A∪B, состоящее из элементов, принадлежащих хотя бы одному

из множеств A, B (рис. 4). Это можно записать как C = A∪B = {x: x ∈ A или x ∈ B} или, с учетом возможных типов элементов, C = A∪B = {x: xA ∪ xB ∪ xAB}.






Рис. 4.

= A\B, состоящее из собственных элементов, принадлежащих исключительно множеству A.

Этот факт можно записать как C = A\B = {x: x ∈ A и x ∉ B} или, с учетом возможных типов элементов, C = A\B = {x: xA} (рис. 5).
 




Рис. 5

Замечание: Когда речь о числовых множествах, то, в общем случае, при нахождении разности C = A\B из множества A следует удалить граничные точки, общие с множеством B.

данной задаче, называется универсальным. Разность Ā = U\A называется дополнением

множества A. Поскольку U ⊃ A, то U = {x: xU ∪ xUA}; A = {x: xUA}; и дополнение множества Ā = U\A = {x: xU} (рис. 6).

 
 
Рис. 6

П р и м е р. Пусть множество A – множество учащихся в 11а классе; B – в 11б классе; C – в 11в классе. Тогда множество U учащихся всех трех 11-x классов (11а, 11б, 11в) будет универсальным по отношению ко множеству A, а дополнением множества A будет множество Ā = U\A = B∪C.
Определение: Мощностью множества A с конечным числом элементов называется число его элементов; это обозначается как n(A) или |A|.

свойства действий над действительными числами. Приведем некоторые из них:
A∪B =

B∪A;
A∩B = B∩A;
(A∪B)∪C = A∪(B∪C);
(A∩B)∩C = A∩(B∩C);
(A∪B)∩C = (A∩C)∪(B∩C);
(A∩B)∪C = (A∪C)∩(B∪C);
(Ā) = A;
∅ = U;
U = ∅;
A ∩ B = A ∪ B;
A ∪ B = A ∩ B, и др.

Моргана.
Доказательство: Ясно, что A ⊂ U; B ⊂ U. В

общем случае указанные множества содержат следующие типы элементов:
U = {x: xU ∪ xUA ∪ xUB ∪ xUAB};
A = {x: xUA ∪ xUAB};
B = {x: xUB ∪ xUAB}.
Соответственно,
A∩B = {x: xUAB} и A∩B = {x: xU ∪ xUA ∪ xUB};
A = {x: xU ∪ xUB}; B = {x: xU ∪ xUA} и A ∪ B = {x: xU ∪ xUA ∪ xUB}.
Равенство (10) доказано. Аналогично,
A∪B = { x: xUA ∪ xUB ∪ xUAB } и A∪B = {x: xU};
A = {x: xU ∪ xUB}; B = {x: xU ∪ xUA} и A ∩ B = {x: xU}.
Равенство (11) доказано.

биологии, лингвистике, социологии, экономике, юриспруденции и др. науках лежит операция

разбиения множества на попарно непересекающиеся части.
Определение: Пусть U – некоторое множество и Xk – система подмножеств множества U, обладающая следующими свойствами:
Объединение всех множеств Xk совпадает с U, т.е. U = ∪ Xk;
Множества Xk попарно не пересекаются, т.е. если k ≠ m, то Xk ∩ Xm = ∅.
П р и м е р. Множество всех действительных чисел R разбивается на два класса непересекающихся числовых множеств – на множество Q рациональных и множество Ir – иррациональных чисел: R = Q∪Ir, причем Q∩Ir = ∅. Множество всех слов русского языка разбивается на непересекающиеся классы слов, начинающихся с буквы а, б, в, ….

5 разных чашек и 3 разных блюдца. Сколькими способами можно

купить чашку с блюдцем?
Задача 2. Маша на свой день рождения пригласила в гости трех лучших подруг - Дашу, Глашу и Наташу. Когда все собрались, то по случаю дня рождения Маши решили обняться - каждая пара по одному разу. Сколько получилось разных пар?
Задача 3. На шахматном турнире каждый участник с каждым сыграл по одной партии. Всего сыграно 36 партий. Сколько шахматистов участвует в турнире?
Задача 4. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?
Задача 5. (Шутка) Как-то раз в воскресенье семеро друзей зашли в кафе, уселись за один столик и заказали мороженое. Хозяин кафе сказал, что если друзья в каждое следующее воскресенье будут садиться по-новому и перепробуют все способы посадки, то с этого момента он обещает кормить их мороженым бесплатно. Удастся ли друзьям воспользоваться предложением хозяина кафе?
Задача 6. Докажите, что среди 9 человек есть либо 3 попарно знакомых, либо 4 попарно незнакомых.

задаче 2: n = C42 = 6;
Ответ к задаче 3:

n = 9
Ответ к задаче 4: n = 54 = 625
Ответ к задаче 5: Различных способов посадки 7 друзей n = 7! = 5040; 5040 недель ≈ 96 лет.
Решение задачи 6: Присвоим каждому из 9 человек номера от 1 до 9; тогда множество X этих людей есть X = {x1; x2; …; x9}. Выберем произвольного человека, например, x1 и каждого из оставшихся 8-ми человек отнесем к одному из двух непересекающихся классов: A – множество людей, знакомых с x1 и B – множество людей, незнакомых с x1. Тогда минимальное число людей в каждом классе не может быть меньше 4 чел.

из некоторой совокупности объектов элементы, обладающие тем или иным свойством,

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

из 30 вопросов на которые нужно дать ответ «Да» или

«Нет». Сколько существует различных вариантов ответов на вопросы теста?
Задача 2. Сколько существует подмножеств множества S, содержащего 5 элементов?
Задача 3. На блюде лежит 7 яблок и 4 груши. Каким количеством способов можно выбрать один плод?

вопрос, то полное количество вариантов ответов на 30 вопросов теста

составляет n = 230.
Ответ: n = 230.
Решение задачи 2: Пусть S = {s1; s2; s3; s4; s5}. Сопоставим каждому подмножеству множества S битовую строку длины 5 (по числу элементов). Если k-ый элемент принадлежит формируемому подмножеству, то сопоставляем ему 1; в противном случае – 0. В итоге получаем битовую строку длины 5, заполненную 0 или 1. Например, подмножеству {s1; s2; s5} соответствует битовая строка 11001. Всего существует n = 25 = 32 различных битовых строк длины 5.
Ответ: n = 25 = 32.
Решение задачи 3: Существует 7 вариантов выбора яблока и 4 варианта выбора груши: всего 11 вариантов.
Ответ: n = 11.

Пусть задана последовательность событий
E1; E2; …; Em
таких, что событие

E1 осуществляется n1 способами, событие E2 осуществляется n2 способами (после осуществления события E1), …, событие Em осуществляется nm способами (после осуществления событий E1; E2; …; Em–1).
Тогда существует n1 × n2 × … nm способов осуществления всей последовательности событий.

…; Sm – попарно непересекающихся множеств (т.е. при i ≠

j пересечение Si ∩ Sj = ∅) и пусть множество S1 содержит n1 элементов; S2 содержит n2 элементов; …; множество Sm содержит nm элементов.
Тогда количество вариантов выбора одного элемента из S1 или S2; …; или Sm равно n1 + n2 + … + nm.
На языке теории множеств это утверждение может быть переписано как
|S1 ∪ S2 ∪ … ∪ Sm| = |S1| + |S2| + … + |Sm|
при условии, что пересечение Si ∩ Sj = ∅ при i ≠ j .

содержащих ровно одну цифру 6?

и 1000, содержащих ровно одну цифру 6 на непересекающиеся классы:

1-цифровое множество S1, 2х-цифровое множество S2 и, наконец, 3х-цифровое множество S3. Очевидно,
|S1| = |6| = 1;
|S2| = |6; 6 | + |6, 0; 6| = 9 + 8 = 17;
|S3| = |6; 6; 6| + |6, 0; 6; 6| + | 6, 0; 6; 6| = 9⋅9 + 8⋅9 + 8⋅9 = 81 + 72 + 72 = 225.
|S| = |S1| + |S2| + |S3| = 1 + 17 + 225 = 243.
Ответ: |S| = |S1| + |S2| + |S3| = 243.

содержащих хотя бы одну цифру 6?

и 1000, на непересекающиеся подмножества чисел, содержащих 6:
1-цифровое множество

S1 может содержать ровно одну цифру 6;
2-цифровое множество S2 может содержать одну или две цифры 6;
3-цифровое множество S3 может содержать одну, две или три цифры 6.
В первом случае, как и в предыдущем примере:
|S1| = |6| = 1.
Во втором случае:
|S2| = |6; 6| + |6, 0; 6| + |6; 6| = 9 + 8 + 1 = 17 + 1 = 18.
Наконец, в третьем случае: |S3| = |6; 6; 6| + | 6, 0; 6; 6| + | 6, 0; 6; 6| +
+ |6; 6; 6| + |6; 6; 6| + | 6, 0; 6; 6| + |6; 6; 6| =
= 9⋅9 + 8⋅9 + 8⋅9 + 9 + 9 + 8 + 1 = 81 + 72 + 72 = 225 + 26 + 1 = 252.
|S| = |S1| + |S2| + |S3| = 1 + 18 + 252 = 271.
Ответ: |S| = |S1| + |S2| + |S3| = 271.

ни на 2, ни на 3, ни на 5? Есть

ли среди этих чисел составные, и если да, то сколько их?

является четным числом и поэтому не годится) в виде:
a

= 10⋅l + k.
С учетом условия, k ∈ {1; 3; 7; 9}; l ∈ {0; 1; 2; 3; 4; 5; 6; 7; 8; 9},
причем сумма l + k не должна делиться на 3.
Суммы l + k (красным выделены суммы, кратные 3)






Ответ: |A| = 26: A = {1; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 49; 53; 59; 59; 61; 67; 71; 73; 77; 79; 83; 89; 91; 97}.

двух пересекающихся множеств. Пусть S и T – произвольные множества

(возможно пересекающиеся). Тогда количество элементов, которые можно выбрать из S или T равно |S ∪ T| = |S| + |T| – |S∩T|.
Доказательство. Для доказательства воспользуемся законами алгебры множеств. Нетрудно доказать, что справедливы следующие разложения множеств на попарно непересекающиеся подмножества:
S ∪ T = (S\T) ∪ (T\S) ∪ (S∩T);
S = (S\T) ∪ (S∩T);
T = (T\S) ∪ (S∩T).
В соответствии с комбинаторным принципом сложения для непересекающихся множеств имеем:
|S ∪ T| = |S\T| + |T\S| + |S∩T|;
|S| = |S\T| + |S∩T|;
|T| = |T\S| + |S∩T|.
Складывая два последних равенства и вычитая сумму из первого, получим требуемое утверждение: |S ∪ T| = |S| + |T| – |S∩T|, ч.т.д.

математику; 75 – историю; 45 чел – и то и

другое. Сколько человек изучают математику или историю? Сколько человек не изучают ни математику, ни историю?

математику (возможно, совместно с историей); H – множество студентов, изучающих

историю (возможно, совместно с математикой). Тогда M∩H – множество студентов, изучающих и математику, и историю. По условию:
|M| = 60; |H| = 75; |M∩H| = 45.
Согласно комбинаторному принципу сложения для двух произвольных множеств имеем для числа студентов, изучающих математику или историю:
|M∪H| = |M| + |H| – |M∩H| = 60 + 75 – 45 = 90 чел.
Тогда число студентов, не изучающих ни математику, ни историю, составляет
| M ∪ H | = 100 – 90 = 10 чел.
Ответ: |M∪H| = |M| + |H| – |M∩H| = 90 чел; | M ∪ H | = 10 чел.

Переставляя их, будем получать различные порядки их следования.
Определение: Перестановками называются

упорядоченные n-элементные множества, различающиеся порядком элементов. Число перестановок n-элементного множества может быть найдено по формуле Pn = n!
Задача 7. В коробке имеется 4 пронумерованных шара с номерами {1; 2; 3; 4}. Шары вынимаются по одному и кладутся в ряд, образуя 4-значное число. Сколько различных чисел может быть получено при вынимании шаров? Сколько из них будет начинаться с 1?
Решение: Количество 4-значных чисел, очевидно, равно числу перестановок из 4 цифр {1; 2; 3; 4} и составляет P4 = 4! = 24.
Количество 4-значных чисел, с единицей на первой позиции, очевидно, равно числу перестановок из 3 оставшихся цифр {2; 3; 4} и составляет P3 = 3! = 6.
Ответ: P4 = 4! = 24; P3 = 3! = 6.

20 чел и из них требуется выбрать президента, вице-президента, секретаря

и казначея (должности не совмещаются).
Решение: Имеется 20 вариантов выбора президента; 19 вариантов выбора вице-президента (после того, как президент выбран); 18 вариантов выбора секретаря из оставшихся членов организации и, наконец, 17 вариантов выбора казначея.
Число вариантов выбора 4-х должностных лиц в определенном порядке следования составляет:
20 × 19 × 18 × 17 = 20!/16! = 20!/(20-4)! = 116280.
Ответ: A204 = 116280.
 Определение: Размещениями из n элементов по k элементов называются упорядоченные k-элементные подмножества n-элементного множества, различающиеся порядком элементов. Число размещений из n элементов по k элементов может быть найдено по формуле
Ank = n!/(n-k)! = n(n – 1)(n – 2) … (n – k + 1).

имеются ткани пяти различных цветов? Сколькими способами можно составить трехцветный

полосатый флаг, если одна полоса должна быть красной?
Решение: Количество способов выбрать ткани трех различных цветов из 5-ти может быть найдено как число размещений:
n1 = A53 = 5!/(5-3)! = 5⋅4⋅3 = 60.
Если одна полоса должна быть красной, то две оставшиеся полосы могут быть одного из 4-х оставшихся цветов. Количество способов выбрать ткани двух различных цветов из 4-х может быть найдено как число размещений:
n2 = A42 = 4!/(4-2)! = 3⋅4 = 12.
Ответ: n1 = 60; n2 = 12.

20 чел и из них требуется выбрать комитет из 4-х

человек, при этом порядок персоналий безразличен.
Решение: Имеется 20 вариантов выбора первого члена комитета; 19 вариантов выбора второго члена комитета (после того, как первый выбран); 18 вариантов выбора третьего члена комитета из оставшихся членов организации и, наконец, 17 вариантов выбора 4-го члена комитета.
Число вариантов выбора 4-х должностных лиц составляет
A204 = 20 × 19 × 18 × 17 = 116280.
Полученное число следует уменьшить в P4 = 4! раз, так как порядок следования персоналий значения не имеет, а число перестановок элементов в выбранной четверке должностных лиц составляет именно P4. Поэтому число способов выбора членов комитета
C204 = A204/P4 = 20! / (20-4)!⋅4! = 20 × 19 × 18 × 17 / 24 = 4845.
  Ответ: C204 = 4845.

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

из n элементов по k элементов может быть найдено по формуле
Cnk = Ank / Pk = n! / (n-k)!⋅k!

и четыре минуса?

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

достаточно найти число способов выписать шесть плюсов на 10 позициях. Количество способов сделать это может быть найдено как число сочетаний из 10 элементов по 6:
C106 = 10! / (10-6)!⋅6! = 10! / 4!⋅6! = 7⋅8⋅9⋅10 / 24 = 210.
Ответ: n = C106 = 210.
Замечание. Очевидно, что аналогичное рассуждение с точки зрения размещения четырех «-» на 10 позициях должно приводить к тому же результату, и это действительно так:
C104= 10! / (10-4)!⋅4! = 10! / 6!⋅4! = C106 = 210.
Вообще,
Cnk = Cnn-k .