Что значит разбиение множества

Разбиение множества

Одной из наиболее часто встречающихся операций над множествами является операция разбиения множества на систему подмножеств.

Так, система курсов данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Пример. Продукция предприятия: — высший сорт, I, II, брак.

Рассмотрим некоторое множество M и систему множеств

Система множеств M называется разбиением множества M, если она удовлетворяет следующим условиям:

1. Любое множество X из M является подмножеством множества М

1. Любые два множества X и Y из М являются непересекающимися

1. Объединение всех множеств, входящих в разбиение, дает множество M

Тождества алгебры множеств

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

Если алгебраические выражения V(X,Y,Z) и S(X,Y,Z) представляют собой одно и то же множество, то их можно приравнять друг другу, получая алгебраическое тождество вида V(X,Y,Z) = S(X,Y,Z)

1. (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогичное дистрибутивному закону (a+b)c=(a+c)(b+c) в обычной алгебре).
2. (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
3. Если Y⊆X, то X∩Y=Y, X∪Y=X. Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит пересечение этих множеств, то есть общая множеств Х и Y совпадает с Y. В объединение множеств X и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества Х. Следовательно, X∪Y совпадает с X.
4. Пусть в примере 3 Y=X. Тогда, учитывая, что X⊆X, то X∩Х=Х, X∪Х=X. (идемпотентность).
5. Докажем тождество (X∪Y)¯=X¯∩Y¯. Предположим, что х∈(X∪Y)¯, то есть х∉X∪Y. Это значит, что х∉X и х∉Y, то есть и x&isinX¯ и x&isinY¯;. Следовательно, x∈X¯∩Y¯. Предположим теперь, что y∈X¯∩Y¯, то есть y∈X¯ и y∈Y¯. Это значит, что y∉X и y∉Y, то есть что y∉X∪Y. Следовательно, y∈(X∪Y)¯.
6. Тождество (X∩Y)¯=X¯∪Y¯. Обычно тождества 5) и 6) называются тождествами де-Моргана.
7. (A\B)∩C=(A∩C)\B=(A∩C)\(B∩C)
8. A\B=A\(A∩B)
9. A=(A∩B)∪(A\B)

Дополнение к занятию «операции над множествами»

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

Для симметрической разности выполняются следующие законы:

1. 1) A⊕B = B ⊕A — коммутативность,
2. 2) A⊕(B⊕С) = (A⊕B)⊕С — ассоциативность,
3. 3) A⊕∅ = А=∅⊕A — существование нейтрального элемента,
4. 4) A ⊕А = ∅
5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивность относительно пересечения.

Источник

Разбиение множества

Определение:
Пусть $A$ — некоторое непустое множество ($A \neq \emptyset$). Разбиением множества $A$ называется непустое множество подмножеств $A_j \subset A$, $j \in I$ ($I$ — некоторое множество индексов), такое, что выполняются два условия:

1. $\underset <\bigcup>A_j = A$
2. $A_i \bigcap A_j = \emptyset$, для любых $i, j \in I$ таких, что $i \neq j$

Пример 1:
Множество $\mathbb R$ можно разбить следующим образом:
$A_1 = \mathbb R^+$, $A_2 = \left\<0\right\>$, $A_3 = \mathbb R^-$
Графически это можно изобразить следующим образом:
Пример 2:
Аналогично множество $\mathbb Z$ можно представить в виде разбиения на множества четных и нечетных целых чисел:
$A_1 = 2\mathbb Z$, $A_2 = 2\mathbb Z + 1$
Графически это можно представить следующим образом:

Пример 3:
Пусть задано множество $A$, состоящее из трех элементов $\left\$. Существует $5$ способов разбить это множество:

Литература:

• Белозеров Г.С. Конспект лекций по линейной алгебре

Источник

Разбиения множеств: размещения и перестановки, сочетания

Разбиение множества на непересекающиеся подмножества – еще одна комбинаторная операция. С ее частным случаем первый встречаются, когда рассматривают сочетания без повторений из n по k . Действительно, результатом повторной выборки из n элементов по к можно считать разбиение исходного n -элементного множества X на два непересекающихся подмножества – подмножество выбранных элементов Х ₁ мощности k и подмножество оставшихся элементов Х ₂ мощности ( n – k ). Учитывая формулу

