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

Работы уже с готовыми рамками. Написана для изучения комбинаторных задач. Сдана 12 января 2015 года. ...

1.1. Основные комбинаторные задачи……………………………………….5
1.2. Типы комбинаторных задач……………………………………………...6

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

Изм.Лист№ докум.ПодписьДатаЛист8К 30.00.002. Основные формулы комбинаторики.Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них.1.Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановокPn = n!, где n! = 1 * 2 * 3 ... n.Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.2.Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещенийAmn = n (n - 1)(n - 2) ... (n - m + 1).3.Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетанийС mn = n! / (m! (n - m)!).Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенствомAmn = PmC mn.З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениямиPn (n1, n2, ...) = n! / (n1! n2! ... ), где n1 + n2 + ... = n.Изм.Лист№ докум.ПодписьДатаЛист9К 30.00.003. Правила комбинаторики.3.1. Правило суммы.Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.Суммой А + В двух событий А и В называют событие, состоящее в появлении события А, или события В, или обоих этих событий. Например, если из орудия произведены два выстрела и А — попадание при первом выстреле, В — попадание при втором выстреле, то А + В — попадание при первом выстреле, или при втором, или в обоих выстрелах.В частности, если два события А и B — несовместные, то А + В — событие, состоящее в появлении одного из этих событий, безразлично какого.Суммой нескольких событий называют событие, которое состоит в появлении хотя бы одного из этих событий. Например, событие А + В + С состоит в появлении одного из следующих событий: А, В, С, А и В, А и С, В и С, А и В и С.Пусть события A и В — несовместные, причем вероятности этих событий известны. Как найти вероятность того, что наступит либо событие A, либо событие В? Ответ на этот вопрос дает теорема сложения.Теорема. Вероятность появления одного из двух несовместных событий, безразлично какого, равна сумме вероятностей этих событий:Р (А + В) = Р (А) + Р (В).Доказательство:Введем обозначения: n — общее число возможных элементарных исходов испытания; m1 — число исходов, благоприятствующих событию A; m2— число исходов, благоприятствующих событию В.Число элементарных исходов, благоприятствующих наступлению либо события А, либо события В, равно m1 + m2. Следовательно,Р (A + В) = (m1 + m2) / n = m1 / n + m2 / n. Приняв во внимание, что m1 / n = Р (А) и m2 / n = Р (В), окончательно получим Р (А + В) = Р (А) + Р (В).Следствие. Вероятность появления одного из нескольких попарно несовместных событий, безразлично какого, равна сумме вероятностей этих событий:Р (A1 + A2 + ... + An) = Р (A1) + Р (A2) + ... + Р (An).Доказательство:Рассмотрим три события: А, В и С. Так как рассматриваемые события попарно несовместны, то появление одного из трех событий, А, В и С, равносильно наступлению одного из двух событий, A + В и С, поэтому в силу указанной теоремыР ( А + В + С) = Р [(А + В) + С] = Р (А + В) + Р (С) = Р (А) + Р (В) + Р(С). Для произвольного числа попарно несовместных событий доказательство проводится методом математической индукции.Полная группа событий.Теорема. Сумма вероятностей событий А1 , А2 , ..., Аn , образующих полную группу, равна единице:Р (A1) + Р (А2) + ... + Р (Аn) = 1.Доказательство:Так как появление одного из событий полной группы достоверно, а вероятность достоверного события равна единице, тоР (A1 + A2 + ... + An) = 1.     (*)Любые два события полной группы несовместны, поэтому можно применить теорему сложения:Р (А1 + А2 + ... + Аn) = Р (A1) + Р (A2) + ... + Р (Аn).(**)Сравнивая (*) и (**), получим Р(А1)+Р(А2)+...+Р(Аn)=1.Изм.Лист№ докум.ПодписьДатаЛист10К 30.00.00Противоположные события.Противоположными называют два единственно возможных события, образующих полную группу. Если одно из двух противоположных событий обозначено через A, то другое принято обозначать Теорема. Сумма вероятностей противоположных событий равна единице: . Доказательство. Базируется на том, что противоположные события образуют полную группу, а сумма вероятностей событий, образующих полную группу, равна единице (см. Теорему о полной группе событий).З а м е ч а н и е 1. Если вероятность одного из двух противоположных событий обозначена через р, то вероятность другого события обозначают через q. Таким образом, в силу предыдущей теоремы p + q = lЗ а м е ч а н и е 2. При решении задач на отыскание вероятности события А часто выгодно сначала вычислить вероятность противоположного события, а затем найти искомую вероятность по формуле .Изм.Лист№ докум.ПодписьДатаЛист11К 30.00.003.2. Правило произведения.Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана mn способами.Произведение событий.Произведением двух событий А и В называют событие АВ, состоящее в совместном появлении (совмещении) этих событий. Например, если А — деталь годная, В — деталь окрашенная, то АВ — деталь годна и окрашена.Произведением нескольких событий называют событие, состоящее в совместном появлении всех этих событий. Например, если А, В, С — появление «герба» соответственно в первом, втором и третьем бросаниях монеты, то АВС — выпадение «герба» во всех трех испытаниях. Условная вероятность. Во введении случайное событие определено как событие, которое при осуществлении совокупности условий S может произойти или не произойти. Если при вычислении вероятности события никаких других ограничений, кроме условий S, не налагается, то такую вероятность называют безусловной; если же налагаются и другие дополнительные условия, то вероятность события называют условной. Например, часто вычисляют вероятность события В при дополнительном условии, что произошло событие А. Заметим, что и безусловная вероятность, строго говоря, является условной, поскольку предполагается осуществление условий S. Условной вероятностью РA (В) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.Исходя из классического определения вероятности, формулу РA (В) = Р (АВ) / Р (А) (Р (А) > 0 можно доказать. Это обстоятельство и служит основанием для следующего общего (применимого не только для классической вероятности) определения.Условная вероятность события В при условии, что событие А уже наступило, по определению, равнаРA (В) = Р (АВ) / Р (А)    (Р(A)>0).Рассмотрим два события: А и В; пусть вероятности Р (А) и РA (В) известны. Как найти вероятность совмещения этих событий, т. е. вероятность того, что появится и событие А и событие В? Ответ на этот вопрос дает теорема умножения.Изм.Лист№ докум.ПодписьДатаЛист12К 30.00.00Теорема. Вероятность совместного появления двух событий равна произведению вероятности одного из них на условную вероятность другого, вычисленную в предположении, что первое событие уже наступило:Р (АВ) = Р (А) РA (В).     (*)Доказательство:По определению условной вероятности,РA (B) = Р (АВ) / Р (A).ОтсюдаР (АВ) = Р (А) РA (В).З а м е ч ан и е. Применив формулу (*) к событию ВА, получимР (ВА) = Р (В) РB (А),или, поскольку событие ВА не отличается от события АВ,Р(АВ) = Р (В) РB (А).     (**)Сравнивая формулы (*) и (**), заключаем о справедливости равенстваР (А) РA (В) = Р (В) РB (А).     (***)С л е д с т в и е. Вероятность совместного появления нескольких событий равна произведению вероятности одного из них на условные вероятности всех остальных, причем вероятность каждого последующего события вычисляется в предположении, что все предыдущие события уже появились:где является вероятностью события An, вычисленной в предположении, что события А1,А2,..., Аn — 1 наступили. В частности, для трех событий Р (AВС) = Р (А) РA (В) РAB (С).Заметим, что порядок, в котором расположены события, может быть выбран любым, т. е. безразлично какое событие считать первым, вторым и т. д.Пусть вероятность события В не зависит от появления события А.Изм.Лист№ докум.ПодписьДатаЛист13К 30.00.00Событие В называют независимым от события А, если появление события А не изменяет вероятности события В, т. е. если условная вероятность события В равна его безусловной вероятности:РA (В) = Р (В). (*)Подставив (*) в соотношение (***) предыдущего параграфа, получимР (A) Р (В) = Р (В) РB (A).ОтсюдаРB (A) = Р (A),т. е. условная вероятность события A в предположении что наступило событие В, равна его безусловной вероятности. Другими словами, событие A не зависит от события В.Итак, если событие В не зависит от события A, то событие A не зависит от события В; это означает, что   свойство независимости событий зваимно.Для независимых событий теорема умноженияР (АВ) = Р (А) РA (В) имеет видР (АВ) = Р (А) Р (В), (**)т. е. вероятность совместного появления двух независимых событий равна произведению вероятностей этих событий.Равенство (**) принимают в качестве определения независимых событий.