Виды выборок по 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.