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

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

Соединения. Пустъ А – множество, состоящее из конечного числа элементов a ₁, a _2, a ₃… a_n. Из различных элементов множества А можно образовывать группы. Если в каждую группу входит одно и то же число элементов m (m из n), то говорят, что они образуют соединения из n элементов пo m в каждом. Различают три вида соединений: размещения, сочетания и перестановки.

Перестановки. Пустъ А – множество, состоящее из конечного числа элементов a ₁, a _2, a ₃… a_n. Из различных элементов множества А можно образовывать группы. Если в каждую группу входит одно и то же число элементов m (m из n), то говорят, что они образуют соединения из n элементов пo m в каждом. Различают три вида соединений: размещения, сочетания и перестановки.

Размещения. Соединения каждое из которых содержит m различных элементов (m < n) взятых из n элементов множества A, отличающихся друг oт друга или составом элементов, или их порядком называются размещениями из n элементов по m в каждом. Число таких размещений обозначается символом

Теорема 1. Число всех различных перестановок из n элементов равно

=n(n-1)(n-2)(n-3)….3*2*1=1*2*3…(n-1)n=n!

Tеорема 2. Число всех размещений из n элементов по m вычисляется по формуле:

 

Иногда для записи числа размещений используют следующую формулу:

 

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

Теорема 3. Число всех сочетаний из n элементов по m определяется формулой:

 

 

Иногда для записи числа размещений используют следующую формулу:

 

2. Сущность и условия применения теории вероятностей.

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

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

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

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

Основные понятия теории вероятностей.

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

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

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

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

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

Виды событий:

достоверное событие - событие, которое в результате опыта обязательно произойдет.

невозможное событие - событие, которое в результате опыта не может произойти.

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

Вероятностью события A (обозначают P(A)) называется отношение числа исходов, благоприятных событию A (обозначают m(A)), к числу всех исходов испытания – N т.е. P(A) = m(A)/ N.

4. Вероятностное пространство.

Вероятностное пространство – это математическая модель случайного эксперимента (опыта) в аксиоматике А.Н. Колмогорова. Вероятностное пространство содержит в себе всю информацию о свойствах случайного эксперимента, необходимую для его математического анализа средствами теории вероятностей. Любая задача теории вероятности решается в рамках некоторого вероятностного пространства, полностью заданного изначально. Задачи, в которых вероятностное пространство задано не полностью, а недостающую информацию следует получить по результатам наблюдений, относятся к области математической статистики.

Вероятностное пространство определяется тройкой компонент (символов) (Ω,S,P), где Ω-пространство элементарных событий

S-∂(сигма)-алгебра событий, Р - вероятность, Ω-достоверное событие, S-система подмножеств пространства элементарных исходов Ω.

5. Непосредственный подсчет вероятности.

Классическое определение вероятности основано на понятии равновозможности событий.

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

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

Вероятностью события A (обозначают P(A)) называется отношение числа исходов, благоприятных событию A (обозначают m(A)), к числу всех исходов испытания – N т.е. P(A) = m(A)/ N.

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

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

Доказательство. Так как, то поделив все части неравенства на N, получим

 

Откуда по классическому определению вероятности следует, что

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

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

6. Теоремы сложения вероятностей.

Если А и В несовместны, то Р(А + В) = Р(А) +Р(В)

Если и противоположные события, то

 

Если А и В совместны, то теорема сложения принимает вид:

Р(А+В)=Р(А)+Р(В) - Р(АВ).

7. Теоремы умножения вероятностей.

Если А и В независимые события, то

Р(АВ) = Р(А)*Р(В).

Если А и В совместны, то

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

8. Теорема о вероятности хотя бы одного события

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

P(A)=1- …. ,где =P()

=1- , i=1,2,….n

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

Пусть событие А может наступить при условии реализации одной из гипотез Н₁, Н₂,..., Н_n, образующих полную группу событий. Тогда

 

Формула (1) называется формулой полной вероятности.

Теорема Байеса.

Предположим, что в результате испытания событие А произошло. Какова вероятность, что событие А произошло в результате реализации гипотезы Н _k, т.е. P (H _k/ A) =? (происходит переоценка вероятностей гипотез). Ответ дает формула Байеса:

 

Формула бернулли.

При n испытаниях событие А произойдет ровно k-раз. Обозначается Pn(k). Ответ на этот вопрос дает формула Бернулли: Pn(k)=

Локальная теорема Лапласа

