Теория вероятности и комбинаторика

Технологический колледж

Восточно - сибирского государственного университета

 

 

 

 

 

 

 

Тема: Теория вероятности и комбинаторика.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Студент 1-го курса, группы П-10

Цыренов Булат Пурбуевич

 

 

 

 

 

 

 

г.Улан - Удэ

Содержание

 

1.Введение ……………………………………………………………………………1.стр.

2.Алгебра событий……………………………………………………………………2.стр.

3.Вероятность…………………………………………………………………………4.стр.

4.Формула Бейса……………………………………………………………………...7.стр.

5.Формула полной вероятности……………………………………………………...8 стр.

6.Комбинаторика……………………………………………………………………..9.стр.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Теория вероятностей является одним из классических разделов математики. Она имеет длительную историю. Основы этого раздела науки были заложены великими математиками. Назову, например, Ферма, Бернулли, Паскаля. Позднее развитие теории вероятностей определились в работах многих ученых. Большой вклад в теорию вероятностей внесли ученые нашей страны: П.Л.Чебышев, А.М.Ляпунов, А.А.Марков, А.Н.Колмогоров. Вероятностные и статистические методы в настоящее время глубоко проникли в приложения. Они используются в физике, технике, экономке, биологии и медицине. Особенно возросла их роль в связи с развитием вычислительной техники.

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

Таким образом, теория вероятностей занимается математическим анализом случайных событий и связанных с ними случайных величин.

 

 

 

 

 

 

 

 

 

 

 

Алгебра событий.

 

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

Да, оно произошло. Нет, оно не произошло.                     

Например, у меня есть лотерейный билет. После опубликования результатов розыгрыша лотереи интересующее меня событие – выигрыш тысячи рублей либо происходит, либо не происходит. События принято обозначать заглавными латинскими буквами: A,B,C,.. С событиями можно совершать операции. Эти операции являются основой алгебры событий. Объединением двух событий С=А В называется событие С, которое происходит тогда и только тогда, когда происходит хотя бы одно из этих событий А и В.

Пересечением двух событий D=А В называется событие, которое происходит тогда и только тогда, когда происходят и А и В. Противоположным событием А* к событию А называется такое событие, которое происходит тогда и только тогда, когда не происходит событие А. Объединением C событий A1,A2,.Ak называется событие C= Ai, которое осуществляется тогда и только тогда, когда осуществляется хотя бы одно из событий Ai,i=1,.,k. Пересечением D событий A1,.,Ak называется событие D=∩Ai, которое осуществляется тогда и только тогда, когда осуществляются все события Ai,i=1,.,k.

 Разностью событий G=A\B называется событие, которое происходит тогда и только тогда, когда происходит событие А, но не происходит событие В. Среди событий особое место занимают невозможное событие и достоверное событие. Невозможное событие – это такое событие, о котором заранее известно, что оно произойти не может. Его обозначают символом . Достоверное событие – это такое событие, о котором заранее известно, что оно произойдет. Его обозначают буквой Ω. События A и B называются не пересекающимися, если одновременно не могут осуществиться и событие A и событие B. В таких случаях также говорят, что пересечение A∩B есть невозможное событие .

Некоторую совокупность L событий называют алгеброй событий, если она удовлетворяет следующим условиям. Эта совокупность L содержит невозможное событие и достоверное событие . Если L содержит некоторое событие А, то она содержит и противоположное событие А*. Если совокупность L содержит некоторые события A1,A2,.,Ak, то она содержит и объединение С= Ai и пересечение D=∩Аi этих событий.

Например, алгеброй событий L является самая скудная такая алгебра, которая состоит всего из двух событий: из невозможного события и достоверного события . В самом деле, сколько бы мы ни составляли объединений и пересечений из этих событий, и сколько бы мы ни брали противоположных событий, мы не получим ничего другого, кроме как опять же события и . Действительно, имеем: *= , *= ,

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

    

     *= , *= , = , .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вероятность.

 

Теория вероятностей изучает случайные события. Это значит, что до определенного момента времени, вообще говоря, нельзя сказать заранее о случайном событии А произойдет это событие или нет. Только после этого момента реализуется определенность: Да, событие А произошло, или наоборот Нет, событие А не произошло, т.е. произошло событие А*. Каждому из рассматриваемых случайных событий приписывается число P ,0≤P≤1(P(A),P(B),P(C),.), которое называется его вероятностью. Это число характеризует шансы, что соответствующее событие произойдет. На практике для интересующих событий числа P назначаются, исходя из опыта и здравого смысла. Когда говорят о событиях, оговаривают обстоятельства, при которых рассматриваются эти события. Принимают, что Р(Ω)=1, Р( )=0. Если события A1,A2,.,Ak попарно не пересекаются, то полагают Р( Ai)=Р (A1)+Р(A2)+.+Р(Ak).

