Комбинаторикой называется раздел математики, который изучает задачи выбора и распределения элементов множеств. Приёмы и методы комбинаторики используются для решения различного рода задач, связанных с комбинациями, в том числе относящихся к теории вероятностей. Они дают возможность точно подсчитывать вероятности событий в самых сложных случаях. Существуют несколько наиболее употребительных понятий и формул, используемых в теории вероятностей.

Определение 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.

236
проверенных автора готовы помочь в написании работы любой сложности
Мы помогли уже 4 372 ученикам и студентам сдать работы от решения задач до дипломных на отлично! Узнай стоимость своей работы за 15 минут!