получаем, что существует всего различных разбиений n -элементного множества на два непересекающихся подмножества мощности k и ( n — к). Заметим, что в данном случае два разбиения считаются разными, если найдется такой элемент исходного множества, который при одном разбиении попал в подмножество выбранных элементов, а при другом разбиении — в подмножество оставшихся элементов. Поэтому, вычисляя количество различных разбиений, мы учитываем, в какое из подмножеств попал каждый конкретный элемент исходного множества.[9]

В общем случае комбинаторная операция разбиения состоит в разбиении исходного n -элементного множества на непересекающиеся подмножества, причем некоторые из подмножеств могут оказаться пустыми. Если некоторые из подмножеств имеют одинаковую мощность, то возможны два подхода к пониманию того, какие варианты разбиения считаются различными. При одном подходе подмножества одинаковой мощности различаются, а при другом – нет. Поэтому при первом подходе два варианта разбиения считаются различными, если хотя бы один из элементов исходного множества при этих разбиениях попал в разные подмножества, даже если они имеют одинаковые мощности (иными словами, важно, кто в каком подмножестве оказался). При втором подходе разбиения считаются разными, если хотя бы один элемент исходного множества при таких разбиениях попал в подмножества разной мощности. Если же в некотором разбиении два подмножества одинаковой мощности целиком обменяются своими элементами, то полученное и исходное разбиения считаются неразличимыми. Иными словами, при втором подходе не важно, в какое из подмножеств одинаковой мощности попал элемент, а важно лишь с кем он оказался в этом подмножестве. Ясно, что число различных вариантов разбиения при первом подходе больше, чем при втором.[21]

3.1. Размещения и перестановки

Рассмотрим комбинаторные конфигурации, называемые размещениями и перестановками, и соответствующие им комбинаторные числами.

Задача 3.1.1. Для обеспечения одного из вариантов работы заводского конвейера необходимо последовательно нажать две из трех различных кнопок, обозначенных на пульте управления буквами , и . Сколько может существовать различных вариантов работы конвейера?

На этот вопрос можно дать различные ответы в зависимости от уточнения его формулировки. Например:

– предусмотрен ли вариант работы, для включения которого необходимо нажать дважды на одну и ту же кнопку , т.е. вариант ?

– существуют ли варианты, отличающиеся порядком нажатия кнопок и ? Иными словами, возможны ли варианты или ?

Следовательно, при поиске числа различных вариантов работы конвейера может оказаться возможным:

1. Повторное нажатие кнопки, а также различный порядок нажатия кнопок. В этом случае имеется 9 вариантов:

2. Запрещено дважды нажимать одну и ту же кнопку. Порядок нажатия кнопок существен. В этой ситуации – 6 вариантов: , , , , , .

3. Повторное нажатие кнопок предусмотрено, но порядок нажатия кнопок не существенен. Тогда имеется также 6 вариантов: , , ,, , .

4. Наконец, запрещено дважды нажимать одну и ту же кнопку, и порядок нажатия кнопок не существенен. В этом случае – 3 варианта: , , .

Таким образом, при решении конкретных задач на подсчет количества способов или вариантов выбора элементов из заданного множества необходимо четко понимать, о каком способе или варианте выбора идет речь. Поэтому различные выборки получили в комбинаторике специальные названия.

В общем случае выборка определяется так. Пусть – множество из n элементов. Любая совокупность элементов из множества Х называется выборкой из n элементов по или кратко – ( n , r )-выборкой.

Например, -выборкой является выборка или выборка из множества .[10]

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

Например, различными являются -выборки pq и qp из множества . Телефонные номера и являются различными (10, 7)-выборками из множества цифр.

Из определения декартовой степени множества следует, что упорядоченная ( n , r )-выборка является элементом множества .

Упорядоченная ( n , r ) – выборка, все элементы которой различны, называется размещением из n элементов по r без повторений или ( n , r )-размещением без повторений.

Например, (10, 7) – размещением без повторений является (10, 7) – выборка из множества цифр.

Упорядоченная ( n , r )-выборка, элементы которой могут повторяться, называется размещением r элементов из n с повторениями или ( n , r )-размещением с повторениями.

Например, (3, 6) – размещением с повторениями является (3, 6)-выборка из множества .

Число всех размещений из n элементов по r без повторений обозначается , а число всех размещений из n элементов по r с повторениями – .

Например, для множества имеется всего 6 размещений из 3 элементов по 2 без повторений: , , , , , . Поэтому . Если добавить к этим размещениям (3, 2) – выборки , , с повторениями, то получим .

Теорема 3.1.1. при и при .

