Kombinatoryka zajmuje się zbiorami skończonymi wraz z pełną relacją. Zestawienie zbioru i relacji nazywamy obiektami (strukturami) kombinatorycznymi. Są to np. permutacje, kombinacje, wariacje, grafy, funkcje opisujące.

Kombinatoryka jest częścią matematyki dyskretnej i ma wspólne obszary z algebrą, geometrią, teorią liczb, analizą, rachunkiem prawdopodobieństwa. W kombinatoryce wyróżnić można 3 grupy:

- czy istnieje obiekt o zadanych właściwościach?

- ile jest obiektów o zadanych właściwościach?

- czy można znaleźć obiekt wg zadanych kryteriów?

Współcześnie najważniejsze zastosowanie kombinatoryki to obliczanie prawdopodobieństwa zdarzeń, gdy wszystkie wyniki pewnego eksperymentu są jednakowo prawdopodobne.

Ω - zbiór zdarzeń elementarnych, zbiór skończony.

|Ω| - ilość zdarzeń

A≤Ω - podzbiór zd. element.

P(A)=|A|/|Ω| - prawdopodobieństwo

Permutacja bez powtórzeń – niech dany będzie zbiór Zn złożony z różnych elementów. Permutacją bez powtórzeń na zbiorze Zn nazywamy każdy ciąg utworzony ze wszystkich elementów zbioru Zn (elementy ciągu się nie powtarzają). |P_n|=n!

Wariacja bez powtórzeń - niech dany będzie zbiór Zn złożony z różnych elementów. Wariacją k-elementową bez powtórzeń na zbiorze Zn (k<n) nazywamy każdy ciąg k-elementowy utworzony z części elementów zbioru Zn (tak, że w tym ciągu elementy nie powtarzają się) $\left| V_{n}^{k} \right| = \frac{n!}{(n - k)!}$

Kombinacje bez powtórzeń - niech dany będzie zbiór Zn złożony z różnych elementów. K-elementową kombinacją bez powtórzeń na zbiorze Zn nazywamy każdy k-elementowy podzbiór (k<n) zbioru Zn. $\left| C_{n}^{k} \right| = (_{k}^{n}) = \frac{n!}{k!\left( n - k \right)!}$

Wariacja z powtórzeniami - niech dany będzie zbiór Zn złożony z różnych elementów. K-elementową wariację z powtórzeniami na zbiorze Zn nazywamy każdy ciąg złożony z k-elementów zbioru Zn, tak, że elementy te mogą się powtarzać. |W_n^k| = n^k

Kombinacja z powtórzeniami - niech dany będzie zbiór Zn złożony z różnych elementów. K-elementową kombinacją z powtórzeniami na zbiorze Zn nazywamy każdy pseudozbiór k-elementowy (k<n, k=n, k>n) złożony z elementów zbioru Zn, tak, że elementy te mogą się powtarzać.

$\left| K_{n}^{k} \right| = \frac{\left( n + k - 1 \right)!}{\left( n - 1 \right)!k!} = (_{n - 1}^{n + k - 1}){= (}_{k}^{n + k - 1})$

Prawo mnożenia – niech A₁,A₂,…A_n są skończonymi zbiorami. Liczba ciągów (a₁,a₂,…,a_n), gdzie a_iA_i i liczba tych ciągów dana jest zbiorem |A_i|=|A₁||A₂|…|A_n|

Ciągi binarne złożone są z elementów zbioru Z₂={0,1} albo Z₂={∙,-}

Prawo dodawania – niech zbiory A₁, A₂,…,A_n są skończone i są parami rozłączne. Moc sumy tych zbiorów, gdzie sumarycznie zaczyna się od A₁, a konczy na A_n.

Ogólne prawo mnożenia – jeżeli pewna procedura kombinatoryczna może być rozbita na n kolejnych kroków z wynikami r₁ – I krok, r₂ – II krok,…, r_n – N krok, to w całej procedurze mamy r₁r₂…r_n wyników.

Bijekcją nazywamy funkcję różnowartościową f:A->B dla której B=f(A)

