Формула включений и исключений для трех и для n множеств.
Метод включений и исключений при подсчете числа элементов объединения трех множеств заключается в следующем: 1) подсчитываем элементы всех трех множеств без различения элементов; 2) вычитываем число элементов, повторяющихся в каких-либо двух списках; 3) прибавляем число элементов, которые повторяются в трех множествах, поскольку они два раза вычитывались.
Теорема. | A È B È C |=| A |+| B |+| C |-| A Ç B |-| A Ç C |-| B Ç C |+| A Ç B Ç C |.
Доказательство. Так как A È B È C =(A È B)È C, то, в силу теоремы 1,
| A È B È C |=| A È B |+| C |-|(A È B)Ç C |.
Используем свойство дистрибутивности пересечения относительно объединения: (A È B)Ç C =(A Ç C)È(B Ç C). И ещё раз применим теорему 1:
|(A Ç C)È(B Ç C)|=| A Ç C |+| B Ç C |-|(A Ç C)Ç(B Ç C)|.
По свойствам пересечения, (A Ç C)Ç(B Ç C)= A Ç B Ç C.
Сформулируем формулу включений и исключений для n множеств:
| A 1È…È An |=| A 1|+…+| An |-| A 1Ç A 2|-| A 1Ç A 3|-…-| An -1Ç An |+
|
|
+| A 1Ç A 2Ç A 3|+| A 1Ç A 2Ç A 4|+…+| An -2Ç An -1Ç An |+…
…+(-1) n -1| A 1Ç A 2Ç…Ç An -1Ç An |.
Комбинации, или выборки, – это различные конструкции элементов заданного множества, подчиненных тем или иным условиям. Простейшие из них – это выборки из n элементов по m, построения, в которых из заданного n -множества надо выбрать элементы m раз, упорядоченных или неупорядоченных, с повторениями или без повторений.
Размещения из n элементов по m – это упорядоченные выборки элементов из заданного n -множества по m.
Приведем все размещения из 3 элементов множества по 2.
С повторениями: .
Без повторений: .
Приведем все размещения из 2 элементов множества по 3.
С повторениями: .
Сочетания из n элементов по m – это неупорядоченные выборки элементов из заданного n -множества по m.
Приведем все сочетания из 3 элементов множества по 2.
С повторениями: .
Без повторений: .
Приведем все сочетания из 2 элементов множества по 3.
С повторениями: .
Математическое представление выборок. Размещение из n элементов по m – это просто последовательность длины m элементов из n -множества.
Сочетание без повторений из n элементов по m – это просто подмножество n -множества, содержащее ровно m элементов.
Сочетание с повторениями из n элементов по m – это график некоторого отображения a из множества первых m натуральных чисел в заданное n -множество: . Только сочетание мы записываем мы проще: a1a2…a m.