Комбинаторика

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n₁ элементов, а вторая - из n₂ элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n₂. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n₂. Так как в первой группе всего n₁ элемент, всего возможных вариантов будет n₁*n₂. 
 
Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? 
 
Решение: n₁=6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n₂=7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n3=4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6). 
 
Итак, N=n₁*n₂*n₃=6*7*4=168.

 
В том случае, когда все группы состоят из одинакового числа  элементов, т.е. n₁=n₂=...n_k=n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n^k.Такой способ выбора носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8? 
 
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5⁴=625.

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

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

 
 
Число размещений обозначается A_n^m и вычисляется по формуле:

 
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

Пример 5. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные? 
 
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

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

Пример 6. Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

 
Число сочетаний обозначается C_n^m 
и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся? 
 
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

 
 
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

 
Число различных перестановок из n элементов обозначается P_n и вычисляется по формуле P_n=n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд? 
 
Решение: эта задача о числе перестановок семи разных книг. Имеется P₇=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

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

Пример. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? 
 
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. 
 
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи  для самопроверки 
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? 
 
2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? 
 
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день? 
 
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек? 
 
5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо? 
 
6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Допустим  к ним присоединился еще один мальчик Даурен. Каковы будут способы расположения в этом случае? В возможных шести случаях Даурен может стоять первым, вторым, третьим и последним:

ДАБС, ДАСБ, ДБАС, ДБСА, ДСАБ, ДСБА;  
АДБС, АДСБ, БДАС, БДСА, СДАБ, СДБА;  
АБДС, АСДБ, БАДС, БСДА, САДБ, СБДА;  
АБСД, АСБД, БАСД, БСАД, САБД, СБАД.

Всего 24 разных способов. А если еще увеличить  количество детей? Каждый раз писать и выводить общее количество трудно. Нам нужно определить число способов, а не виды способов. Нет ли других методов для определение этого число? - Есть. И в теории вероятностей нас больше интересует количество способов расположения, чем виды расположения. Раздел математики, называемый комбинаторикой, дает возможность сразу определить количество таких способов. Ознакомимся с основными понятиями комбинаторики, необходимыми для решения задач теории вероятностей. Это - перестановка, размещение и сочетания. Остановимся на каждом в отдельности.

1. Перестановка. Рассмотрим число случаев в  предыдущей задаче. Мы переставили  местами буквы А, Б, С и посчитали число всевозможных комбинаций, оно равнялось 6. А когда число мальчиков увеличилось на единицу, переставь местами буквы А, Б, С, Д, мы нашли число всевозможных комбинаций, оно равнялось 24.

ОПРЕДЕЛЕНИЕ. Перестановкой из n различных элементов называются комбинации, которые состоят из n элементов и отличаются друг от друга только порядком их расположения.

Число перестановок из n различных элементов обозначают P_n и подсчитывают по формуле:

P_n=n! (14)

здесь n! (читается "эн факториал") означает произведение всех натуральных чисел от 1 до n:

n!=1•2•3•...•n

Понятно, что один факториал равен единице, 1! = 1, вместе с этим, в математике принято считать что и ноль факториал равен единице. И так 0! = 1.

Вернемся  к примеру. Здесь n=3. Следовательно, можно найти искомое число  перестановок по формуле (1): P₃=3!=1•2•3=6. Аналогично, число перестановок из четырех букв равно: P₄=4!=1•2•3•4=24

Пример 7. Найдем значение выражения с факториалами 8!/6!•2!

Сначала преобразуем 8!=1•2•3•4•5•6•7•8=6!•7•8

Это преобразование подставим в выражение и упростим. 8!/6!•2=6!•7•8/6!•2=7•8/2=28

2. Размещения. Рассмотрим пример. Сколько двузначных  чисел (цифры не повторяются)  можно записать с помощью цифр 7, 8, 9. Это можно сделать в двух  этапах: первый этап - определение  количество подбора разрядов  десятков числа, он равен 3 (любая  из данных 3 цифр может занять  разряд десятков); второй этап - определение  количество подбора разрядов  единиц числа, он равен 2 (любая  цифра из оставшихся двух может  занять разряд единиц). По правилу  умножения из трех чисел можно  составить всего 3•2=6 различных  двузначных чисел. Действительно,  можно в этом убедиться непосредственно записывая эти числа 78, 79, 87, 89, 97, 98, При решении задачи мы расположили по два элемента из трех, причем эти комбинации отличаются либо составом (78, 98), либо порядком их расположения (78, 87).

ОПРЕДЕЛЕНИЕ. Размещением из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающихся друг от друга либо самими элементами, либо порядком их расположения.

Число размещений из n элементов по m элементов обозначают и читают так: "А из эн по эм". Чтобы найти используют формулу:

В нашем  примере n=3, а m=2. Тогда 

Рассмотрим  еще один пример. В 5 классе изучают 10 предметов. Сколькими способами  можно составить расписание, если в этот день должно быть 4 различных урока?

