Характеристика основных правил и соединений в комбинаторике

Условная вероятность события В при условии, что событие А уже наступило, по определению, равна

РA (В) = Р (АВ) / Р (А)    (Р(A)>0).

Рассмотрим два события: А и В; пусть вероятности Р (А) и РA (В) известны. Как найти вероятность совмещения этих событий, т. е. вероятность того, что появится и событие А и событие В? Ответ на этот вопрос дает теорема умножения.

Теорема. Вероятность совместного появления двух событий равна произведению вероятности одного из них на условную вероятность другого, вычисленную в предположении, что первое событие уже наступило:

Р (АВ) = Р (А) РA (В).     (*)

Доказательство:

По определению условной вероятности,

РA (B) = Р (АВ) / Р (A).

Отсюда

Р (АВ) = Р (А) РA (В).

З а м е ч ан и е. Применив формулу (*) к событию ВА, получим

Р (ВА) = Р (В) РB (А),

или, поскольку событие ВА не отличается от события АВ,

Р(АВ) = Р (В) РB (А).     (**)

Сравнивая формулы (*) и (**), заключаем о справедливости равенства

Р (А) РA (В) = Р (В) РB (А).     (***)

С л е д с т в и е. Вероятность совместного появления нескольких событий равна произведению вероятности одного из них на условные вероятности всех остальных, причем вероятность каждого последующего события вычисляется в предположении, что все предыдущие события уже появились:

где

является вероятностью события An, вычисленной в предположении, что события А1,А2,..., Аn — 1 наступили. В частности, для трех событий

Р (AВС) = Р (А) РA (В) РAB (С).

Заметим, что порядок, в котором расположены события, может быть выбран любым, т. е. безразлично какое событие считать первым, вторым и т. д.

Пусть вероятность события В не зависит от появления события А.

Событие В называют независимым от события А, если появление события А не изменяет вероятности события В, т. е. если условная вероятность события В равна его безусловной вероятности:

РA (В) = Р (В). (*)

Подставив (*) в соотношение (***) предыдущего параграфа, получим

Р (A) Р (В) = Р (В) РB (A).

Отсюда

РB (A) = Р (A),

т. е. условная вероятность события A в предположении что наступило событие В, равна его безусловной вероятности. Другими словами, событие A не зависит от события В.

Итак, если событие В не зависит от события A, то событие A не зависит от события В; это означает, что   с в о й с т в о   н е з а в и с и м о с т и   с о б ы т и й   в з а и м н о.

Для независимых событий теорема умножения Р (АВ) = Р (А) РA (В) имеет вид

Р (АВ) = Р (А) Р (В), (**)

т. е. вероятность совместного появления двух независимых событий равна произведению вероятностей этих событий.

Равенство (**) принимают в качестве определения независимых событий.

Два события называют независимыми, если вероятность их совмещения равна произведению вероятностей этих событий; в противном случае события называют зависимыми.

На практике о независимости событий заключают по смыслу задачи. Например, вероятности поражения цели каждым из двух орудий не зависят от того, поразило ли цель другое орудие, поэтому события «первое орудие поразило цель» и «второе орудие поразило цель» независимы.

З а м е ч а н и е 1. Если события А и В независимы, то независимы также события

Действительно,

Следовательно,

Отсюда

т. е. события А и В независимы. 
Независимость событий

является следствием доказанного утверждения.

Несколько событий называют попарно независимыми, если каждые два из них независимы. Например, события А, В, С попарно независимы, если независимы события А и В, А и С, В и С.

Для того чтобы обобщить теорему умножения на несколько событий, введем понятие независимости событий в совокупности.

Несколько событий называют независимыми в совокупности (или просто независимыми), если независимы каждые два из них и независимы каждое событие и все возможные произведения остальных. Например, если события A1, A2, А3, независимы в совокупности, то независимы события A1 и А2, А1 и А3, А2 и A3; А1 и A2A3, A2 и A1A3, А3 и A1A2. Из сказанного следует, что если события независимы в совокупности, то условная вероятность появления любого события из них, вычисленная в предположении, что наступили какие-либо другие события из числа остальных, равна его безусловной вероятности.

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

Поясним сказанное на примере. Пусть в урне имеется 4 шара, окрашенные: один — в красный цвет (А), один — в синий цвет (В), один — в черный цвет (С) и один — во все эти три цвета (АВС). Чему равна вероятность того, что извлеченный из урны шар имеет красный цвет?