Доказательство. Пусть . Каждое размещение из n элементов по r без повторений является упорядоченной последовательностью r элементов, члены которой выбраны из n данных элементов и попарно различны. Первый элемент этой последовательности может быть выбран n способами. После выбора первого элемента для выбора второго элемента последовательности остается способ. После выбора второго элемента для выбора третьего есть способа и т.д. Поэтому, после выбора -го элемента последовательности ее r -й член может быть выбран способами. В силу обобщенного правила произведения

Умножая и деля правую часть полученной формулы на , получим .Определим 0! = 1 (что соответствует пустой выборке). Тогда

Пусть . Так как из n данных элементов нельзя выбрать более n различных элементов, .

Задача 3.1.2. В финале областного конкурса СТЭМов присуждаются три диплома: I , II и III степени. В конкурсе участвует 9 студенческих театров миниатюр. Сколько существует различных вариантов распределения дипломов?

Решение . Рассматриваются выборки, в которых учитывается, какие три театра миниатюр из девяти, участвующих в конкурсе, выйдут в финал и как произойдет распределение мест в финале. Ясно, что один и тот же театр не может одновременно получить два или три диплома. Поэтому для ответа на вопрос задачи надо найти число размещений из 9 элементов по 3 без повторений. Имеем .

Доказательство. Каждое размещение из n элементов по r с повторениями является упорядоченной последовательностью длины r . При этом каждый член этой последовательности может быть выбран n способами. По обобщенному правилу произведения . ■

Задача 3.1.3. Найдите число всех подмножеств n -эле-ментного множества Х.

Решение . Пронумеруем элементы множества Х с помощью первых n натуральных чисел. Тем самым определяется биекция . Поэтому число подмножеств множества Х равно числу подмножеств множества M = <1,…, n >.

Каждое подмножество из M закодируем последовательностью длины n , составленной из 0 и 1. Если число i из M входит в подмножество, то на i -ом месте последовательности ставим 1, в противном случае – 0.

Например, подмножества <1>, <2, 3>, <1, 2, 3, 4>четырехэлементного множества M = <1, 2, 3, 4>кодируются последовательностями 1000, 0110, 1111. Обратно, каждой такой последовательности соответствует единственное подмножество из M . Например, последовательностям 0000, 0101 соответствуют пустое множество и подмножество <2, 4>.

C помощью указанного кодирования задается биекция множества М на множество построенных последовательностей. Значит, подмножеств множества М столько же, сколько последовательностей. Эти последовательности являются размещениями из двух элементов (0 и 1) по n c повторениями. Поэтому искомое число подмножеств равно .

Примечание. Составляя выборки с повторениями, обычно предполагают, что выбор элементов из данного множества производится с возвращением, т.е. считают, что выбранный из множества элемент сразу же возвращается назад или автоматически замещается таким же элементом.[10]

Размещения из n элементов по n без повторений называются перестановками из n элементов. Число перестановок из n элементов обозначают P _n .

В силу теоремы 3.1.1.

Задача 3.1.4. В областном конкурсе СТЭМов принимают участие 9 студенческих театров. Порядок их выступлений определяется жеребьёвкой. Сколько существует вариантов в определении порядка выступления?

Решение . Число вариантов в определении порядка выступлений равно числу перестановок из 9 элементов: P ₉ = 9! =
= 362880.

Задача 3.1.5. Сколькими способами официант можно рассадить 9 посетителей за круглым столом, если учитывать только порядок соседей?

Решение . Казалось бы, что, как и в предыдущей задаче, ответ равен 9!. Однако это не так, в задаче 2.3 упорядочивание производилось в ряд, а здесь – по кругу. При вращении клиентов вокруг стола соседи слева и справа от любого из них остаются прежними, поэтому такое вращение не меняет их взаимного расположения. Значит, перестановки, переходящие при вращении друг в друга, следует считать одинаковыми. Иными словами, при 9 возможных вращениях из каждой перестановки получается 9 равных ей перестановок. Поэтому искомое число способов равно .

В этой задачей мы имели дело с циклической перестановкой или, короче, циклом . Цикл из элементов записывается в виде , при этом элемент считается соседним с элементом . Поэтому цикл можно записать начиная с любого из элементов , т.е.

Следовательно, число циклов, образованных элементами, равно .

Наряду с выборками из множества , образованного элементами , . будем рассматривать выборки из совокупностей, в которых указанные элементы повторяются заданное число раз. Такие совокупности будем называть мультимножествами и обозначать

Таким образом, мультимножество отличается от множества тем, что один и тот же элемент () может повторяться в нем раз.

Рассмотрим мультимножество, в котором элемент повторяется раз, элемент – раз, и т.д., элемент – раз. Число называется числом элементов мультимножества.

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