Zasada bijekcji - Niech A i B będą skończonymi zbiorami. Jeżeli istnieje bijekcja f (przepis) przekształcająca A w B to |A|=|B| (liczność A = liczność B)

Różny sposób wybierania (losowania) k elementów ze zbioru n-elementowego Zn. Nazywamy to schematami wyboru. Przed przystąpieniem do losowania trzeba odp na 2 pytania:

1. Czy istotna jest kolejność wylosowanych elementów?

2. Czy wylosowane elementy mogą się powtarzać?

1|T|N|T|N|

2|T|N|N|T|

|W|C|V|K|

Podziały zbiorów – uogólnieniem kombinacji są podziały zbioru na rozłączne podzbiory o zadanych mocach. Na ile sposobów można podzielić zbiór Y na rozłączne podzbiory A₁, A₂,…A_r o mocach odpowiednio…

Dwumian Newtona – (a + b)ⁿ = (_oⁿ)aⁿb⁰ + (₁ⁿ)a^n − 1b¹ + (₂ⁿ)a^n − 2b² + … + (_n − 1ⁿ)a¹b^n − 1 + (_nⁿ)a⁰bⁿ

INDUKCJA MATEMATYCZNA

1. Tw. o indukcji – jeżeli pewna teza T(n) (równanie, nierówność, zdanie) jest prawdziwa dla n=1 oraz założenia jej prawdziwości dla dowolnego n wynika jej prawdziwość dla n+1 to mówimy, że teza T(n) jest prawdziwa dla każdego nЄN⁺.

2. Dowód indukcyjny jest postępowaniem wykonywany wg schematu:

a) wykazanie tezy (równania, nierówności, zdania) dla n=1 (najmniejszej wartości)

b) Z – założenie prawdziwości tezy dla dowolnego n

T – twierdzę, że ta teza jest prawdziwa dla n+1

c) wykazanie prawdziwości tezy indukcyjnej z b) T w oparciu o założenie indukcyjne w punkcie b) z przekształcenia tożsamościowe i inne znane twierdzenia

d) formuła zamykania – w oparciu o tw. o indukcji udowadniana teza jest prawdziwa dla każdej liczby naturalnej.

Nieporządkiem nazywamy permutację bez punktów stałych.

Liczby Bella – Niech Bn będzie liczbą wszystkich podziałów zbioru n-elementowego na rozłączne i niepuste zbiory, których kolejność nie jest ważna.

Serie ciągów binarnych – max ilość ciągów kolejnych jednakowych elementów. 1110011101 Serie 0 i 1 przeplatają się i jest ich tyle samo albo różnią się o 1.

Funkcja d(n,m) (n-1,m-0) to liczba ciągów binarnych, w których dla każdego kroku i=1,2,3,m,n+m na pierwszych pozycjach znajduje się co najmniej tyle 0 co 1. Taki ciąg nazywamy zdominowanym przez 0.

Liczby Catalana – $c_{n} = \frac{1}{n + 1}(_{n}^{2n}) = \frac{\left( 2n \right)!}{\left( n + 1 \right)!n!}$, rekurencyjnie: c₀=1; c_n=c₀c_n-1+c₁c_n-2+…+c_n-2c₁+c_n-1c₀

Zdarzeniem elementarnym ω będziemy nazywać każdy możliwy wynik przeprowadzonego doświadczenia losowego. Ω={ ω₁, ω₂,…, ω_n} – zdarzenia elementarne

Przestrzenią zdarzeń pewnego doświadczenia losowego będziemy nazywać zbiór wszystkich możliwych wyników tego doświadczenia. Ω

Zdarzeniem będziemy nazywać dowolny podzbiór przestrzeni zdarzeń.

Prawdopodobieństwem lub funkcją prawdopodobieństwa nazwiemy funkcję P: Ω->[0,1] spełniającą następujące warunki: 1) P(Ω)=1, 2)$\bigwedge_{E,F\ E \land F \neq 0}^{}{P\left( E \cup F \right) = P\left( E \right) + P(F)}$

