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

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

Рассмотрим некоторое множество Х, состоящее из n элементов . Будем выбирать из этого множества различные упорядоченные подмножества из k элементов.

Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор элементов множества Х.

Если выбор элементов множества  из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле (размещения с повторениями).

Если же выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается и определяется равенством
 
(размещения без повторений).

Пример. Пусть даны шесть цифр: 1; 2; 3; 4; 5; 6. Определить сколько трехзначных чисел можно составить из этих цифр.

Решение. Если цифры могут повторяться, то количество трехзначных чисел будет . Если цифры не повторяются, то .

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

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

Частный случай размещения при n=k называется перестановкой из n элементов. Число всех перестановок из n элементов равно
 .

Пример. 30 книг стоит на книжной полке, из них 27 различных книг и одного автора три книги. Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора стояли рядом?

Решение. Будем считать три книги одного автора за одну книгу, тогда число перестановок будет . А три книги можно переставлять между собой способами, тогда по правилу произведения имеем, что искомое число способов равно: * =3!*28!

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

Справедливы равенства: , , .

Пример. В группе из 27 студентов нужно выбрать трех дежурных. Сколькими способами можно это сделать?

Решение. Так как порядок студентов не важен, используем формулу для числа сочетаний: .

Еще наглядно с картинками и примерами про основные формулы комбинаторики (размещения, перестановки, сочетания) и их применение для решения задач здесь: Формулы комбинаторики.

При решении задач комбинаторики  используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.

Пример. Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка?

Решение. Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4*5*3=60 нарядов (комбинаций).

 

1.2. Классическое  определение вероятности

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

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

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

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

Рассмотрим полную группу равновозможных несовместных случайных событий. Такие  события будем называть исходами. Исход называется благоприятствующим появлению события А, если появление этого события влечет за собой появление события А.

Пример. В урне находится 8 пронумерованных шаров (на каждом шаре поставлено по одной цифре от 1 до 8). Шары с цифрами 1, 2, 3 красные, остальные – черные. Появление шара с цифрой 1 (или цифрой 2 или цифрой 3) есть событие, благоприятствующее появлению красного шара. Появление шара с цифрой 4 (или цифрой 5, 6, 7, 8) есть событие, благоприятствующее появлению черного шара.

Вероятностью  события A называют отношение числа m благоприятствующих этому событию исходов к общему числу n всех равновозможных несовместных элементарных исходов, образующих полную группу


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

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

Пример. В урне 10 пронумерованных шаров с номерами от 1 до 10. Вынули один шар. Какова вероятность того, что номер вынутого шара не превосходит 10?

Решение. Пусть событие А = (Номер вынутого шара не превосходит 10). Число случаев благоприятствующих появлению события А равно числу всех возможных случаев m=n=10. Следовательно, Р(А)=1. Событие А достоверное.

Пример. В урне 10 шаров: 6 белых и 4 черных. Вынули два шара. Какова вероятность, что оба шара белые?

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

Пример. В урне 15 шаров: 5 белых и 10 черных. Какова вероятность вынуть из урны синий шар?

Решение. Так как синих шаров в урне нет, то m=0, n=15. Следовательно, искомая вероятность р=0. Событие, заключающееся в вынимании синего шара, невозможное.

Пример. Из колоды в 36 карт вынимается одна карта. Какова вероятность появления карты червовой масти?

Решение. Количество элементарных исходов (количество карт) n=36. Событие А = (Появление карты червовой масти). Число случаев, благоприятствующих появлению события А, m=9. Следовательно,
 .

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

Решение. Общее число возможных исходов равно числу способов, которыми можно отобрать 7 человек из 10, т.е. 
 .

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

Искомая вероятность 
 .

 

1.3. Геометрическое  определение вероятности

Пусть случайное испытание можно  представить себе как бросание точки  наудачу в некоторую геометрическую область G (на прямой, плоскости или  пространстве). Элементарные исходы –  это отдельные точки G, любое событие  – это подмножество этой области, пространства элементарных исходов G. Можно считать, что все точки G «равноправны» и тогда вероятность  попадания точки в некоторое  подмножество пропорционально его  мере (длине, площади, объему) и не зависит  от его расположения и формы.

Геометрическая  вероятность события А определяется отношением: 
 , 
где m(G), m(A) – геометрические меры (длины, площади или объемы) всего пространства элементарных исходов и события А.

Пример. На плоскость, разграфленную параллельными полосами шириной 2d, расстояние между осевыми линиями которых равно 2D, наудачу брошен круг радиуса r ( ). Найти вероятность того, что круг пересечет некоторую полосу.

Решение. В качестве элементарного исхода этого испытания будем считать расстояние x от центра круга до осевой линии ближайшей к кругу полосы. Тогда все пространство элементарных исходов – это отрезок . Пересечение круга с полосой произойдет в том случае, если его центр попадет в полосу, т.е. , или будет находится от края полосы на расстоянии меньшем чем радиус, т.е. .

Для искомой вероятности  получаем: .

 

1.4. Сложение  и умножение вероятностей

Событие А называется частным случаем события В, если при наступлении А наступает и В. То, что А является частным случаем В, записываем .

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

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

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

Заметим, что сформулированная теорема  справедлива для любого числа  несовместных событий:

.

Если случайные события  образуют полную группу несовместных событий, то имеет место равенство

.

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

Теорема о сложении вероятностей 2. Вероятность суммы совместных событий вычисляется по формуле

.

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

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

.

Вероятность произведения зависимых  событий вычисляется по формуле  условной вероятности (см. следующий  раздел).

Пример. В первом ящике 1 белый и 5 черных шаров, во втором 8 белых и 4 черных шара. Из каждого ящика вынули по шару. Найти вероятность того, что один из вынутых шаров белый, а другой – черный.

Решение. Обозначим события: А – вынули белый шар из первого ящика, 
 ;

- вынули черный шар из первого  ящика, 
 ;

В – белый шар из второго ящика, 
 ;

- черный шар из второго ящика,  
 .

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

Пример. Вероятность попадания в цель у первого стрелка 0,8, у второго – 0,9. Стрелки делают по выстрелу. Найти вероятность: а) двойного попадания; б) двойного промаха, в) хотя бы одного попадания; г) одного попадания.

Решение.

Пусть А – попадание первого стрелка, ;

В – попадание второго стрелка, .

Тогда - промах первого, ;

- промах второго,  .

Найдем нужные вероятности.

а) АВ – двойное попадание,

б) – двойной промах, .

в) А+В – хотя бы одно попадание,

.

г) – одно попадание,

.

Пример. Студент разыскивает нужную ему формулу в трех справочниках. Вероятности того, что формула содержится в первом, втором и третьем справочниках равны 0,6; 0,7 и 0,8. Найти вероятности того, что формула содержится 1) только в одном справочнике; 2) только в двух справочниках; 3) во всех трех справочниках.

Решение.

А – формула содержится в первом справочнике;

В – формула содержится во втором справочнике;

С – формула содержится в третьем справочнике.

Воспользуемся теоремами сложения и умножения вероятностей.

1.

2. .

3.

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

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