20. Основные формулы комбинаторики и их применение на практике.

Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них. Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Pn = n!, где n! = 1 * 2 * 3 ... n. Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1. Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений Amn = n (n - 1)(n - 2) ... (n - m + 1). Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний С mn = n! / (m! (n - m)!). примеры перестановок, размещений, сочетаний Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством Amn = PmC mn. З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями Pn (n1, n2, ...) = n! / (n1! n2! ... ), где n1 + n2 + ... = n.

Основное правило комбинаторики. Пусть имеется  групп элементов по  различных элементов в каждой . Из каждой группы отбирается по одному элементу. Тогда, общее число способов , которыми можно произвести такой выбор равняется: . (1.4) Формула для числа размещений без повторений. Из группы, содержащей  различных элементов отбираются  элементов и размещаются в порядке их появления. Получающиеся таким образом комбинации называются размещениями из  элементов по  элементов, а полное число таких выборок определяется формулой:  (1.5) Формула для числа перестановок. Пусть имеется  различных элементов, из которых формируются выборки, отличающиеся порядком элементов. Получающиеся таким образом комбинации называются перестановками из  элементов, а полное число таких выборок определяется формулой:  (1.6) Формула для числа сочетаний без повторений. Из группы, содержащей  различных элементов отбираются  различных элементов без учета порядка элементов. Получающиеся таким образом комбинации называются сочетаниями из  элементов по  элементов, а полное число таких выборок определяется формулой:  (1.7) Формула для числа размещений с повторениями. Из группы, содержащей  различных элементов отбираются  элементов и размещаются в порядке их появления, причем каждый последующий элемент выбирается из полной группы. Получающиеся таким образом комбинации называются размещениями с повторениями, а полное число таких выборок определяется формулой:  (1.8) Пример 2.В корзине находятся четыре белых и пять черных шаров. Наудачу вынимаются три шара. Найти вероятность того, что из них ровно два белых и один черный. Решение. Общее число элементарных исходов  равно числу способов, которыми можно выбрать из девяти имеющихся шаров по три различных шара, т.е. . Из этих трех шаров, два белых, из четырех имеющихся, можно получить  способами. При этом для каждой выбранной комбинации из двух белых шаров, оставшийся один черный шар можно выбрать, из пяти имеющихся черных,  способами. Следовательно,  и . Пример 3.Числа 1,2,…,9 записываются в случайном порядке. Какова вероятность, что числа 1 и 2 будут рядом в порядке возрастания. Решение. Общее число исходов  равно числу перестановок из 9 элементов, т.е.  Число 1 в этой последовательности из 9 чисел может занимать 8 различных позиций (с 1-ой по 8-ую), при этом число 2 должно занимать соседнюю позицию. При каждом фиксированном положении чисел 1 и 2, оставшиеся 7 позиций могут быть заняты оставшимися 7 числами очевидно  способами (число перестановок из 7 элементов). Следовательно, искомая вероятность: . Пример 4. Наудачу взятый телефонный номер состоит из 5 цифр. Какова вероятность, что в нем все цифры различные? Решение. Так как на каждом из пяти мест в пятизначном номере может стоять любая из цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, то всех различных пятизначных номеров будет:  Номера, у которых все цифры различные, - это размещения из 10 элементов по 5, то есть . Следовательно: .