P(Ω)=P(ω₁υω₂υω₃υ…υ ω_n)=P(ω₁)υP(ω₂)υ…υP(ω_n)

iЄ{1,2,…,n)

P(ω_i)=1/n, n=|Ω|

Jeżeli w Ω={ ω₁, ω₂,…, ω_n} mamy zdarzenia jednakowo prawdopodobne to $\bigwedge_{i \in \{ 1,2,..n\}}^{}{P\left( \omega_{i} \right) = \frac{1}{\overset{}{\Omega}}}$

Def. klasyczna prawdopodobieństwa: $\bigwedge_{A \subset \Omega}^{}{P\left( A \right) = \frac{|A|}{|\Omega|}}$. Przy założeniu skończoności Ω i z tego, że Ω składa się z zdarzeń jednakowo prawdopodobnych.

Twierdzenia: Niech P będzie prawdopodobieństwem na skończonej Ω.

a) P(ø)=0

b) P(A’)=1-P(A)

c) P(A\B)=P(A)-P(A∩B)

d) P(AυB)=P(A)+P(B)-P(A∩B)

e) P(A₁υA₂υ…υA_n)=$\sum_{i = 1}^{n}{P(A_{i})}$

Def. Niech X będzie niepustym zbiorem. Powiedzmy, że rodzina F podzbioru X stanowi σ – ciało zbioru jeżeli:

1) ø=F

2) AЄF=>A’ЄF

3) $\bigwedge_{A1,A2\text{ϵF}}^{}{A_{1} \cup A_{2}\ldots\text{ϵF}}$

Prawdopodobieństwo na nieskończonym Ω. Niech M będzie σ – ciałem na zbiorze Ω. Wtedy p nazwiemy funkcję P:M→[0,1] spełniającą następujące warunki.

1) P(A)≥0

2) P(Ω)=1

3) $\bigwedge_{\text{Ai},\text{Aj}\ldots\text{ϵM}}^{}{P(\bigcup_{i = 1}^{\infty}{\text{Ai}) = \sum_{i = 1}^{\infty}{P(\text{Ai})}}}$

Prawdopodobieństwem warunkowym P(A|B) (praw. zajścia A pod war. B), przy założeniu P(B)>0, nazwiemy: $P\left( A \middle| B \right) = \frac{P(A \cap B)}{P(B)}$

Zdarzenia A i B nazwiemy niezależnymi gdy P(A|B)=P(A) => $P\left( A \middle| B \right) = \frac{P(A \cap B)}{P(B)} = P(A)$

//-------------

