Основные правила комбинаторики. Выборки, сочетания. Аксиомы теории вероятностей

Лемма 5.1. Из m элементов a₁, …, a_n первой группы и n элементов b₁, …, b_n второй группы можно составить ровно m∙ n упорядоченных пар вида (a_i, b_j), содержащих по одному элементу из каждой группы.

(a₁, b₁), (a₁, b₂), …, (a₁, b_n), Всего m∙ n пар

(a₂, b₁), (a₂, b₂), …, (a₂, b_n), m строк

… … … … … …...

(a_m, b₁), (a_m, b₂), …, (a_m, b_n).

n столбцов

Пример 5.2. В колоде карт 4 масти (черва, пика, трефа, бубна), в каждой масти по 9 карт или по 13 карт, тогда в колоде либо n=4∙ 9=36 карт, либо n=4∙ 13=52 карты.

Лемма 5.3. Из n₁ элементов первой группы a₁, a₂, …, ,

n₂ элементов второй группы b₁, b₂, …, ,

и т.д. … … … … … … … …

n_k элементов k -той группы x₁, x₂, …, .

можно составить ровно n₁ ∙ n₂ ∙ …∙ n_k различных упорядоченных комбинаций вида ( …, ), содержащих по одному элементу из каждой группы.

Пример 5.4. При бросании двух игральных костей число различных упорядоченных комбинаций следующее: N = 6² = 36; при бросании трех костей – N=6³=216.

Леммы 5.1 и 5.3 называются основными правилами комбинаторики.

Пусть имеется множество из n элементов { a₁, a₂, …, a_n }. Будем рассматривать выборки объёма k вида (, , …, ) из n элементов. Все выборки можно классифицировать по двум признакам:

1) упорядоченные и неупорядоченные;

2) с возвращением и без возвращения.

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

Пример 5.5. Рассмотрим множество, состоящее из трёх элементов {1, 2, 3}. Составим таблицу числа выборок объёма k =2 из трёх элементов.

Общая таблица числа выборок объёма из элементов:

nk		с возвращением
		без возвращения
упорядоченные	неупорядоченные	выборки

Определение 5.6. Упорядоченная выборка без возвращения называется размещением.

Число размещений = .

Пример 5.7. В лифт 12-этажного дома зашли 3 человека. Найти вероятность того, что все вышли на разных этажах.

Ω ={(i₁, i₂, i₃) | i₁, i₂, i₃ {2, 3, …, 12}}, { i₁ i₂, i₂ i₃ } – дополнительное условие для события А. Первое (Ω – упорядоченные выборки с возвращением, n =11³. Число благоприятствующих исходов k = = =9∙ 10∙ 11. По классическому определению вероятности Р(А)= = = = .

Определение 5.8. Перестановкой из k элементов называется совокупность этих же элементов, записанных в произвольном порядке. Число перестановок из k элементов P_k = k! (0! =1).

Определение 5.9. Произвольное k -элементное подмножество множества, состоящего из n элементов, называется сочетанием из n элементов по k элементов.

Обозначается число сочетаний из n элементов по k элементов через

= ; k {0, 1, …, n }.

Свойства сочетаний:

1) = =1;

2) = = n;

3) = ;

4) + = .