Поэтому Р(A)+Р (A*)=1. Например, если подбрасывается хорошо сбалансированная монета, то вероятность того события A, что она упадет орлом вверх принимается равной ½ , а вероятность противоположного события A*, то есть того, что она упадет решкой вверх, принимается тоже равной 1/2. При этом событие, состоящее в том, что монета встанет и останется стоять на ребре, принимается за невозможное. Если бросают игральную кость, то вероятность того, что выпадет, например, четыре очка, принимается равной  1/6. Вероятность противоположного события, то есть того, что выпадет какое-либо число очков, не равное четырем, принимается равной 5/6. Если из хорошо перетасованной колоды в пятьдесят две карты вынимают наугад одну карту, то вероятность того, что вынут короля, равна 4/52=1/13 и т. д. Говорят, что некоторое событие B благоприятствует событию A, если всякий раз как происходит событие B, происходит и событие A . Принимают следующее соглашение. Если из n всех возможных непересекающихся равновозможных событий, то есть таких, для которых вероятности полагаются равными, некоторому событию A благоприятствует m из таких равновозможных случаев, то принимают      Р(A)=m/n.  

В приведенном выше примере с колодой карт имеется n=52 равновозможных события: вынут одну какую-нибудь карту. Событию A–тому, что вынут короля, благоприятствуют m=4 события: B1–вынут короля пик, B2–короля треф, B3–короля бубен, B4–короля червей. И только такие события Bi благоприятствуют событию A. При этом A есть объединение событий Bi: A=U Bi и события Bi и Bj не пересекаются: Bi∩Bj= ,i≠j. Поэтому и принимают Р(А)=m/n=4/52=1/13. Данное определение вероятности через благоприятствующие равновозможные непересекающиеся события называют часто классическим определением вероятности. Оно подтверждается на практике в виде закона больших чисел. Он проявляется следующим образом. Если сделать большое число n* испытаний, в каждом из которых может появиться событие A, то в результате оказывается, что число m* появлений события A оказывается как правило очень близким к величине Р(A), то есть выполняется с вероятностью очень близкой к единице – практически обязательно, с большой степенью точности приближенное равенство      m*/n* ≈ m/n=Р(A).                                     

     Условной вероятностью события А по событию В называют величину Р(А|В), которая дает равенство Р (А∩В)=Р(A|B)·P(B). Смысл этого определения таков. Условная вероятность оценивает шансы осуществления события А, когда известно, что произошло событие В. События А и В называются независимыми, если Р (A|B)=P(A). Тогда Р(А∩В)=Р(A)·P (B). Иначе говоря, события А и В независимы, когда вероятность осуществления события А не зависит от того, осуществилось или нет событие В. И наоборот, вероятность осуществления события В не зависит от осуществления события А.

Например, пусть бросают две не связанные друг с другом игральные кости. Пусть событие А–на первой кости выпало 4 очка. Событие В–на второй кости выпало 2 очка. Тогда Р(А)=1/6,Р (В)=1/6. События А и В естественно полагать независимыми. Стало быть, полагаем Р(А|B)=P(A), P (B|A)=P(B) и P(А∩В)=P(A)·P (B)=1/6·1/6=1/36. То есть вероятность события С=А∩В – на первой кости выпало 2 очка и при этом на второй кости выпало 4 очка равна 1/36. Несколько событий A1,A2,.,Ak называются независимыми в совокупности, если Р(∩Ai)=Р(A1)·Р (A2)·.·Р(Ak). Важно заметить, что из попарной независимости всех событий Аi и Aj, i=1,.,k, j=1,.,k, i j, вообще говоря, не следует независимость событий A1,A2,.,Ak в совокупности. В этом можно убедиться на конкретном примере.

Подчеркнем еще раз, что физической основой для теории вероятностей является следующее статистическое свойство устойчивости частот. Буквой А обозначим случайное событие, связанное с некоторым повторяющимся опытом. Пусть опыт повторяется n* раз при одинаковых условиях. Пусть *–число появлений событий А. Относительная частота появления событий А определяется формулой

                                           

Если неограниченно увеличивать число повторений опыта , то относительная частота будет устойчиво приближаться к некоторой фиксированной величине Р

(А) и отклоняться от нее тем меньше и реже, чем больше n*. Эта величина и является вероятностью P события А. Если в теории вероятность Р(А) определена правильно, то

оказывается, что теоретическое число Р(А) совпадает с описанным выше практическим пределом. Это обстоятельство и позволяет численно оценивать вероятность случайного события в теории.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Формула Бейеса.

 

Пусть мы знаем вероятности событий А и В: Р(А) и Р(В). И пусть мы знаем условную вероятность события А по В: Р(A|B). Как найти условную вероятность P(B|A). На этот вопрос отвечает формула Бейеса.

     Р(B|A)=P(A|B)·P(B)/P(A)                          

Разумеется этой формулой можно пользоваться только при условии, что Р(А) 0.

Формула Бейеса выводится из следующих равенств

     Р(В А)=Р(В|A)·P(A)                             

     Р(A B)=Р(A|B)·P(B)  причем  Р(В А)=Р(A B) так как пересечение событий В и А очевидно не зависит от порядка, в котором записаны А и В, т.е. В А=A B. В случае Р(А)=0 принимаю обычно, что Р (В|A) есть величина неопределенная.