В мультимножестве , составленном из элементов множества , элемент повторяется три раза, элемент – четыре, а элемент – один; т.е. =, , .

Задача 3.1.6. С колько различных перестановок с повторениями букв можно сделать в слове «КОЛОБОК».

Решение . Данное слово состоит из семи букв, которые можно переставить способами. Однако, переставляя между собой три буквы «О» или меняя местами две буквы «К», мы новых перестановок не получим. Так как число перестановок трех букв равно , а двух – , то искомое число различных перестановок в раз меньше Стало быть, это число равно .

В общем случае справедлива

Теорема 3.1.3. Число перестановок из n элементов с повторениями, в каждой из которых элемент повторяется раз, элемент – раз, и т.д., элемент – раз вычисляется по формуле

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

в которой последовательно выписаны все элементы , потом все элементы . наконец, все элементы . Элементы можно переставлять друг с другом способами. Но так как все эти элементы одинаковы, то такие перестановки элементов ничего не меняют, т.е. перестановка (*) не изменяется. Точно так же ничего не меняют перестановок элементов . перестановок элементов .

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

Ясно, что в любой другой отличной от (*) упорядоченной последовательности, содержащей все n элементов данного мультимножества, можно делать независимо друг от друга перестановки способами так, что она не изменится. Поэтому число всех искомых перестановок с повторениями в раз меньше, чем число всех перестановок из различных элементов. ■

Задача 3.1.7. Сколько анаграмм можно составить из слова «математика»? (Анаграммой называется «слово», полученное перестановками букв данного слова, независимо от того, имеет оно или не имеет смысловое значение.)

Решение . В слове «математика» 10 букв, среди которых 3 раза встречается буква «а», 2 раза – буква «м» и 2 раза – буква «т». Поэтому число анаграмм

3.2. Сочетания

Пусть – множество из n элементов. Неупорядоченная ( n , r )-выборка, все элементы которой различны, называется сочетанием из n элементов по r без повторений или ( n , r )-сочетанием без повторений. Иными словами, сочетание из n элементов по r без повторений – любое r -элементное подмножество множества X .

Например, если из десяти сотрудников отдела нужно выбрать троих делегатов на заводскую конференцию, то порядок выбора сотрудников не имеет значения. Поэтому любая тройка выбранных сотрудников является (10, 3) – сочетанием без повторений. Но если из десяти цифр на телефонном аппарате необходимо набрать трехзначный телефонный номер, все цифры которого различны, то порядок набора цифр уже имеет значение. Поэтому тройка цифр такого телефонного номера не является сочетанием, а будет (10, 3) – размещением без повторений.

Неупорядоченная ( n , r )-выборка, элементы которой могут повторяться, называется сочетанием r элементов из n с повторениями или ( n , r )-сочетанием с повторениями.

При одноразовом бросании игральной кости может выпасть от 1 до 6 очков. Если при пятикратном бросании игральной кости последовательно выпало 3, 3, 5, 2 и 4 очка, то эта последовательность очков является (6, 5)-сочетанием с повторениями. Если же последовательность 33524 есть телефонный номер, то порядок расположения цифр существенен, в этом случае выборка 33524 является (10, 5)-размещением с повторениями. (3, 5)-сочетанием с повторениями элементов множества являются выборки , , .

Число сочетаний из n элементов по r без повторений обозначается символом , а число сочетаний из n элементов по r с повторениями – символом .

Сочетания без повторений. Пусть X – конечное множество, состоящее из n элементов. Найдем число всех -сочетаний без повторений из элементов этого множества.

Теорема 3.2.1. при , и при .

Доказательство. Пусть . Если в каждом сочетании из n элементов по (без повторений) выполнить все перестановки (а их для каждого сочетания – ), то получим все размещения без повторений из данных n элементов по . Поэтому или

Из формулы следует, что , т.е.

Умножая на числитель и знаменатель этой дроби, получим

При нельзя выбрать r различных элементов из n данных, поэтому в этом случае полагаем .

Напомним, мы условились считать , что 0! = 1, поэтому полученная формула имеет место и для (пустая выборка), и для : .

Примечание. Формула связывает число сочетаний и размещений из n элементов по без повторений и число перестановок из элементов.

Следствие. Число всех r -элементных подмножеств
n -элементного множества X равно .

Задача 3.2.1. В областном конкурсе СТЭМов участвует
9 театров. Сколькими способами жюри конкурса может выбрать трех участников финала?

