Комбинаторикой называется раздел математики, который изучает задачи выбора и распределения элементов множеств. Приёмы и методы комбинаторики используются для решения различного рода задач, связанных с комбинациями, в том числе относящихся к теории вероятностей. Они дают возможность точно подсчитывать вероятности событий в самых сложных случаях. Существуют несколько наиболее употребительных понятий и формул, используемых в теории вероятностей.
Определение 1
Допустим, есть множество из n компонентов $a_1, a_2, … a_m$. Тогда размещениями из m элементов по k называют такие комбинации, которые будучи составлены из количества k компонентов взятых из общего количества m, различаются и составом компонентов, и порядком их расстановки. Вычислить суммарное количество всех допустимых размещений можно по формуле:
$A_m^k=m(m-1)(m-2)…(m-(k-1))$
Запись можно сделать более компактной, применяя понятие факториала $m!= 1\cdot2\cdot3\cdot … \cdot m$ . Теперь, если домножить и разделить выражение на (m-k)! — это позволит упростить формулу. В числителе получим m! и запись примет следующий вид:
$ A_m^k =\frac{m!}{(m-k)!}$
Определение 2
Предположим, существует m отличных друг от друга компонентов. Расположив их в определённом порядке можно составить комбинацию, которая называется перестановкой. Перестановки создаются из одних и тех же компонентов, количество компонентов постоянно, меняется только порядок элементов. Количество всех вариантов перестановок рассчитывается согласно формуле:
$P_m=m!$
Дополнительно можно отметить связь между перестановками и размещениями. Так перестановка — это такое размещение, которое выполняется из максимального числа элементов входящих в используемое множество, то есть:
$P_m= A_m^m=m(m-1)(m-2)…(m-(m-1))=m!$
Если возьмём одинаковое количество одних и тех же элементов и расставим их в одном и том же порядке, то получим одинаковые перестановки. Если элементы стоят на разных местах, то такие перестановки считаются различными.
Определение 3
Пусть существует множество отличающихся компонентов m. Если из данного множества сформировать подмножества, состоящие из k компонентов, причём k<m, то каждое такое подмножество будем называть сочетанием и обозначать как $С_m^k$
Два сочетания называются различными, если состав их отличается количеством, либо в какое-либо из сочетаний входит хоть один компонент отсутствующий в другом.
Теорема 1
Чтобы вычислить количество сочетаний, которое можно составить из k компонентов взятых во множестве из m компонентов, подходит формула:
$С_m^k= \frac{m!}{k!(m-k)!} $
Доказательство
Используем метод математической индукции. Количество сочетаний по 1 компоненту из m, очевидно будет иметь значение m, а именно: $С_m^1= m$. Проверяя подстановкой модем убедиться, что, приведённая в теореме, формула выполняется.
Предположим выполнение формулы происходит также вплоть до некоего конечного выражения k. Докажем, что она актуальна и для числа k+1. Тогда сочетание $С_m^k$ дополнится до k+1 количеством способов m-k. Данную процедуру допустимо осуществить в отношении всех сочетаний из $С_m^k$.
Получим, что сочетания по k+1 из m элементов можно получить в каждом сочетании ($С_m^k$) m-k способами. Среди таких сочетаний появятся в том числе и одинаковые. Учитывая повторяющиеся сочетания, можем записать:
$С_m^{k+1}=C_m^k \frac {m-k}{k+1}=\frac {m!(m-k)}{k!(m-k)!(k+1)}=\frac{m!}{(k+1)!(m-k-1)!} $
Правило 1
А — элемент, который допустимо выбрать из множества количеством способов k. B — элемент, который допустимо выбрать из множества количеством способов m. Тогда возможность выбора какого-либо одного из данных объектов доступна k+m способами. Данное правило называется правилом суммы.
Правило 2
А — элемент, который допустимо выбрать из множества количеством способов k. B — элемент, который допустимо выбрать из множества количеством способов m. Тогда выбрать два объекта возможно $k\cdot m$ количеством способов. Данное правило называется правилом суммы.
Формула Стирлинга
При больших значениях m для вычисления факториала допустимо применять упрощённое выражение для вычисления факториала
$n!\approx {(\frac{m}{e})}^m \sqrt{2\pi m}$
Рассмотрим применение формул комбинаторики для теории вероятностей.
Пример
Имеется емкость, в которую сложены шары. Они выполнены из одного и того же материала, обладают идентичными размерами. На каждый из шаров нанесено число. Всего использованы числа от единицы до сотни. Из емкости вынимают 4 шара, какова вероятность события заключающегося в том, что один из вытащенных из ёмкости шаров будет с номером 100.
Элементарный результат эксперимента по вытаскиванию шаров заключается в получении четырёх из них, пронумерованных определёнными числами. Такие 4 шара будут в свою очередь являться подмножеством множества, состоящего из сотни. Тогда в соответствии с формулами комбинаторики мы можем установить количество вариантов формирования таких подмножеств. Они будут представлять из себя сочетания, а их количество вычисляется как $С_100^4$. При этом появление каждого такого набора шаров имеет равную вероятность, поэтом можем записать вероятность появления одного случайного набора как $\frac{1}{С_100^4}$.
Осталось определить сколько именно элементарных результатов будет соответствовать событию А — появлению числа 100. Если событие А сбылось, то нам известно, что шар 100 вынут из мешка, другие же три шара из оставшихся 99 можно достать $С_99^3$ способами. Мы уже знаем вероятность каждого элементарного результата. Событию А удовлетворяют $С_99^3$ элементарных результата, а значит вероятность можно вычислить перемножив $\frac{1}{С_100^4}$ на количество результатов:
$P(A)=\frac{ С_99^3}{С_100^4}= \frac{ 99! 4! 96!}{3! 96! 100!}= \frac{1}{25}=0,04 $
Таким образом, согласно вычислениям получаем, что вероятность вытянуть шар с номером 100 при доставании четырёх произвольных шаров из одной и той же емкости, составляет Р(А)=0,04.
Статьи по теме
Поможем выполнить
любую работу