Пример задачи для формулы Бейеса.                      

     Задача 6.1.

Пусть имеем те же урны с теми же наборами шаров, как и в задаче (5.1). Снова из выбранной наугад урны выбрали наугад шар. Оказалось, что вынули черный шар.

Какова вероятность, что его вынули из третьей урны?

     Решение:

Пусть В – событие, состоящее в том, что вынули черный шар. События Ei те же, что  и в решении задачи (5.1). Интересующая нас вероятность есть условная вероятность Р(E3|B). По формуле Бейеса (4.5) имеем

     Р(Е3|B)=P(B|E3)·P(E3)/(P(B|E1)·P(E1)+P(B|E2)·P(E2)+P(B|E3)·P(E3))  (6.1)

У нас: Р(Ei)=1/3, i=1,2,3, P(B|E1)=3/10,

P(B|E2)=1/2, P(B|E3)=7/10. Таким образом, получаем

Р(Е3|B)=(7/10)·(1/3)/((1/3)·(7/10+5/10+3/10))=(7/10)/(15/10)=7/15       (6.2)

     Ответ:         Вероятность того, что вынули шар из третьей урны, при условии, что шар оказался черным равна 7/15.

 

 

 

 

 

 

 

Формула полной вероятности.

Пусть имеем полную группу из n попарно непересекающихся событий . То есть

     ,                              

     , , . Пусть мы знаем условные вероятности некоторого события А по Еi: Р(А|Ei) и вероятности Р(Ei), i=1,.,n. Справедлива следующая формула полной вероятности для события А Р(А)=Р(A|E1)·P(E1)+.+P(A|En)·P(En)                     

Доказательство этой формулы вытекает из следующих равенств

     P(A)=P( )=P(A ( Ei))=P(A E1)+.+P(A En)=

     =Р(A|E1)·P(E1)+.+P(A|En)·P(En). Из элементарной формулы Бейеса (3.1) и формулы полной вероятности вытекает следующая более полная формула Бейеса

     Р(Еi|A)=P(A|Ei)·P(Ei)/(Р(A|E1)·P(E1)+.+P(A|En)·P(En))  

Пример задачи для формулы полной вероятности.                

     Задача 5.1.

Пусть имеем три урны с шарами. В первой урне 7 белых и 3 черных шара. Во второй урне 7 белых и 7 черных шаров. В третьей урне 3 белых и 7 черных шаров. Наугад выбрали одну урну. Из этой урны наугад вынули шар. Какова вероятность, что вынули белый шар?

     Решение:

Пусть событие А – вынули белый шар, событие Ei – вынули шар из 

i-той урны, i=1,2,3. Вероятности P(Ei) полагаем равными, т.е. Р(Ei)=1/3. Вероятность Р

(A|E1)=7/10, вероятность Р(А|E2)=7/14=1/2, вероятность Р (А|E3)=3/10. Таким образом по формуле полной вероятности (4.3) имеем

     Р(А)=Р(A|E1)·Р(E1)+Р(A|E2)·Р(E2)+Р(A|E3)·Р(E3)=

     =(1/3)·(7/10+5/10+3/10)=(1/3)·15/10=1/2                  

     Ответ:         Вероятность вынуть белый шар равна ½.

 

 

 

 

 

 

 

 

 

 

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

 

Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Примеры комбинаторных конфигураций и задач

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

• Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
• Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
• Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
• Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
• Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Примерами комбинаторных задач являются:

1. Сколькими способами можно разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?
2. Сколько существует функций из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
3. Сколько существует различных перестановок из 52 игральных карт?

Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.

4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?

Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

 

Разделы комбинаторики

Перечислительная комбинаторика

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Экстремальная комбинаторика

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

Теория Рамсея

Основная статья: Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Топологическая комбинаторика

Топологическая комбинаторика (англ.) применяет идеи и методы комбинаторики в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Открытые проблемы

Комбинаторика, и в частности, теория Рамсея, содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

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

Как в физике объясняется необратимость тепловых процессов. Почему все процессы в природе необратимы, и самые трагические из них – старение и смерть организмов и какова вероятность того, что 20 000 обезьян, хаотически ударяя по клавишам пишущих машинок, напечатают без единой ошибки «Войну и мир» Л.Н.Толстого?

На эти вопросы нам дают ответы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы.

 

• Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
• Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.
• Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
• Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
• Раизер Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.
• Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна, 2006.
• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
• Риордан Дж. Введение в комбинаторный анализ. — пер. с англ. — М., 1963.
• Р. Стенли. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2
• Р. Стенли. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — ISBN 978-5-03-003476-8

Или http://ru.wikipedia.org/wiki/%CA%EE%EC%E1%E8%ED%E0%F2%EE%F0%E8%EA%E0

И

• Шейнин О. Б. Теория вероятностей. Исторический очерк. Берлин: NG Ferlag, 2005, 329 с.
• Ширяев, А. Н. «Вероятность», Наука. М.: 1989.
• Ширяев, А. Н. «Основы стохастической финансовой математики В 2-х т.», ФАЗИС. М.: 1998.