Если вер-тьp появления события А в каждом испытании постоянна и отлична от нуля и единицы, то вер-тьтого,что события А появится в n-испытаниях ровно k-раз приближенно =: Pn(k)=1/ * ᵠ(x), ᵠ(х)=1/ * при x=|k-np/ |

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

Соединения. Пустъ А – множество, состоящее из конечного числа элементов a ₁, a _2, a ₃… a_n. Из различных элементов множества А можно образовывать группы. Если в каждую группу входит одно и то же число элементов m (m из n), то говорят, что они образуют соединения из n элементов пo m в каждом. Различают три вида соединений: размещения, сочетания и перестановки.

Перестановки. Пустъ А – множество, состоящее из конечного числа элементов a ₁, a _2, a ₃… a_n. Из различных элементов множества А можно образовывать группы. Если в каждую группу входит одно и то же число элементов m (m из n), то говорят, что они образуют соединения из n элементов пo m в каждом. Различают три вида соединений: размещения, сочетания и перестановки.

Размещения. Соединения каждое из которых содержит m различных элементов (m < n) взятых из n элементов множества A, отличающихся друг oт друга или составом элементов, или их порядком называются размещениями из n элементов по m в каждом. Число таких размещений обозначается символом

Теорема 1. Число всех различных перестановок из n элементов равно

=n(n-1)(n-2)(n-3)….3*2*1=1*2*3…(n-1)n=n!

Tеорема 2. Число всех размещений из n элементов по m вычисляется по формуле:

 

Иногда для записи числа размещений используют следующую формулу:

 

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

Теорема 3. Число всех сочетаний из n элементов по m определяется формулой:

 

 

Иногда для записи числа размещений используют следующую формулу:

 

2. Сущность и условия применения теории вероятностей.

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

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

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

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

Основные понятия теории вероятностей.

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

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

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

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

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

Виды событий:

достоверное событие - событие, которое в результате опыта обязательно произойдет.

невозможное событие - событие, которое в результате опыта не может произойти.

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

Вероятностью события A (обозначают P(A)) называется отношение числа исходов, благоприятных событию A (обозначают m(A)), к числу всех исходов испытания – N т.е. P(A) = m(A)/ N.

4. Вероятностное пространство.

Вероятностное пространство – это математическая модель случайного эксперимента (опыта) в аксиоматике А.Н. Колмогорова. Вероятностное пространство содержит в себе всю информацию о свойствах случайного эксперимента, необходимую для его математического анализа средствами теории вероятностей. Любая задача теории вероятности решается в рамках некоторого вероятностного пространства, полностью заданного изначально. Задачи, в которых вероятностное пространство задано не полностью, а недостающую информацию следует получить по результатам наблюдений, относятся к области математической статистики.

Вероятностное пространство определяется тройкой компонент (символов) (Ω,S,P), где Ω-пространство элементарных событий

S-∂(сигма)-алгебра событий, Р - вероятность, Ω-достоверное событие, S-система подмножеств пространства элементарных исходов Ω.

5. Непосредственный подсчет вероятности.

Классическое определение вероятности основано на понятии равновозможности событий.

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

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

Вероятностью события A (обозначают P(A)) называется отношение числа исходов, благоприятных событию A (обозначают m(A)), к числу всех исходов испытания – N т.е. P(A) = m(A)/ N.

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

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

Доказательство. Так как, то поделив все части неравенства на N, получим

 

Откуда по классическому определению вероятности следует, что

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

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

6. Теоремы сложения вероятностей.

Если А и В несовместны, то Р(А + В) = Р(А) +Р(В)

Если и противоположные события, то

 

Если А и В совместны, то теорема сложения принимает вид:

Р(А+В)=Р(А)+Р(В) - Р(АВ).

7. Теоремы умножения вероятностей.

Если А и В независимые события, то

Р(АВ) = Р(А)*Р(В).

Если А и В совместны, то

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

8. Теорема о вероятности хотя бы одного события

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

P(A)=1- …. ,где =P()

=1- , i=1,2,….n

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

Пусть событие А может наступить при условии реализации одной из гипотез Н₁, Н₂,..., Н_n, образующих полную группу событий. Тогда

 

Формула (1) называется формулой полной вероятности.

Теорема Байеса.

Предположим, что в результате испытания событие А произошло. Какова вероятность, что событие А произошло в результате реализации гипотезы Н _k, т.е. P (H _k/ A) =? (происходит переоценка вероятностей гипотез). Ответ дает формула Байеса: