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

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

	С возвращением	Без возвращения
Упорядочен.	М^n (1)	A^nm (2)
Неупорядоч.	C^n (m+n-1) (4)	C^nm (3)

1. Ω= {ω:ω=(a₁,a₂,…,a_n);a_i€{1….M} i€{1,2,…n}}

N(Ω₁)= Мⁿ

M+M+…..+M=M(1+1+….+1)=M*M= Мⁿ

2. Ω= {ω:ω=(a₁,a₂,…,a_n);a_i€{1….M} j,i€{1,2,…n} n≤M a_i≠a_j сли i≠j}

N(Ω₂)= M(M-1)*…*(M-(n-1))/(M-n)!= M!/(M-n)!= Aⁿ_m число размещений

3. Ω= {ω:ω=[a₁,a₂,…,a_n];a_i€{1….M} j,i€{1,2,…n} n≤M a_i≠a_j сли i≠j}}

N(Ω₃)= N(Ω₂)/n!= Aⁿ_m /n! = M!/((M-n)!n!)= Cⁿ_m число сочетаний

4. Ω= {ω:ω=[a₁,a₂,…,a_n];a_i€{1….M} i€{1,2,…n} n≤M}

N(Ω₄)= Cⁿ _(m+n-1)

Ω ={гг,гр,рг,рр}

А={гг,гр,рг} -1 раз греб

В={рр,рг,гр} -1 раз решка

Р(А)= ∑ _{ω €А}Р(ω) =Р(гг)+Р(гр)+Р(рг)= ¼+¼+¼ = ¾

Р(Ω) = 1

Р(Ø)=0

1. Р(АUB)

Р(АUB) = ∑ Р(ω)=S(AUB)=S(A)+S(B)-S(A*B)= P(A)+P(B)-P(A*B)

Р(АUB)= P(A)+P(B)-P(A*B)

2. P(AUBUC)=S(AUBUC)=S(A)+S(B)+S(C)-S(AB)-S(AC)-S(BC)+S(ABC)= P(A)+P(B)+P(C)-P(AB)-P(AC)-P(BC)+P(ABC)

P(A₁UA₂U…A_n)= ∑ⁿ _i=1P(A_i) - ∑ⁿ _{i,j=1 i≠j}P(A_i,A_j)+ ∑ⁿ _{k,i,j=1 i≠j≠k}P(A_i,A_j,A_k)+…..+(-1)ⁿ⁺¹∑P(A₁+A₂+…A_n)

P(A₁UA₂U…A_n) ≤P(A₁)+P(A₂)+….+P(A_n)

Свойства

1. АВ=ВА, умножение AUB=ВUА сложение коммутативности

2. (AB)С=А(ВС) (AUB) UС=АU (ВUС) ассоциативности

3. А(ВUС)=АВUАС, АU(ВС)=(АUВ)(АUС) дистрибутивности

4. А*А=А АUА=А идемпотентности

3. А и А^- несовместны

Р(А)+Р(А^- ) = 1

4. Р(АΔВ)= S(АΔВ)=S(A)+S(B)-2S(AB)= P(A)+P(B)-2P(AB)

АΔВ=(A\B)U(B\A)

АΔВ=AB^-=BA^-

Условная вероятность

Условной вероятностью называют верятность события В при условии, что произошло событие А является Р(В/А)= Р(АВ)/Р(А), Р(А)>0

Св-ва усл.вероятности

1. Р(В+С/А)=Р[(В+С) ∩А]/Р(А)=Р(ВА+СА)/Р(А)=(Р(ВА)+Р(СА))/Р(А)=Р(ВА)/Р(А)+Р(СА)/Р(А)=Р(В/А)+Р(С/А)

Р(В+С/А)= Р(В/А)+Р(С/А)

В и С не совместны В*С = Ø

2. ВсА

Р(А/В)=Р(АВ)/Р(В)= Р(В)/ Р(В)=1

Р(А/В)=1

3. Р(А+А^- /В)=Р(Ω/В)=1

Р(А/В)+Р(А^- /В)=1

Р(А/В)=Р(АВ)/Р(В)

Р(АВ)= Р(А/В)* Р(В) если Р(А/В)=Р(А)

Р(АВ)= Р(А)* Р(В) А и В независимые события

3. Р(Ø/А) = Р(Ø А)/Р(А)=Р(Ø)/Р(А)=0

4. Р(А/А) = 1 из 2-го св-ва

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

Теорема: Вероятность события А, которое может наступить лишь при условии появления одного из несовместных событий В₁, В₂,…..В_n, образующих полную группу, равна сумме произведений вероятностей каждого из этих событий на соответствующую условную условную вероятность события А:

