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

 

Лемма 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 из трёх элементов.

 

(1,1), (1,2), (1,3) (2,1), (2,2), (2,3) (3,1), (3,2), (3,3)	(1,1), (1,2), (1,3)      (2,2), (2,3)                (3,3)	с возвращением
(1,2), (1,3) (2,1), (2,3) (3,1), (3,2)	(1,2), (1,3)             (2,3)	без возвращения
упорядоченные	неупорядоченные	выборки

 

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

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) + = .