Решение . Каждый из 9 СТЭМов может оказаться участником финала. Так как СТЭМы равноправны, число способов выбора финалистов равно .

Задача 3.2.2. Доказать, что для всех справедливо равенство:

Решение . Согласно формуле

Задача 3.2.3. Доказать, что при

Задача 3.2.4. Доказать, что для всех справедливо равенство

Решение . Пусть даны n элементов . Число всех сочетаний по элементов, содержащих элемент и не содержащих элементов с большим индексом, можно образовать способами (т.к. одно место занято самим элементом ). Число всех сочетаний по элементов, содержащих элемент и не содержащих элементов с большим индексом, можно образовать способами. Число всех сочетаний по элементов, содержащих элемент и не содержащих элементов с большим индексом, можно образовать способами и т.д. Наконец, число сочетаний по элементов, содержащих элемент , можно образовать способами. Тогда общее число сочетаний из n элементов по элементов равно .[10]

В то же время, число сочетаний из n элементов по равно . Таким образом, имеем:

Сочетания с повторениями. Для подсчета числа сочетаний из n элементов по r с повторениями используется

Доказательство. Каждому сочетанию с повторениями из n элементов по r , в котором элемент повторяется раз, поставим в соответствие последовательность, в начале которой стоят единиц, затем 0 и следом единиц, снова 0 и единиц и т.д., до единиц в конце строки. Полученная последовательность состоит из единиц (мы выбираем элементов, учитывая их повторяемость) и нулей. Обратно, каждой такой последовательности единиц и –1 нулей соответствует вполне определенное сочетание с повторениями из n элементов по .

Пусть, например, исходное множество состоит из трех элементов. Считая элемент a первым, b – вторым, c – третьим можно составить следующие сочетания с повторениями по 5 элементов: aabcc , acccc , bbccc (на самом деле, порядок следования элементов в этих выборках роли не играет). Этим сочетаниям соответствуют последовательности 1101011, 1001111, 0110111. Обратно, каждой такой последовательности из 5 единиц и 2 нулей соответствует вполне определенное сочетание с повторениями. Например, последовательностям 1011011, 1011110, 1010111 соответствуют сочетания с повторениями , , .

Полученные последовательности из 1 и 0 не что иное, как перестановки с повторениями, в которых один элемент повторяется раз, а второй раз. Согласно формуле число таких перестановок равно . Поскольку между множеством сочетаний с повторениями из элементов по и множеством перестановок с повторениями из единиц и нулей установлено взаимно-однозначное соответствие, формула справедлива. Равенство следует из формулы .

Задача 3.2.5. В цветочном магазине имеется 7 различных сортов цветов. Сколькими способами можно составить букет из 5 цветов?

Решение . Считая, что выбор цветов каждого сорта не ограничен, имеем .

Задача 3.2.6. Сколькими способами 25 человек могут заказать на десерт по порции мороженого, если в ассортименте кафе имеется 5 сортов мороженого и выбор каждого сорта не ограничен?

При решении задач на сочетания с повторениями рассматриваются либо выборки с возвращением, либо -выборки из совокупности предметов разных типов. Во втором случае количество предметов каждого типа считается неограниченным (так было в предыдущих задачах).

В тех случаях, когда выборка происходит из мультимножества, следует быть осторожным. Здесь выбор предметов может оказаться ограниченным. Рассмотрим задачу.

Задача 3.2.7. Сколькими способами можно составить букет из 5 роз, если в наличии имеется 5 одинаковых красных, 4 одинаковых белых и 3 одинаковых желтых розы?

Решение . В этой задаче полностью составить букет можно только из красных роз, выбор белых и желтых роз ограничен. Поэтому, если, как и в предыдущих задачах, воспользоваться формулой , решение будет неверным.

Нетрудно, однако, перебрать все возможные варианты составления букета. Буквы К, Б и Ж в выборках будут означать включение в букет красной, белой и желтой розы соответственно. Последовательно составим все возможные букеты с 5, 4, 3, 2, 1 и 0 красными розами.

КККББ, КККБЖ, КККЖЖ;

ККБББ, ККББЖ, ККБЖЖ, ККЖЖЖ;

КББББ, КБББЖ, КББЖЖ, КБЖЖЖ;

ББББЖ, БББЖЖ, ББЖЖЖ.

Итак, число всех выборок равно .

Примечание. Аналогичные ситуации могут возникнуть и при выборке из мультимножества -размещений с повторениями (в случае, когда число предметов хотя бы одного типа меньше, чем ).[10]

Источник