Niech A₁,A₂,…,A_n są pewnymi schematami z Ω. Jeżeli $P(\bigcap_{\text{iϵj}}^{}\text{Ai} = \prod_{I \notin J}^{}{P(\text{Ai})}$ gdzie J to pewien dowolny podzbiór indeksu ze zbioru {1,2,...,n} to zdarzenia A₁,...,A_z są niezależne. Zatem zdarzenia A₁, A₂, A₃ będą niezależne.

P(A₁∩A₂)=P(A₁)∙P(A₂)

P(A₂∩A₃)=P(A₂)∙P(A₃)

P(A₁∩A₃)=P(A₁)∙P(A₃)

P(A₁∩A₂∩A₃)=P(A₁) ∙P(A₂) ∙P(A₃)

Prawdopodobieństwo całkowite. Niech {Ai}_i = 1ⁿ będzie układem zupełnym zdarzeń (tzn. $\bigcup_{i = 1}^{n}\text{Ai} = \Omega \land \bigwedge_{i \neq j}^{}{\text{Ai} \cap \text{Aj} = \varnothing}$) Dla dowolnego zdarzenia B ⊂ Ω. $P\left( B \right) = \sum_{i = 1}^{n}{P\left( \text{Ai} \right) \bullet P(B|\text{Ai})}$

Wzór Bayesa. Niech {Ai}_i = 1ⁿtworzą układ zupełny zdarzeń, wtedy dla dowolnego B ⊂ Ω: $\bigwedge_{i \in n}^{}{P\left( \text{Ai} \middle| B \right) = \frac{P(B|\text{Ai}) \bullet P(\text{Ai})}{P(B)} = \frac{P(B|\text{Ai}) \bullet P(\text{Ai})}{\sum_{i = 1}^{n}{P(B|\text{Ai}) \bullet P(\text{Ai})}}}$

Zmienną losową na przestrzeni Ω nazywamy dowolną funkcję rzeczywistą określoną na Ω. X:Ω→R.

Funkcję f_x, zdefiniowaną na zbiorze R wzorem f_x(x)=P(X=x) dla xЄR nazywamy rozkładem prawdopodobieństwa zmiennej losowej X.

Niezależność dwóch zmiennych. Zmienne losowe X i Y określone na Ω są niezależne P(XЄI i YЄJ)= P(XЄI)∙(YЄJ) dla wszystkich przedziałów I i J z R. Jeśli Ω jest skończona to warunek ten jest równoważny: P(X=x ^ Y=y)=P(X=x)∙P(Y=y) dla dowolnych x,yЄR.

Zmienne losowe X₁,X₂,…,X_n określone na Ω są niezależne P(XiЄJ dla i=1,2,…,n)=$\prod_{i = 1}^{n}{P(Xi \in Ji)}$ dla wszystkich przedziałów J₁,J₂…J_nЄR.

//-------------

Def. Zbiór A nazwiemy przeliczalnym jeśli jest on skończony lub równoliczny ze zbiorem liczb naturalnych.

Def. Zmienna losowa X jest dyskretna (skokowa) X(Ω) jest zbiorem przeliczalnym.

Def. Dystrybuanta zmiennej losowej X nazwiemy funkcję określoną na zbiorze liczb R, taką że F_x(k)=P(X≤k). Można powiedzieć ze dystrybuanta akumuluje wartości rozkładu prawdopodobieństwa. F_x(k)=∑_xЄkf_x(x)

Własności dystrybuanty

- funkcja rosnąca

- przyjmuje wartości z przedziału [0,1]

- prawostronnie ciągła

Def. Wartością oczekiwaną (wartością średnią) zmiennej losowej X nazwiemy liczbę μ=E(X)=∑_ωЄΩX(ω)*P({ω})

Własności wartości oczekiwanej

1. E(X+Y) = E(X)+E(Y)

2. E(X1+X2+…+Xn)=∑ⁿ_i=1E(Xi)

3. E(a*X)=a*E(X)

4. E(a)=a

5. E(X-μ)=0

Dowody:

Ad 1) E(X+Y)=∑_ωЄΩ(X+Y)(ω)*P({ω})=∑_ωЄΩ(X(ω)+Y(ω))P({ω})=∑_ωЄΩ(X(ω)* P({ω})+Y(ω)* P({ω}))=∑_ωЄΩ X(ω)* P({ω})+∑_ωЄΩ Y(ω)* P({ω})=E(X)+E(Y)

Ad 2) E(X1+X2+…+Xn)=E(X1)+E(X2+…+Xn)=E(X1)+E(X2)+E(X3+…+Xn)=∑ⁿ_i=1E(Xi)

Ad 3) E(a*X)= ∑_ωЄΩ(a*X)(ω)*P({ω})=∑_ωЄΩa*X(ω)*P({ω})=a*∑_ωЄΩX(ω)*P({w})=a*E(X)

Ad 4) E(a)= ∑_ωЄΩa*P({ω})=a*∑_ωЄΩ*P({ω})=a*1=a

Ad 5) E(X-μ)=E(X+(-μ))=E(X)+E(-μ)=μ-μ=0

Def. Wartość oczekiwana wyznaczona za pomocą rozkładu prawdopodobieństwa ma postać μ=E(X)=∑_kЄX(Ω)k*P(X=k)=∑_kЄX(Ω)k*f_x(k)

Dowód:

Ωx=(ωЄΩ:X(ω)=x}

