Тема Элементы комбинаторики Комбинаторика это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения

• Название: Тема Элементы комбинаторики Комбинаторика это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения
• Дата: 23.11.2021
• Размер: 1.75 Mb.
• Имя файла: lekcii16.pdf
• Тип: Конспект; #280266
• страница: 1 из 6

Теория вероятностей и математическая статистика
Краткий конспект лекций
Тема 1. Элементы комбинаторики
Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.
Комбинаторный принцип умножения если одну часть действия можно выполнить способами, а другую - способами, то все действие можно выполнить числом способов.
Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется:
5 различных ручек,
7 различных карандашей,
10 различных линеек.
Сколькими способами можно составить требуемый набор?
Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить
Число способов. Т.е. возможно 350 вариантов такого набора.
Пример. Сколько существует наборов длины из нулей и единиц?
Решение. Действием в данном случае является составление набора длины из нулей и единиц.
Набор будет составлен, если все позиций (мест) будут заполнены нулями и единицами. Действие распадается на частей: заполнить первую позицию, вторую и т.д., заполнить -ю позицию. Первую часть действия – написать первую компоненту - можно двумя способами: можно написать 0, а можно написать 1, написать вторую компоненту тоже можно двумя способами, и так все мест в наборе: на каждом месте можно написать либо 0 либо 1:

Тогда все действие согласно комбинаторному принципу умножения можно выполнить числом способов:
Комбинаторный принцип сложения. Если два действия взаимно исключают друг друга, и одно из них можно выполнить способами, а другое - способами, то оба действия можно выполнить числом способов.
Пример.
Выборкой объема из множества называется всякая последовательность из элементов множества
Если элементы в выборке не повторяются, то выборка называется бесповторной, иначе – выборкой с повторениями
При бесповторной выборке все равно, каким образом осуществляется выбор: берутся все элементы сразу, или же поочередно (по одному).
Расположение элементов выборки в определенном порядке называется упорядочением , при этом выборка называется упорядоченной, в противном случае – неупорядоченной.
Рассмотрим бесповторную выборку
Расположение различных элементов в определенном порядке называется перестановкой без повторений из элементов.
Например, на множестве из трех элементов возможны следующие перестановки:
Число различных перестановок без повторений из элементов обозначается и равно , т.е.
Сочетанием без повторений из элементов по называется неупорядоченное - элементное подмножество -элементного множества. Число сочетаний без повторений из элементов по равно
:
Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства в группе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются, то мы имеем случай сочетаний из 30 элементов по 3 без повторений:

Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.
Размещением без повторений из элементов по называется упорядоченное - элементное подмножество -элементного множества.
Теорема.
Число размещений без повторений из элементов по равно:
Доказательство. Чтобы получить упорядоченное -элементное подмножество - элементного множества, нужно выполнить два этапа: выбрать элементов из (это можно выполнить числом способов) и затем упорядочить выбранные элементы (это можно сделать числом способов). Согласно комбинаторному принципу умножения, все действие
- получить упорядоченное -элементное подмножество -элементного множества
– можно числом способов.
Свойства сочетаний без повторений:
1)
Доказательство. Поскольку и
, то утверждаемое очевидно.
2)
(без доказательства).
Значения могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).
Этот треугольник имеет вид:
1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1

Закономерность его построения такова: складывая две рядом стоящие числа, получаем число, стоящее ниже между ними. Первая строчка – значения числа сочетаний из 1 (
), вторая – из 2 (
- слева направо), и т.д.
Рассмотрим выборку с повторениями
Пусть имеется выборка из элементов, причем элементов из них - одинаковые.
1. Число различных перестановок на элементах такой выборки равно:
- число перестановок с повторениями на множестве из элементов
2. Сочетание с повторениями из элементов по - неупорядоченная выборка элементов с возвращением из множества, содержащего элементов:
- число различных сочетаний с повторениями из элементов по
3. Размещения с повторениями из элементов по - расположение различных шаров по различным ячейкам
- число различных размещений с повторениями
Пример.
Сколько различных
4-буквенных слов можно составить из символов
?
Решение. Другими словами, требуется найти число перестановок с повторениями на 4 элементах выборки, в которой два элемента одинаковы:
Пример. Сколько различных перестановок можно составить из букв слова АБАКАН?
Решение. Требуется найти число перестановок на множестве из 6 элементов, среди которых три элемента одинаковы:
Верно обобщение рассматриваемой формулы: число различных перестановок на множестве из элементов, среди которых имеется

