Виды выборок по m элементов из n элементов

Формула включений и исключений для трех и для 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 ₁È…È A_n |=| A ₁|+…+| A_n |-| A ₁Ç A ₂|-| A ₁Ç A ₃|-…-| A_{n -1}Ç A_n |+

+| A ₁Ç A ₂Ç A ₃|+| A ₁Ç A ₂Ç A ₄|+…+| A_{n -2}Ç A_{n -1}Ç A_n |+…

…+(-1) ^{n -1}| A ₁Ç A ₂Ç…Ç A_{n -1}Ç A_n |.

Комбинации, или выборки, – это различные конструкции элементов заданного множества, подчиненных тем или иным условиям. Простейшие из них – это выборки из 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 -множество: . Только сочетание мы записываем мы проще: a₁a₂…a _m.