Чтобы найти число способов расположения 10-ти предметов по четыре предмета, воспользуемся формулой (15) нахождения числа размещений из 10 элементов  по 4 элемента:

Итак, 10 предметов по 4 предмета можно расположить 5040 различными способами.

3. Сочетания.  Пример. Нужно составить произведения  двух различных чисел из данных  трех чисел 7, 8, 9.

Учитывая  переместительное свойство умножения, имеем: 7•8=56, 7•9=63, 8•9=72. При решении  задачи мы отобрали по два элемента из трех, причем эти комбинации отличаются только составом (78, 98), а их расположения не влияют на произведение.

ОПРЕДЕЛЕНИЕ. Сочетанием из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающиеся друг от друга только составом.

Число сочетаний из n элементов по m элементов обозначают и читают так: "це из эн по эм". Чтобы найти используют формулу:

В нашем  примере n=3, а m=2. Тогда 

Рассмотрим  еще пример. В классе 25 учеников, из них 12 мальчиков. а) Нужно составить  дежурство по два человека, причем пары должны состоят либо из мальчиков, либо из девочек. б) Сколько можно  создать групп для дежурства, из двух мальчиков и одной девочки?

Решение. а) При решении этой задачи воспользуемся  правилом сложения и формулой сочетания. Сначала посчитаем сколько пар можно создать из мальчиков (m₁) и из девочек (m₂), после найдем их сумму (m=m₁+m₂).

Чтобы определить сколько пар можно создать из 12 мальчиков воспользуемся формулой для подсчета числа сочетаний из 12 элементов по 2 элемента

Из девочек  можно создать 78 различных пар. Тогда  по два мальчика и по две девочки  всего можно создать m=66+78=144 различных  пар.

б) При  решении этой задачи воспользуемся  правилом умножения и формулой сочетания. В группе два мальчика и одна девочка. Сначала посчитаем сколькими  способами можно выбрать из 12 мальчиков по два мальчика (m₁) и из 13 девочек одну девочку (m₂), затем перемножим полученные результаты (m=m₁•m₂).  
Из 12 мальчиков 2 мальчика можно выбрать 66 различными способами. А из 13 девочек 1 девочку можно выбрать следующим образом:

Тогда группу из двух мальчиков и из одной  девочки можно создать m=66•13=856 различными способами.

Пусть в урне содержится 6 одинаковых, тщательно  перемешанных шаров, причем 2 из них  красные, 3-синие и 1-белый. Очевидно, возможность вынуть наудачу из урны цветной (т.е. красный или синий) шар  больше, чем возможность извлечь  белый шар. Можно ли охарактеризовать эту возможность числом? Оказывается, можно. Это число и называют вероятностью события (появление цветного шара). Таким образом, вероятность есть число, характеризующее степень  возможности появления события.

ОПРЕДЕЛЕНИЕ (классическое определение вероятности). Вероятностью события А называют отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных исходов, образующих полную группу.

Итак, вероятность  события А определяется формулой:

где m – число элементарных исходов, благоприятствующих А; n – число всех возможных элементарных исходов испытания.

Пример 1 Найти вероятность события А={появление не менее пяти очков при одном бросании игральной кости}.

Используем  формулу (1). В нашем случае число  возможных исходов n=6, а число, благоприятствующих этому событию исходов, m=2. То есть P(A)=2/6=1/3. Итак, вероятность появления  не менее пяти очков при одном  бросании игральной кости равна 0.33 или 1/3

Из  определения вероятности  вытекают следующие  ее свойства:

Свойство 1. Вероятность достоверного события  равна единице.

Действительно, если событие достоверно, то каждый элементарный исход испытания благоприятствует событию. В этом случае m=n, следовательно, P(A)=m/n=n/n=1

Свойство 2. Вероятность невозможного события  равна нулю.

В этом случае m=0, следовательно, P(A)=m/n=0/n=0

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

Действительно, случайному событию благоприятствует лишь часть из общего числа элементарных исходов испытания. В этом случае 0<m<n, значит 0<m/n<1, следовательно,

0<P(A)<1

Итак, вероятность  любого события удовлетворяет двойному неравенству 

0

Например, если из орудия произведены два выстрела и А – попадание при первом выстреле, В – попадание при втором выстреле, то событие А+В – попадание хотя бы при одном выстреле (или при первом выстреле, или при втором, или в обоих случаях).

Теорема 1.(теорема сложения вероятностей)

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

P(A+B)=P(A)+P(B) (3)

Доказательство: Введем обозначения: n – общее число возможных элементарных исходов испытания; m₁ – число исходов, благоприятствующих событию А; m₂ – число исходов, благоприятствующих событию В.Число элементарных исходов, благоприятствующих наступлению либо события А, либо события В, равно m₁+m₂. Следовательно, P(A+B)=(m₁+m₂)/n= . Приняв во внимание, что m₁/n=P(A) и m₂/n=P(B), окончательно получим P(A+B)=P(A)+P(B)

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