Так как из четырех шаров два имеют красный цвет, то Р(А) = 2 / 4 = 1 / 2. Рассуждая аналогично, найдем Р (В) = 1 / 2, Р (С) = 1/ 2. Допустим теперь, что взятый шар имеет синий цвет, т. е. событие В уже произошло. Изменится ли вероятность того, что извлеченный шар имеет красный цвет, т. е. изменится ли вероятность события А? Из двух шаров, имеющих синий цвет, один шар имеет и красный цвет, поэтому вероятность события А по-прежнему равна 1 / 2. Другими словами, условная вероятность события А, вычисленная в предположении, что наступило событие В, равна его безусловной вероятности. Следовательно, события А и В независимы. Аналогично придем к выводу, что события A и С, В и С независимы. Итак, события А, В и С попарно независимы.

Независимы ли эти события в совокупности? Оказывается, нет. Действительно, пусть извлеченный шар имеет два цвета, например синий и черный. Чему равна вероятность того, что этот шар имеет и красный цвет? Лишь один шар окрашен во все три цвета, поэтому взятый шар имеет и красный цвет. Таким образом, допустив, что события В и С произошли, приходим к выводу, что событие А обязательно наступит. Следовательно, это событие достоверное и вероятность его равна единице. Другими словами, условная вероятность РBC (A)= 1 события А не равна его безусловной вероятности Р (А) = 1 / 2. Итак, попарно независимые события А, В, С не являются независимыми в совокупности.

Приведем теперь следствие из теоремы умножения.

С л е д с т в и е. Вероятность совместного появления нескольких событий, независимых в совокупности, равна произведению вероятностей этих событий:

Р (А1А2 ... Аn) = Р (А1) Р (А2) ... Р (Аn).

Доказательство:

Рассмотрим три события: А, В и С. Совмещение событий А, В и С равносильно совмещению событий АВ и С, поэтому

Р (AВС) = Р (АВ * С).

Так как события А, В и С независимы в совокупности, то независимы, в частности, события АВ и С, а также А и В. По теореме умножения для двух независимых событий имеем:

Р (АВ * С) = Р (АВ) Р (С) и Р (АВ) = Р (А) Р (В).

Итак, окончательно получим

Р (AВС) = Р (А) Р (В) Р (С).

Для произвольного n доказательство проводится методом математической индукции.

З а м е ч а н и е. Если события А1, А2, ..., Аn независимы в совокупности, то и противоположные им события

также независимы в совокупности.

Пусть в результате испытания могут появиться n событий, независимых в совокупности, либо некоторые из них (в частности, только одно или ни одного), причем вероятности появления каждого из событий известны. Как найти вероятность того, что наступит хотя бы одно из этих событий? Например, если в результате испытания могут появиться три события, то появление хотя бы одного из этих событий означает наступление либо одного, либо двух, либо трех событий. Ответ на поставленный вопрос дает следующая теорема.

Теорема. Вероятность появления хотя бы одного из событий А1 , А2 , ..., Аn , независимых в совокупности, равна разности между единицей и произведением вероятностей противоположных событий 

Р (A) = 1 — q1q2 ... qn.(*)

Доказательство:

Обозначим через А событие, состоящее в появлении хотя бы одного из событий А1,А2, ...,An. События А и

(ни одно из событий не наступило) противоположны, следовательно, сумма  их вероятностей равна единице:

Отсюда, пользуясь теоремой умножения, получим

или

Ч а с т н ы й   с л у ч а й. Если события А1 , А2 , ..., Аn имеют одинаковую вероятность, равную р, то вероятность появления хотя бы одного из этих событий

P (A) = l — qn. (**)

 

 

 

 

 

 

 

 

 

 

Основные формулы

Размещения,  перестановки,  и  сочетания без повторений.

Перестановки,  размещения и  сочетания считаются основными задачами (операциями) комбинаторики, которые подразделяются на два раздела: “без повторений“, когда элементы множества используются единожды и  “с повторениями“, когда элементы множества могут использоваться не однократно. Операции перестановки и  размещения  в результате их выполнения дают упорядоченных подмножеств. Множества, в которых установлен порядок следования называются кортежами. Длина кортежа – есть число элементов в нем. Сочетания дают не упорядоченное множество.

Размещения без повторения.

Пусть дано множество, содержащее n элементов.

Размещением из n элементов по m называется комбинация (кортеж), содержащая   m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования. Под размещение можно понимать любое упорядоченное множество, состоящее из n элементов, взятых из данного множества. Обозначается: , Р=n(n-1)(n-2) …(n-m+1) – число размещений без повторения

Перестановки без повторений

Перестановкой из n элементов называется любая комбинация (кортеж) из n элементов, отличающаяся от других только порядком следования. Под перестановкой понимается  любое упорядоченное множество, составленное из n  элементов данного множества.  Обозначается P(n), Pn

Р= n(n-1)(n-2) …3·2·1 – число перестановок  без повторения