E(X)= ∑_ωЄΩX(ω)*P({ω})=∑_xЄX(Ω) ∑_ωЄΩX(ω)*P({ω})=∑_xЄX(Ω) ∑_ωЄΩx*P({ω})=∑_xЄX(Ω)*x* ∑_ωЄΩ*P({ω})= ∑_xЄX(Ω)x*P(X=x)

Twierdzenie. Niech φ:R->R. Dla zmiennej losowej X mamy:

E(φ○X)=∑_kЄX(Ω)φ(k)*P(X=k)

φ○X=φ(X)

X=|k|	3	0	1	2
k	-3	0	1	2
	1/6	1/3	1/3	1/6

E(X)=-3*1/6+0*1/3+1*1/3+2*1/6=-1/2+1/3+1/3=1/6

E(|X|)=3*1/6+0*1/3+1*1/3+2*1/6=1/2+1/3+1/3=7/6

//-------------

Def. Niech φ:RxR→R będzie funkcją określoną dla dwóch zmiennych losowych X i Y wtedy $\bigwedge_{\omega \in \Omega}^{}{\varphi\left( X,Y \right)\left( \omega \right) = \varphi(X\left( \omega \right),Y\left( \omega \right))}$.

Def. Dla zmiennych losowych x,y i funkcji φ określonej jak powyżej zachodzi: $E\left( \varphi\left( X,Y \right) \right) = \sum_{k \in X(\omega)}^{}{\sum_{l \in Y(\omega)}^{}{\varphi\left( k,l \right) \bullet P(X = k\ i\ Y - l)}}$

Tw. Dla niezależnych zmiennych losowych X i Y zachodzi E(X∙Y)=E(X)∙E(Y).

Def. Wariancją zmiennej losowej X nazwiemy liczbę $\sigma^{2} = V\left( x \right) = \sum_{k}^{}{{(k - n)}^{2} \bullet P\left( X = x \right) = \sum_{k \in X(\Omega)}^{}{{(k - n)}^{2} \bullet f_{x}\left( k \right) = E(\left( x - n \right)^{2})}}$
Odchyleniem standardowym nazywamy liczbę: $\sigma = \sqrt{V(x)}$

Wariancja zmiennej losowej x jest równa σ² = E(x²) − (E(x))²

Odchylenie standardowe zmiennej losowej x: $\sigma = \sqrt{E\left( x^{2} \right) - {(E\left( x \right))}^{2}}$

Własności wariancji

1) V(aX)=a²V(x)

2) V(X+a)=V(x)

3) Dla niezależnych zmiennych losowych x₁,x₂,…x_n: $V(x1,x2,\ldots xn) = \sum_{i = 1}^{n}{V(xi)}$

Rozkład zero-jedynkowy

x - ma rozkład zero-jedynkowy; x(Ω)={0,1}; p – prawdopodobieństwo sukcesu; q – prawdopodobieństwo porażki; q=1-p

Rozkład dwumianowy (Bernouliego)

Próby Bernouliego; n – prób; każda z prób kończy się dwoma możliwymi wynikami; p – prawdopodobieństwo sukcesu; q – prawdopodobieństwo porażki; próby są niezależne.

Zmienna losowa X, która jest równa liczbie sukcesów (k) w n próbach Bernouliego ma rozkład dwumianowy X~B(n,p,k). Dla n prób mamy X(Ω)={0,1,…,n}.f_x(k) = (_kⁿ)p^kq^n − k

Dystrybuanta $F_{x}\left( k \right) = \sum_{i \leq k}^{}{(_{l}^{n})p^{l}k^{n - l}}$. X=X₁+X₂+…+X_n.

X­_i – wynik w pojedynczej próbie ma rozkład zero-jedynkowy.

{Xi}_i = 1ⁿ - są niezależne. $E\left( X \right) = E(\sum_{i = 1}^{n}{Xi) =}\sum_{i = 1}^{n}{E\left( x \right) = \sum_{i = 1}^{n}{= p = n \bullet p}}$ $V\left( X \right) = V(\sum_{i = 1}^{n}{Xi) =}\sum_{i = 1}^{n}{V\left( x \right) = \sum_{i = 1}^{n}{= p \bullet q = n \bullet p \bullet q}}$