P(A₁+A₂+...+A_n)=P(A₁)+P(A₂)+...+P(A_n)

Пример 3. В урне 30 шаров: 10 красных, 5 синих  и 15 белых. Найти вероятность появления  цветного шара.

Появление цветного шара означает появление либо красного, либо синего шара. Вероятность  появления красного шара (событие  А) P(A)=10/30=1/3 Вероятность появления  синего шара (событие В) P(B)=5/30=1/6 События А и В несовместны (появление шара одного цвета исключает появление шара другого цвета), поэтому теорема сложения применима. Искомая вероятность P(A+B)=P(A)+P(B)=

Теорема 2. Сумма вероятностей событий А₁, А₂, …, А_n, образующих полную группу, равна единице:

P(A₁)+P(A₂)+...+P(A_n)=1 (4)

Доказательство: Так как появление одного из событий  полной группы достоверно, а вероятность  достоверного события равна единице, то:

P(A₁+A₂+...+A_n)=1 (5)

любые два события полной группы несовместны, поэтому можно применить теорему  сложения:

P(A₁+A₂+...+A_n)=P(A₁)+P(A₂)+...+P(A_n) (6)

Сравнивая (4) и (5), получим P(A₁+A₂+...+A_n)=1

ОПРЕДЕЛЕНИЕ. Два несовместных события, образующие полную группу называются противоположными событиями. Если одно из двух противоположных  событий обозначено через А, то другое принято обозначать .

Пусть в результате испытания возможны только два единственно возможных  события. Например, а) при одном бросании монеты - "выпал герб" и "выпала цифра"; б) при одном бросании игральной  кости - "выпало 6 очков" и "не выпало 6 очков"; с) при одном выстреле - "попадание в мишень" и "не попадание в мишень". В каждой паре событий появление одного исключает  появление второго. Действительно, если монета выпала гербом, то уже не может выпасть цифрой; игральная  кость не может одновременно выпасть  сразу двумя гранями; стрелок  попадая в мишень, исключает промах. Итак, данных примерах противоположными событиями являются: а) A={выпал герб}, ={выпала цифра}; б) B={выпало 6 очков}, ={не выпало 6 очков}; с) C={попадание в мишень}, ={не попадание в мишень}.

Теорема 3. Сумма вероятностей противоположных  событий равна единице:

P(A)+P(

ОПРЕДЕЛЕНИЕ. Произведением двух событий А и В называют событие АВ, состоящее в совместном появлении (совмещении) этих событий. Например, если А – деталь годная, В – деталь окрашенная, то АВ – деталь годна и окрашена.

ОПРЕДЕЛЕНИЕ. Условной вероятностью Р_А(В) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.

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

Следствие 2. Эту теорему можно обобщить на любое конечное число зависимых  событий A₁,A₂,...,A_k

P(A₁,A₂,...,A_k)=P(A₁)•P_A1(A₂)•P_A1A2(A₃)...P_A1A2...Ak-1(A)

Событие В называют независимым от события А, если появление события А не изменяет вероятности события В, т.е. если условная вероятность события В равна его безусловной вероятности P_AB=P(B)

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

P(AB)=P(A)•P(B) (9)

Пример 4. Найти вероятность совместного поражения цели двумя орудиями, если вероятность поражения цели первым орудием (событие А) равна 0,8, а вторым (событие В)-0,7.

Событие А и В независимые, поэтому, по теореме умножения, искомая вероятность P(AB)=P(A)•P(B)=0.7•0.8=0.56

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

P(A₁,A₂,...,A_n)=P(A₁)•P(A₂)•...•P(A_n)

Теорема 5. Вероятность появления хотя бы одного из событий A₁,A₂,...,A_n, независимых в совокупности, равна разности между единицей и произведением вероятностей противоположных событий ₁, ₂,..., _n

P(A)=1-q₁q₂...q_n (10)

Доказательство: Обозначим через А событие, состоящее в появлении хотя бы одного из событий A₁,A₂,...,A_n. Событие A и ₁,..., _n (ни одно из событий не наступило) противоположны, следовательно, сумма их вероятностей равна единице:

P(A)+P(

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

P(A)=1-P(

или

P(A)=1-q₁q₂...q_n

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

P(A+B)=P(A)+P(B)-P(AB) (11)

Доказательство: Поскольку события А и В, по условию, совместны, то событие А+В наступит, если наступит одно из следующих трех совместных событий: B, A или AB. По теореме сложения вероятностей несовместных событий:

P(A+B)=P(

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

P(A)=P(A )+P(AB)

Отсюда P(A )=P(A)-P(AB)  
Аналогично имеем P(B)=P( B)+P(AB)  
Отсюда P( B)=P(B)-P(AB)

Подставив все в (*)б, окончательно получим P(A+B)=P(A)+P(B)-P(AB)