Произведение n последовательных натуральных чисел называется факториалом и обозначается Р!, 5!, 10!

Сочетания без повторений

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

 – число сочетаний  без  повторения

- другая формула, которая легко  получается из предыдущей формулы.

При вычислении сочетаний легко усмотреть свойства, которое упрощает вычисления:

Сnm =Cnn-m ,     С11 =1,            Сn n=1,            Cn1=n,             Сn0 =1

Размещения,  перестановки, сочетания с  повторениями.

Примеры ситуаций, приводящих  к рассмотрению  комбинаторных задач  с повторениями:

1. У продавца цветов имеется  гвоздики: 10 – красных, 15 белых,  20 оранжевых. Необходимо составить  букеты   по 5 гвоздик каждый, в  которых  должны присутствовать  гвоздики разного цвета.  Сколькими  способами можно это сделать.

2. В компьютерах вся информация  шифруется с помощью двух знаков: 0 и 1 кортежами, в которых   8, 16, 32  знака . Естественно нули и  единицы повторяются.

3. Из десяти цифр можно составить  число, содержащее сколь угодно  знаков.

Размещения с  повторениями

Размещением из n элементов по k с повторениями –  кортежи, содержащая m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования, причем элементы в комбинациях могут повторяться от 1 до m раз.

Дано множество X={a,b,c,d}. составить все размещения  из этого четыре элементного множества по два с повторениями. Эта записывается в виде:  Ā nk.

Запишем  некоторые  кортежи длины 2. (a; a ), (a; b). (a; c),  (a; d), (b; b) …Всего таковых  кортежей    =  4·4=16. С другой стороны это есть численность декартового произведения  =т(АхА)= 4·4=16

Запишем  некоторые  кортежи длины 3. (a; a; a), (a; a; b) …. Всего таковых  кортежей    =  4·4·4=64

Общая задача. Найти число кортежей дины k, которые можно составить из элементов множества, содержащего n элементов.

 – число размещений с повторения  из n элементов по k

Перестановки с повторениями

Необходимо составить шеренгу из 20 физкультурников, среди которых 10 имеют белые майки, 4- синие, 6 – красные. Сколькими способами это можно сделать?  Если бы цвета не повторялись, то это можно сделать P(20)=20!. В виду того, что цвета будут повторяться,  то перестановок с повторениями будет меньше в 10!·41·61· раз.

Общая задача. Имеются  элементы  k видов. Причем k1 вида   n1 штук, k2 вида   n2 штук и т.д. Сколько перестановок можно сделать из этих элементов?

,  где  n = n1+n2+…=n  – сумма  всех элементов.

Сочетания с  повторениями

В магазине имеется вода жерех видов. Покупателю нужно приобрести  10 бутылок. Сколькими способами он это может сделать. По-другому, сколько различных наборов по 10 элементов можно составить из  4 наименований.

Составляемые наборы будут отличаться количеством элементов каждого наименования. Причем не обязательно, что бы присутствовали в таких наборах элементы всех наименований. Например, можно выбрать  элементы  только одного наименования или по несколько элементов каждого. В любом случае набор должен содержать установленное для данной ситуации число элементов, например 10 бутылок, как в рассматриваемой конкретной ситуации.

Ситуации такого характера приводят к  сочетаниям с повторениями, Обозначается.

Общая задача. Требуется составить k наборов (кортежей) из элементов данных n  множеств d1. d2, d3,…dn. Число элементов в каждом из множеств di  не меньше числа k.

Бином Ньютона

 Возведение двучлена a + b в степень n может быть произведено по  формуле называемой разложением  бинома Ньютона:

(a + b)n = an + C1n an - 1 b + C2n an - 2 b2 +...+Ckn an - k bk +... + Cn - 1n abn - 1 + Cnnbn

 или (после подстановки выражений Ckn с учетом формулы Ckn = Cn - kn):

,

 где Ckn — число всех возможных  сочетаний, которые можно образовать  из n элементов по k.

Пример:

(a + b)5 = a5 + C15 a4b + C25 a3b2 + C35 a2b3 + C45 ab4 + C55 b5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5

Свойства бинома Ньютона

Разложение бинома (a + b)n представляет собой многочлен, расположенный по убывающим степеням a (от n-й до нулевой) и по возрастающим степеням b (от нулевой до n-й); сумма показателей a и b в каждом члене разложения равна показателю степени бинома. Число членов разложения на единицу больше показателя степени бинома.

Коэффициенты членов разложения («биноминальные коэффициенты») возрастают до середины разложения и затем убывают; коэффициенты каждой пары членов, равноотстоящих от начала и конца разложения, равны между собой. Если n четное, то имеется один средний наибольший коэффициент; если n нечетное, то имеется два средних наибольших коэффициента.