элементов первого вида, элементов второго вида,
… элементов
-го вида равно:
Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА?
Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых: буква К повторяется 2 раза; буква О повторяется 3 раза; буква Л повторяется 2 раза буква А повторяется 1 раз.
Таким образом,
Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида?
Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам?
Решение. Поскольку по условию задачи в один вагон могут сесть несколько человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещения с повторениями:
Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить 9 способами, и т.д. :
Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам по одному в вагон?

Решение. Поскольку по условию задачи в один вагон могут сесть только один человек, и поскольку рассадка зависит от того кто в каком вагоне находится, то используем формулу размещений без повторений:
Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить 9 способами, и т.д. :
Пример. Сколько различных сигналов можно составить из четырех флажков различных цветов, если каждый сигнал должен состоять не менее чем из двух флажков?
Решение. Составить сигнал можно из двух флажков, из трех или из четырех.
Перечисленные ситуации взаимно исключают друг друга (два флажка – это не три и не четыре), поэтому вычислим, сколькими способами можно составить сигнал в каждой из перечисленных ситуаций, и сложим полученные результаты.
Действие – составить сигнал – означает выбрать флажки из четырех и расположить их в определенном порядке. Таким образом, в каждом случае нужно выполнить два этапа: первый - выбрать флажки, второй – расположить выбранные флажки в определенном порядке.
Составляем сигналы из двух флажков: выбрать два флажка из четырех можно различными способами, и расположить выбранные два флажка в определенном порядке можно числом способов. Таким образом, согласно комбинаторному принципу умножения, можно составить различных сигналов из двух флажков.
Составляем сигналы из трех флажков: выбрать три флажка из четырех можно различными способами, и расположить выбранные три флажка в определенном порядке можно числом способов. Таким образом, согласно комбинаторному принципу умножения, можно составить различных сигналов из трех флажков.
Составляем сигналы из четырех флажков: выбрать четыре флажка из четырех можно
- одним способом, а расположить выбранные четыре флажка

в определенном порядке можно способами.
Значит, можно составить различных сигнала из четырех флажков.
Применим теперь комбинаторный принцип сложения: всего существует сигналов из не менее, чем двух флажков.
Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.
Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно
10.000.
Число всех возможных комбинаций из
30 букв по две равно
Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы).
Итого, полное количество комбинаций по две буквы равно 900.
Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.
Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно
270.000.000.
Тема 2. Основные понятия и теоремы теории вероятностей
Классификация событий
Одним из основных понятий теории вероятностей является понятие события. Под событием понимают любой факт, который может произойти в результате опыта или испытания. Под опытом, или испытанием, понимается осуществление определѐнного комплекса условий.
Примеры событий:
– попадание в цель при выстреле из орудия (опыт — произведение выстрела; событие — попадание в цель);
– выпадение двух гербов при трѐхкратном бросании монеты (опыт — трѐхкратное бросание монеты; событие — выпадение двух гербов);
– появление ошибки измерения в заданных пределах при измерении дальности до цели (опыт — измерение дальности; событие — ошибка измерения).
Можно привести бесчисленное множество подобных примеров. События обозначаются заглавными буквами латинского алфавита и т.д.
Различают события совместные и несовместные. События называются совместными, если наступление одного из них не исключает наступления другого. В противном случае события называются несовместными. Например, подбрасываются две игральные кости.

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

Например, если событие есть попадание в цель при первом выстреле, событие — при втором, то событие есть попадание в цель вообще, безразлично, при каком выстреле
— первом, втором или при обоих вместе.
Произведением, или пересечением, нескольких событий называется событие, состоящее в совместном появлении всех этих событий.
Например, если событие есть попадание в цель при первом выстреле, событие — при втором, то событие состоит в том, что в цель попали при обоих выстрелах.
Классическое определение вероятности случайного события
Для количественного сравнения событий по степени возможности их появления вводится числовая мера, которая называется вероятностью события.
Вероятностью события называется число, являющееся выражением меры объективной возможности появления события.
Вероятность события равна отношению числа случаев , благоприятствующих ему, из общего числа единственно возможных, равновозможных и несовместных случаев к числу.
Свойство 1. Если все случаи являются благоприятствующими данному событию , то это событие обязательно произойдет. Следовательно, рассматриваемое событие является достоверным, а вероятность его появления , так как в этом случае
Свойство 2. Если нет ни одного случая, благоприятствующего данному событию , то это событие в результате опыта произойти не может. Следовательно, рассматриваемое событие является невозможным, а вероятность его появления , так как в этом случае :
Свойство 3. Вероятность наступления событий, образующих полную группу, равна единице.
Свойство 4. Вероятность наступления противоположного события определяется так же, как и вероятность наступления, события.
Важное достоинство классического определения вероятности события состоит в том, что с его помощью вероятность события можно определить, не прибегая к опыту, а исходя из логических рассуждений.
Элементы комбинаторики
В теории вероятностей часто используют размещения, перестановки и сочетания.
Если дано множество , то размещением (сочетанием) из элементов по называется любое упорядоченное (неупорядоченное) подмножество элементов множества . При размещение называется перестановкой из элементов.
Статистическое определение вероятности
На практике часто классическое определение вероятности неприменимо по двум причинам: во-первых, классическое определение вероятности предполагает, что общее число случаев должно быть конечно. На самом же деле оно зачастую не ограничено. Во-