Р(А)=Р(В₁)Р(А/В₁)+Р(В₂)Р(А/В₂)+…..+Р(В_n)Р(А/В_n)

Р(А)= ∑ⁿ _i=1 Р(В_i)Р(А/В_i)

Док-во

По условию событии А может наступить, если наступит одно из несовместных событий В₁,В₂…Пользуясь для вычисления вероятности события А теоремой сложения, получим

Р(А)=Р(В₁А)+Р(В₂А)+….Р(В_nА)

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

Р(В₁А)=Р(В₁)Р(А/В₁)

Р(В₂А)=Р(В₂)Р(А/В₂)подставим правые части этих неравенств в соотношение, получим полную формулу вероятности Р(А)=Р(В₁)Р(А/В₁)+Р(В₂)Р(А/В₂)+…..+Р(В_n)Р(А/В_n)

формула и теорема Байеса.

Рассмотрим А и В

Р(А)≠0

Р(В) ≠0

Р(А/В)=Р(АВ)/Р(А) (1)

Р(В/А)=Р(ВА)/Р(А) (2)

Из (1) Р(АВ)=Р(В)Р(А/В)

Из (2) Р(АВ)=Р(А)Р(В/А)

Р(В)Р(А/В)= Р(А)Р(В/А) отсюда Р(А/В) = (Р(А)Р(В/А))/Р(В) – формула Байеса

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

Ω = А₁+А₂+….А_n в формулу Байеса подставляем А→А_i

Р(А_i/В) = (Р(А_i)Р(В/А_i))/Р(В)

Р(В)=Р(А₁)Р(В/А₁)+…+Р(А_n) Р(В/А_n)=∑ⁿ_i=1Р(А_i) Р(В/А_i)

Р(А_i/В) = (Р(А_i)Р(В/А_i))/Р(В))/( ∑ⁿ_i=1Р(А_i) Р(В/А_i)) – теорема Байеса

Аксиомы теории вероятностей

1. каждому событию А поставлено в соответствие неотрицательное действительное число Р(А). это число называется вероятностью события А

2. вероятность достоверного события равна 1 Р(Ω)=1

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

Частота случайного события и его вероятность

Относительная частота наряду с вероятностью принадлежит к основным понятиям теории вероятностей

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

А=m/n где m- число появлений события n- общее число испытаний.

Сопоставляя определения вероятности и относительной частоты, заключаем: определение вероятности не требует, чтобы испытания производились в действительности; определение же относительной частоты предполагает, что испытания были произведены фактически. Другими словами. Вероятность вычисляют до опыта, а относительную частоту – после опыта. Свойство состоит в том, что в различных опытах относительная частота изменяется мало (тем меньше, чем больше произведено испытаний), колеблясь около некоторого постоянного числа. Оказалось, что постоянное число есть вероятность появления события

Дискретные случайные величины. Определение и свойства

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

Числовые характеристики дискретной случайной величины

К числу числовых характеристик относится математическое ожидание. Мат.ожидание приближено равно среднему значению случайной величины. Мат.ожидание дискретной случайной величины называют сумму произведений всех ее возможных значений на их вероятности. Пусть случайная величина Х может принимать только значения х₁,х₂,…,х_n, вероятности соотвественно равны р₁,р₂,…р_n. Тогда мат.ожидание М(Х) случайной величины Х определяется равенством М(Х)=х₁р₁+х₂р₂+…+х_nр_n

М(Х)=∑^∞_i=1x_ip_i

св-ва мат.ожидания

1) Мат. ожидание постоянной величины равно самой постоянной: М(С)=С.

2) Постоянный множитель можно выносить за знак мат. ожидания: М (СХ)=СМ (Х).

3) Мат. ожидание произведения взаимно независимых С.В. равно произведению мат. ожиданий сомножителей: М (Х₁,Х₂…Х_n)=M(X₁)*M(X₂)…M(Xn).

4) Мат. ожидание суммы С.В. равно сумме мат. ожиданий слагаемых: М (Х₁+Х₂+Х₃+…+Х_n)=M(X₁)+M(X₂)+M(X₃)+…+M(X_n).

дисперсией дискретной случайной величины называют мат.ожидание квадрата отклонения случайной величины от ее математического ожидания D(X)=M[X-M(X)]²

D(X)=M[X-M(X)]²=[x₁-M(X)]²p₁+[x₂-M(X)]²p₂+…+[x_n-M(X)]²p_n

Св-ва дисперсии:

1) Д. постоянной равна нулю: D(C)=0.

2) Постоянный множитель можно выносить за знак Д., предварительно возведя его в квадрат: D (CX)=C*2D(X).

3) Д. суммы независимых С.В. равна сумме Д. слагаемых: D (X₁+X₂+…+X_n) =D(X₁)+D(X₂)+…+D(X_n).