$$\sigma = \sqrt{n \bullet p \bullet q}$$

P(X=2) + P(X=3) = $C_{3}^{2} \bullet {(\frac{9}{10})}^{2} \bullet \left( \frac{1}{10} \right) + C_{3}^{2} \bullet {(\frac{9}{10})}^{3} \bullet {(\frac{1}{10})}^{0}$

P(X=0)=$\ C_{3}^{0} \bullet {(\frac{9}{10})}^{0} \bullet {(\frac{1}{10})}^{3} = 0,001$

P(X=1)=$\ C_{3}^{1} \bullet {(\frac{9}{10})}^{1} \bullet {(\frac{1}{10})}^{2} = 0,027$
P(X=2)=0,243 P(X=3)=0,729

$F_{x}(X)\left\{ \begin{matrix} 0\ dla\ k < 0 \\ 0,001\ dla\ 0 \leq k < 1 \\ 0,028\ dla\ 1 \leq k < 2 \\ 0,217\ dla\ 2 \leq k \leq 3 \\ 1\ dla\ k > 3 \\ \end{matrix} \right.\ $ P(X≥2)=1-P(X≤1)=1-0,028=0.972

E(X)=n·p=3·0,9=2,7 V(X)=n·p·q=3·0,9·0,1=0,7 σ=$\sqrt{\frac{27}{100}} = 0.52$

Rozkład geometryczny

Pojedyncza próba kończy się sukcesem lub porażką doświadczenie losowe polega na powielaniu prób dopóki nie otrzymamy pierwszego sukcesu.

X – ilość przeprowadzonych prób ma rozkład geometryczny.

X(Ω)={1,2,…}=N; $\bigwedge_{k \in N}^{}{f_{x}\left( k \right) = q^{n - 1}p}$; $F_{x}\left( k \right) = \sum_{l \leq k}^{}{q^{l - 1}p}$; $E\left( x \right) = \frac{1}{p}$; $V\left( x \right) = \frac{q}{p^{2}}$; $\sigma = \sqrt{\frac{q}{p^{2}}}$

Zadanie:
Prawdopodobieństwo połączenia się klienta z serwerem wynosi $\frac{2}{10}$, klient próbuje się połaczyć w 6 sekund. Jakie jest prawdopodobieństwo, że połączy się w ciągu 20s?
X-ilość połączenia z serwerem X-ma rozkład geometryczny o p=0,2
P(X=1)=0,2 P(X=2)=0,8•0,2=0,16 P(X=3)=(0, 8)²•0,2=0,128 P(X=4)=(0, 8)³•0,2=0,1024

P(X=5)=(0, 8)⁴•0,2=0.08192
Dystrybuanta :

$F_{x}(k)\left\{ \begin{matrix} 0\ dla\ k < 1 \\ 0,2\ dla\ 1 \leq k < 2 \\ 0,36\ dla\ 2 \leq k < 3 \\ 0,488\ dla\ 3 \leq k < 4 \\ 0,5094\ dla\ 4 \leq k < 5 \\ \end{matrix} \right.\ $ P(X≤4)= F_x(4) = 0, 5904 E(X)=$\ \frac{1}{0,2}$=5 V(X)=$\ \frac{0,8}{{(0,2)}^{2}}$=20 σ=$\sqrt{20} = 2\sqrt{5}$

Rozkład Poissona

Zmienna losowa X na rozkład Poissona

X ~ Poissona(k,λ)

X(Ω)={0,1,2,3…}
P(X=k)=$\frac{\lambda}{k!}^{k}e^{- \lambda}$

Dystrybuanta F­­x(x)=$\sum_{k \leq x}^{}{\frac{\lambda}{k!}^{k}e^{- \lambda}}$
Twierdzenie Poissona

Niech granica n  • p_n = λ .

Wtedy dla każdego k≥0 zachodzi B(n,p_n,k) = Poissona(k, λ)

Wniosek:

Twierdzenie Poissona daje dobre przybliżenie rozkładu dwumianowego rozkładem Poissona gdy n jest duże, p jest małe a λ średnie tzn. :

$\left\{ \begin{matrix} p \leq 0.1 \\ n \geq 100 \\ \lambda = n\ \bullet p_{n}\ \lbrack 0,1,10\rbrack \\ \end{matrix} \right.\ $ Wtedy rozkład Bernoulliego można przybliżać rozkładem Poissona.

B(n,p_n,k)~ Poissona(k, λ)

1. E(x)= λ

2. V(x) λ

1. Dowód: E(x) = E(x_n) =n  • p_n = λ gdzie X_n ∼ B(n,p_n,k)

2. Dowód: V(x) = V(x_n) =$\operatorname{}{n\ \bullet p_{n} \bullet q_{n}} = \operatorname{}{n\ \bullet p_{n} \bullet (1 -}p_{n}) = \operatorname{}{n\ \bullet p_{n} \bullet (1 -}\frac{\lambda}{n}) = \lambda$

Zadanie:

Każdego roku 1% ubezpieczonych mężczyzn traci życie w określonym rodzaju wypadku. Jakie jest prawdopodobieństwo, że w danym roku ubezpieczyciel będzie musiał wypłacić odszkodowanie więcej niż 3 mężczyznom jeśli ubezpieczono 100 mężczyzn?

Sukces –śmierć mężczyzny

Ilość prób – 100

X-ilość śmierci w grupie 100 mężczyzn K- liczba sukcesów.

X~B(100,$\frac{1}{100}$, k) λ = n  • p = 1 Można przybliżyć rozkładem Poissona

P(X>3)=1-P(X≤3)=$\ \sum_{i = 0}^{3}{\frac{\lambda^{i}}{i!}e^{- \lambda}}$

X~Poisson(k,1)= )=$\ \sum_{i = 0}^{3}{\frac{1^{i}}{i!}e^{- 1} = 1 - \left( 0,981 \right) = 0,019 = 1,9\%}$

Standaryzacja zmiennej losowej

Standaryzacja klasyczne zmiennej losowej X polega na przekształceniu zmiennej losowej według wzoru T=$\frac{x - \mu}{\sigma}$
Otrzymane zmienne losowe T( standaryzacja zmienna losowe X) ma rozkład o wartości oczekiwanej równej 0 i odchyleniu standardowemu równym 1.

E(x)= μ $\sqrt{V\left( x \right)} = \ \sigma$
E(T) =E$\left( \frac{x - \mu}{\sigma} \right)$=$\frac{1}{\sigma}E\left( x - \mu \right) = \frac{1}{\sigma}\left( E\left( x \right) - \mu \right) = 0$

$$\sqrt{V\left( T \right)} = \sqrt{V\left( \frac{x - \mu}{\sigma} \right)} = \sqrt{\frac{1}{\sigma^{2}} \bullet V(x - \mu)} = \sqrt{\frac{1}{\sigma^{2}} \bullet V(x)} = \sqrt{\frac{\sigma^{2}}{\sigma^{2}}} = 1$$

Jeśli ustandaryzujemy zmienną losową X o rozkładzie normalnym to otrzymamy tzw. Zmienną losową unormowaną . U~N(0,1)

Dystrybuantę tej zmiennej losowej oblicza się się literą Ф

Centralne twierdzenie graniczne (tw. Lindberga Levy’ego)

Załóżmy, że mamy dany ciąg niewiadomych zmiennych losowych x­­­­­­­­­­­_­­1 + x₂ aż do x_n wtedy Z_n ~ N(n$\ \mu,\sigma\sqrt{n})$ przy n → ∞ gdzie σ i μ to charakterystyki zmiennych losowych {X_i}=1
Wniosek: Dla rozkładu dwumianowego załóżmy, że x ~ B( n,p,k) wtedy X~N(np, $\sqrt{\text{npq}}$) dla n → ∞ ($\mu = p,\ \ \sigma = \sqrt{\text{pq}}$)

Zadanie:

Prawdopodobieństwo uzyskania wygranej w pewnej grze losowej wynosi 0,1. Jakie jest P, że spośród 500 osób:

a) wygra mniej niż 60 osób; b) wygra mniej niż 20 osób;