вторых, часто невозможно представить исходы опыта в виде равновозможных и несовместных событий.
Частота появления событий при многократно повторяющихся Опытах имеет тенденцию стабилизироваться около какой-то постоянной величины. Таким образом, с рассматриваемым событием можно связать некоторую постоянную величину, около которой группируются частоты и которая является характеристикой объективной связи между комплексом условий, при которых проводятся опыты, и событием.
Вероятностью случайного события называется число, около которого группируются частоты этого события по мере увеличения числа испытаний.
Это определение вероятности называется статистическим.
Преимущество статистического способа определения вероятности состоит в том, что он опирается на реальный эксперимент. Однако его существенный недостаток заключается в том, что для определения вероятности необходимо выполнить большое число опытов, которые очень часто связаны с материальными затратами. Статистическое определение вероятности события хотя и достаточно полно раскрывает содержание этого понятия, но не дает возможности фактического вычисления вероятности.
Геометрическая вероятность
В классическом определении вероятности рассматривается полная группа конечного числа равновозможных событий. На практике очень часто число возможных исходов испытаний бесконечно. В таких случаях классическое определение вероятности неприменимо. Однако иногда в подобных случаях можно воспользоваться другим методом вычисления вероятности. Для определенности ограничимся двумерным случаем.
Пусть на плоскости задана некоторая область площадью , в которой содержится другая область площадью (рис. 3). В область наудачу бросается точка. Чему равна вероятность того, что точка попадет в область ? При этом предполагается, что наудачу брошенная точка может попасть в любую точку области , и вероятность попасть в какую- либо часть области пропорциональна площади части и не зависит от ее расположения и формы.
Таким образом, в общем случае, если возможность случайного появления точки внутри некоторой области на прямой, плоскости или в пространстве определяется не положением этой области и ее границами, а только ее размером, т. е. длиной, площадью или объемом, то вероятность попадания случайной точки внутрь некоторой области определяется как отношение размера этой области к размеру всей области, в которой может появляться данная точка. Это есть геометрическое определение вероятности.
Аксиомы теории вероятностей
Из статистического определения вероятности случайного события следует, что вероятность события есть число, около которого группируются частоты этого события, наблюдаемые на опыте. Поэтому аксиомы теории вероятностей вводятся так, чтобы вероятность события обладала основными свойствами частоты.

Аксиома 1. Каждому событию соответствует определенное число , удовлетворяющее условию и называемое его вероятностью.
Аксиома 2. Вероятность достоверного события равна единице.
Аксиома 3. Вероятность невозможного события равна нулю.
Аксиома 4. (аксиома сложения). Вероятность суммы двух несовместных событий равна сумме их вероятностей.
Основные теоремы теории вероятностей
На практике обычно требуется определить вероятность событий, непосредственное экспериментальное воспроизведение которых затруднено.
Обычно такая оценка и производится с целью выявления наиболее рациональных конструктивных параметров элементов перспективной техники.
Поэтому, как правило, для определения вероятностей событий применяются не непосредственные прямые методы, а косвенные, позволяющие по известным вероятностям одних событий определять вероятности других событий, с ними связанных.
Применяя эти косвенные методы, мы всегда в той или иной форме пользуемся основными теоремами теории вероятностей. Этих теорем две:
• теорема сложения вероятностей;
• теорема умножения вероятностей.
Введем понятие о сумме событий и произведении событий.
Суммой двух событий А и В называется событие С состоящее в появлении хотя бы одного из событий А и В. Суммой нескольких событий называется событие, состоящее в появлении хотя бы одного из этих событий.
Произведением двух событий А и В называется событие С, состоящее в совместном выполнении события А и В. Произведением нескольких событий называется событие, состоящее в совместном появлении всех этих событий.
Теорема сложения вероятностей
Вероятность суммы двух несовместных событий равна сумме вероятностей этих событий:
Р(А+В) = Р(А) + Р(В)
Теорема сложения вероятностей применима к любому числу несовместных событий.
В общем виде ее удобно записать:
Р(∑Ai) = ∑Р(Ai)
Отметим следствия вытекающие из теоремы сложения вероятностей.
Следствие 1: Если события А1, А2, …, Аn образуют полную группу несовместных событий, то сумма их вероятностей равна единице:
∑Р(Ai) = 1

