Элементы комбинаторики: Часть 1

Элементы комбинаторики

При решени задач по теории вероятностей часто используются элементы комбинаторики. Рассмотрим основные понятия комбинаторики.

1. Пусть имеется n различных объектов — n неповторяющихся элементов некоторого множества, которые нужно расположить в каком-то определенном порядке. Произвольный упорядоченный набор n неповторяющихся элементов множества из n различных элементов будет называться перестановкой. Число перестановок множества из n элементов равно факториалу числа n : n!=1\cdot 2\cdot 3\cdot \dots n .

2. Пусть из имеющихся n различных объектов ( n неповторяющихся элементов некоторого множества) необходимо выбрать m неповторяющихся элементов и упорядочить их. Упорядоченный набор из m различных элементов, выбранных из n различных элементов, называется размещением. Размещения отличаются друг от друга, как составом элементов, так и порядком их следования. Число размещений равно \frac{n!}{(n-m)!} .

3. Пусть из имеющихся n различных объектов ( n неповторяющихся элементов некоторого множества) необходимо выбрать m неповторяющихся элементов без учета порядка. Неупорядоченный набор из m различных элементов, выбранных из n различных элементов, называется сочетанием. Сочетания отличаются друг от друга только составом элементов, порядок их следования не важен. Числом сочетаний равно C_n^m=\frac{n!}{m!(n-m)!} .

Отметим, что по определению считают 0!=1 . Это позволяет использовать полученные выше формулы при m=n . Рассмотрим примеры применения формул комбинаторики для решения задач по теории вероятностей.

Схема Бернулли

Пусть мы проводим серию одинаковых случайных экспериментов, в каждом из которых возможны два различных случайных исхода (например несколько раз бросаем монету). Будем считать, что при каждом повторении эксперимента вероятности наступления каждого из исходов фиксированы и не зависят от номера эксперимента, а результаты всех экспериментов попарно независимы. Один из двух возможных элементарных исходов этого эксперимента будем считать успехом, а другой — неудачей. Пусть вероятность успеха равна p , а вероятность неудачи равна q=1-p .

Найдем вероятность того, что в серии из n испытаний произойдет ровно m успехов. Вероятность наступления одного конкретного исхода серии из n испытаний, в которой произойдет ровно m успехов, равна p^m \cdot q^{n-m} . Все такие исходы являются несовместными, равновероятными и будут отличаться друг от друга выбором номеров испытаний, в которых произошли успехи. Количество вариантов такого выбора будет равно числу сочетаний C_n^m . Поэтому вероятность того, что в серии из n испытаний произойдет ровно m успехов, определяется формулой P=C_n^m\cdot p^m \cdot q^{n-m}. Эта формула называется формулой Бернулли, а сама схема, в которой много раз проводится один и тот же эксперимент с двумя различными элементарными исходами, будет называться схемой Бернулли.