a) n=500; p=0,1; q=0,9; X – ilość wygranych; X~B(500;0,1;k); przybliżenie X rozkładem normalnym $X\sim N(500 \bullet 0,1;\sqrt{500 \bullet 0,1 \bullet 0,9})$; X~N(50;6,7); $P\left( X \geq 61 \right) = 1 - P\left( X \leq 60 \right) = 1 - P\left( \frac{x - 50}{6,7} \leq \frac{60 - 50}{6,7} \right) = 1 - P\left( U \leq 1,49 \right) = 1 - \left( 1,49 \right) = 1 - 0,93 = 0,07$

GRAFY

Grafem nieskierowanym G nazywamy uporządkowaną trójkę G=(V(G), E(G),γ(G)) gdzie V(G) jest niepustym zbiorem wierzchołków grafu G, E(G) – niepustym zbiorem krawędzi grafu G, zaś γ(G) funkcje γ(G) : E(G) →p p={ {p,q} , p,q V(G)} jest funkcją incydencji grafu.

Grafem skierowanym (digrafem G) nazywamy uporządkowaną trójkę G=(V(G), E(G),γ(G)) gdzie V(G)=zbiór wierzchołków E(G)- zbiór krawędzi.
γ(G)=E(G) → V(G) x V(G)
W grafie G o krawędzi e γ€ { p,q} mówimy, że łączy wierzchołki p i q. Krawędź e incydentą do wierzchołków p i q.