Перед тем как вывести второе следствие теоремы сложения, введем понятие
«противоположные события».
Противоположными событиями называются два несовместных события, образующих полную группу. Событие противоположное событию А принято обозначать
A.
Пример:
Событие А – безотказная работа всех элементов технической системы; A — отказ хотя бы одного элемента.
Следствие 2: Сумма вероятностей противоположных событий равна единице:
P(A) + P(A) =1
Следствие 2 есть частный случай следствия 1.
Вероятность суммы двух совместных событий выражается формулой:
Р(А+В) = Р(А) + Р(В) – P(AB)
Аналогично вероятность суммы трех совместных событий вычисляется по формуле:
Р(А+В+С) = Р(А) + Р(В) + Р(С) – P(AB) – P(AС) – P(ВС) + Р(АВС)
Общая формула для вероятности суммы любого числа совместных событий:
Р(∑Ai) = ∑Р(Ai) — ∑Р(AiAj) + ∑Р(AiAjAk) — (-1)n-1P(A1A2…An) где суммы распространяются на различные значения индексов i; i, j; i, j, k и т.д.
Из формул можно записать аналогичную формулу для произведения событий
P(AB) = Р(А) + Р(В) – Р(А+В)
Р(АВС) = Р(А) + Р(В) + Р(С) – P(A+B) – P(A+С) – P(В+С) + Р(А+В+С)
Теорема умножения вероятностей
Введем понятие независимые и зависимые события.
Событие А называется независимым от события В, если вероятность события А не зависит от того, произошло событие В или нет.
Событие А называют зависимым от события В, если вероятность события А меняется в зависимости от того, произошло событие В или нет.
Вероятность события А, вычисленная при условии, что имело место другое событие
В, называется условной вероятностью события А и обозначается Р (А/В)
Пример:
В урне два белых и один черный. Два лица вынимают из урны по одному шару.
Рассматриваются события: А- появление белого шара у 1-го лица; В – появление белого шара у 2-го лица.
Решение: Р(А) до того как произошло событие В равно 2/3. Если событие В произошло, то Р(А)=1/2. Таким образом, событие А зависит от события В.
Условие независимости события А от события В можно записать в виде:
Р(А/В) = P(A) (10)

а, условие зависимости: Р(А/В) ≠ P(A)
Теорема умножения: Вероятность произведения двух событий равна произведению вероятности
Р(АВ) = P(A)⋅ Р(В/А)
Вероятность произведения нескольких событий равна произведению вероятностей этих событий, причем вероятность каждого следующего по порядку события вычисляется при условии, что все предыдущие имели место:
Р(А1А2…Аn ) = P(A1)⋅ Р(А2/А1)⋅ Р(А3/А1А2)⋅ …⋅ Р(Аn/А1А2…А n-1) (13)
Следствие1: Если событие А не зависит от события В, то и событие В не зависит от события А
Следствие2: Вероятность произведения двух независимых событий равна произведению вероятностей этих событий
P(AВ) = P(А)
⋅ Р(В)
Р(А1А2…Аn ) = P(A1)⋅ Р(А2)⋅ ….⋅ Р(Аn)
Формула полной вероятности
Следствием основных теорем является так называемая формула полной вероятности.
Пусть требуется определить вероятность некоторого события А, которое может произойти вместе с одним из событий:
Н1, Н2, ….Нn,
Образующих полную группу несовместных событий. Будем эти события называть гипотезами.
В этом случае, вероятность события А вычисляется как сумма произведений вероятности каждой гипотезы на вероятность события при этой гипотезе
Р(А)=∑Р(Hi)⋅ P(A/Hi)
Теорема гипотез (формула Бейеса)
Имеется полная группа несовместных гипотез Н1, Н2, …., Нn. Вероятности этих гипотез до опыта известны и равны соответственно Р(Н1), Р(Н2)…. Р(Нn).
Произведен опыт, в результате которого наблюдалось появление некоторого события
А. Как следует изменить вероятность гипотез в связи с появлением этого события? По существу речь идет о том, чтобы найти условную вероятность Р(Нi/А) для каждой гипотезы.
Р(Нi/А) = [Р(Нi)⋅ Р(Нi/A] / [∑Р(Hi)⋅ P(A/Hi)], i = 1, 2, …, n