W grafie G o krawędzi e takiej że γ(e)={p,q} mówimy, że jest krawędzią od wierzchołka p do q.

Drogą grafu G nazywamy dowolny ciąg e₁, e₂, …, e_n spełniający zależność γ(a_i)={x₁, x_i+1} Mówiący, że droga ta ma długość n, jeżeli x₁=x_n+1 nazywamy ją zamkniętą.

Drogę nazywamy drogą prostą jeżeli wszystkie gałęzie je tworzące są różne.

Drogą zamkniętą o ciągu ?wierzchołków? x₁,x₂,…,x_n o długości co najmniej 1 nazywamy cyklem, jeżeli wszystkie wierzchołki są różne. Grafem acyklicznym nazywamy graf nie posiadający cykli.
Macierz sąsiedztwa digrafu G o n-wierzchołkach v₁,v₂,…,v_n nazwiemy macierz ??? n x n której każdy wyraz n i j jest liczbą krawędzi od wierzchołka v_i do […urwane…]
W grafie G mówimy że wierzchołki p i q są sąsiednie jeśli dla pewnej krawędzi e γ(e)={p,q}
Graf spójny w którym każdy wierzchołek ma stopień parzysty ma cykl Eulera
Graf spójny o dokładnie 2 wierzchołkach stopnia nieparzystego lub bez wierzchołków. Stopnie nieparzystego ma drogę Eulera
Drogą Eulera w grafie G nazywamy każdą drogę prostą (bez zamknięcia).
Cyklem Eulera nazywamy każdą drogę prostą i zamkniętą zawierającą wszystkie krawędzie grafu G.
WARUNEK KONIECZNY istnienia cyklu Eulera
Jeżeli graf G ma cykl Eulera to wszystkie jego wierzchołki są stopnia parzystego.
WARUNEK WYSTARCZAJĄCY istnienia cyklu Eulera (TWIERDZENIE EULERA)
Graf spójny, w którym każdy wierzchołek ma stopień parzysty nazywamy cyklem Eulera.
WARUNEK KONIECZNY istnienia drogi Eulera
Jeżeli graf G ma drogę Eulera to ma on albo dokładnie 2 wierzchołki stopnia nieparzystego, albo nie ma w ogóle wierzchołków stopnia parzystego.
Graf G nazwiemy spójnym jeśli każda para różnych wierzchołków jest połączona drogą w tym grafie.
Spójny podgraf, który nie jest zawarty w większym, spójnym podgrafie grafu G nazywamy składową grafu G