- 1 -
MATEMATYKA DYSKRETNA – MATERIAŁ DO EGZAMINU
Część I
Kombinatoryka – zajmuje się zbiorami skończonymi z pewną relacją
STRUKTURY:
Permutacją bez powtórzeń na zbiorze Z
n
nazywamy każdy ciąg utworzony z wszystkich
elementów zbioru Z
n.
|P
n
| = n !
Wariacją bez powtórzeń na zbiorze Z
n
nazywamy każdy ciąg k - elementowy (k < n )
utworzony z części elementów zbioru Z
n
tak, że w tym ciągu elementy nie powtarzają się.
!
|
|
(
)!
k
n
n
V
n k
k – ilość el. ciągu; n – ilość el. zbioru ;
K - elementową kombinacją bez powtórzeń na zbiorze Z
n
nazywamy każdy k –
elementowy (k < n ) podzbiór zbioru Z
n.
_
_
!
|
| ( )
(
)! !
k el podzbioru
n
n el zbioru
k
n
C
n k k
K - elementową wariację z powtórzeniami na zbiorze Z
n
nazywamy każdy ciąg złożony z k
elementów zbioru Z
n
tak, że elementy te mogą się powtarzać.
_
_
|
|
k el ciągu
k
n el zbioru
W
n
K – elementową kombinację z powtórzeniami ze zbioru Z
n
nazywamy każdy pseudo zbiór
k – elementowy (k < n; k = n; k > n) złożony z elementów zbioru Z
n
tak, że elementy te mogą
się powtarzać.
_
1
1
_
1
(
1)!
|
| (
) (
)
(
1)! !
k el podzbioru
n k
n k
n el zbioru
n
k
n k
K
n
k
METODY PRZELICZANIA OBIEKTÓW KOMBINATORYCZNYCH:
1. Prawo mnożenia
Niech A
1
,A
2
,...,A
n
będą skończonymi zbiorami.
Liczba ciągów (a
1
,a
2
,...,a
n
), gdzie a
i
A
i
, i = 1,2,...,n wynosi:
|A
1
|·|A
2
|·...·|A
n
W szczególności, liczba uporządkowanych par (a,b), gdzie a
A natomiast b B wynosi:
|A|·|B|
2. Prawo dodawania
Niech zbiory A
1
, A
2
, … , A
n
są skończone i parami rozłączne (tzn. A
i
A
j
=
przy i j )
Moc sumy tych zbiorów, gdzie sumowanie odbywa się od A
1
do A
n
:
1
1
|
|
|
|
n
n
i
i
i
i
A
A
3. Ogólne prawo mnożenia
Jeżeli pewna procedura może być rozbita na n kolejnych kroków, z r
1
wynikami w
pierwszym kroku, r
2
wynikami w drugim kroku, ..., r
n
wynikami w n - tym kroku, to w całej
procedurze mamy r
1
·r
2
·...·r
n
łącznych wyników (rozumianych jako uporządkowane ciągi
wyników cząstkowych).
4. I wzór V
5
(czyt. „fał pinć”) obliczający wszystkie dotychczasowe wzory wartości
zmiennych jakie poznałeś. : )
3
5
(1000000 )!
.
V
REKURENCYJNA FUNKCJA 2-PARAMETRYCZNA
( , )
(
1, )
( ,
1)
f n k
f n
k
f n k
(
1)!
( , )
(
1)! !
n k
f n k
n
k
BIJEKCJA
Bijekcją – nazywamy funkcję różnowartościową, która zbiór A przekształca w zbiór B (dla
której B = f(A) ) tzn. :
f A
B
dla B = f(A)
Zasada bijekcji: niech A i B będą skończonymi zbiorami. Jeżeli istnieje bijekcja f (przepis)
A
B
to | A| = | B|
- 2 -
DWUMIAN NEWTONA
0
1 1
2 2
0
0
1
2
(
)
( )
( )
( )
... ( )
n
n
n
n
n
n
n
n
n
n
a b
a b
a b
a b
a b
0
( )
n
n
n k k
k
k
a b
UOGÓLNIONY WZÓR NEWTONA
INDUKCJA MATEMATYCZNA
Twierdzenie o indukcji
Jeżeli pewna teza T(n) n
N
+
[równanie, nierówność, zdanie] jest prawdziwa dla n=1
oraz z 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
+
.
Dowód indukcyjny – jest postępowaniem wykonywanym według następującego schematu:
1. Wykazanie tezy dla n=1 (dla najmniejszego z możliwych n)
2. Założenie indukcyjne: Zakładam prawdziwość tezy dla dowolnego n
Teza indukcyjna:
Twierdzę, że teza ta jest prawdziwa dla n+1
3. Wykazuję prawdziwość tezy indukcyjnej z punkty 2 T w oparciu o założenie
indukcyjne w punkcie 2 Z i inne znane przekształcenia, twierdzenia.
4. W oparciu o twierdzenie o indukcji udowodniona teza jest prawdziwa dla wszystkich
N
+
(bądź ewentualnie od któregoś n)
SERIĄ CIĄGÓW BINARNYCH
- nazywamy maksymalny podciąg kolejnych jednakowych elementów.
Funkcja dominacji (n, m) =
1
(
)
1
n m
m
m
n
m
Gdy n = m
2
1
( , )
( )
1
n
n
d n m
n
LICZBY CATALANA
- szczególny ciąg liczbowy, mający zastosowanie w różnych aspektach kombinatoryki.
Każdy n-ty wyraz ciągu określony jest wzorem jawnym:
Rekurencyjnie ciąg jest określony w następujący sposób:
Początkowe wartości ciągu, poczynając od wyrazu zerowego, to:
1, 1, 2, 5, 14, 42, 132, 429
RÓWNANIA REKURENCYJNE
Przykłady.
PODZBIORY BEZ SĄSIADÓW
Przykłady.
CIĄG FIBONACCIEGO
- ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:
- 3 -
Część II
Zdarzeniem elementarnym
nazywamy każdy możliwy wynik przeprowadzonego
doświadczenia losowego.
Przestrzenią zdarzeń
pewnego doświadczenia losowego nazywamy zbiór wszystkich
możliwych wyników tego doświadczenia.
1
2,
{ ,
..., }
n
w w
w
Zdarzeniem – nazywamy dowolny podzbiór przestrzeni zdarzeń.
Prawdopodobieństwem (funkcją prawdopodobieństwa) nazywamy funkcję *
[0,1]
P
spełniającą następujące warunki:
1) ( ) 1
P
(skończona przestrzeń zdarzeń)
2)
0
(
)
( )
( )
E F
P E F
P E
P F
1
2
1
2
( )
( ,
,...,
)
( )
(
) ...
( )
n
n
P
P w w
w
P w
P w
P w
1
( )
i
P w
n
(ilość zdarzeń elementarnych w przestrzeni, liczebność )
Jeżeli w
mamy zdarzenia jednakowo prawdopodobne to
1...
1
( )
n
i
P w
Klasyczna definicja:
( )
A
A
P A
przy założeniu skończoności
i tego, że składa się ona
ze zdarzeń jednakowo prawdopodobnych.
TWIERDZENIA I ICH DOWODY
Niech P będzie prawdopodobieństwem na skończonej
.
a.) ( ) 0
P
Dowód: ( )
(
)
( )
( ) 0
P
P
P
P
b.) ( ) 1
( )
P A
P A
Dowód:
1
( )
(
)
( )
( )
( ) 1
( )
P
P A
A
P A
P A
P A
P A
c.) ( \ )
( )
(
)
P A B
P A
P A B
Dowód:
( )
( \ )
(
)
( \ )
(
)
( \ )
( )
(
)
P A
P A B
P A B
P A B
P A B
P A B
P A
P A B
d.) (
)
( )
( )
(
)
P A B
P A
P B
P A B
Dowód:
(
)
(( \ )
)
( \ )
( )
( )
(
)
( )
P A B
P A B
B
P A B
P B
P A
P A B
P B
e.)
1
2
1
(
...
)
( )
n
n
i
i
P A
A
A
P A
Dowód:
1
2
1
2
3
1
2
3
4
1
2
1
(
...
)
( )
(
...
)
( )
( )
(
...
)
( )
( ) ...
( )
( )
n
n
n
n
n
i
i
P A
A
A
P A
P A
A
A
P A
P A
P A
A
A
P A
P A
P A
P A
Prawdopodobieństwem warunkowym P(A|B) nazywamy prawdopodobieństwo zajścia
zdarzenia A pod warunkiem zajścia zdarzenia B, przy założeniu, że P(B) > 0 Określamy
wzorem:
(
)
( | )
( )
P A B
P A B
P B
.
- 4 -
Zdarzenia A i B nazwiemy niezależnymi, gdy ( | )
( )
P A B
P A
.
REKURENCJA
Do uzupełnienia.
Nieporządkiem nazywamy permutację bez punktów stałych.
Niech D(n) oznacza liczbę nieporządków rzędu „n” :
1
2
(
1)(
)
n
n
n
D
n
D
D
0
( 1)
!
!
i
n
n
i
D
n
i
1
*
( 1)
n
n
n
D
n P
LICZBY BELL ’A
Niech B(n) będzie liczbą wszystkich przedziałów zbioru n – elementowego na rozłączne i
niepuste podzbiory, których kolejność nie jest ważna:
1
0
( )
n
n
n
j
j
i
B
B
TWIERDZENIE I WZÓR SYLWESTRA
|
| | | | | |
|
A B
A
B
A B
|
| | | | | | | |
| |
| |
| |
|
A B C
A
B
C
A B
A C
B C
A B C
1
1
2
1
1
|
...
|
( 1)
n
n
k
n
i
n
k
k
i
A
A
A
A
S
[ ]
|
|
k
n
k
I n
i I
S
i
A
Zbiór A nazwiemy przeliczalnym jeśli jest on skończony lub równoliczny ze zbiorem
liczb naturalnych.
Zmienna losowa X jest dyskretna inaczej skokowa, wtedy i tylko wtedy, gdy zbiór
wartości X(
) jest zbiorem przeliczalnym.
Dystrybuantą zmiennej losowej X nazwiemy funkcję określoną na zbiorze liczb R taką, że :
( )
(
)
x
F k
P x k
.
Można powiedzieć, że dystrybuanta akumuluje wartości rozkładu
prawdopodobieństwa
( )
( )
x
x
x k
F k
f x
.
Własności dystrybuanty:
funkcja rosnąca od <0,1>
jest prawostronnie ciągła
przyjmuje wartości [0,1]
Wartością oczekiwaną (średnią) zmiennej losowej X nazwiemy liczbę:
( )
( )* ({ })
E X
X
P
WŁASNOŚCI WARTOŚCI OCZEKIWANEJ WRAZ Z DOWODAMI:
(
)
( )
( )
E X Y
E X
E Y
Dowód:
- 5 -
(
)
(
)( ) ({ })
( ( )
( )) ({ })
( ) ({ })
( ) ({ })
( ) ({ })
( ) ({ })
( )
( ).
E X Y
X Y
P
X
Y
P
X
P
Y
P
X
P
Y
P
E X
E Y
1
2
1
(
...
)
( )
n
n
i
i
E X
X
X
E X
Dowód:
1
2
1
2
3
1
2
3
1
2
3
1
(
...
)
(
)
(
(
...
)
(
)
(
)
(
...
)
(
)
(
)
(
) ...
(
)
( )
n
n
n
n
n
i
i
E X
X
X
E X
E X
X
X
E X
E X
E X
X
E X
E X
E X
E X
E X
( * )
* ( )
E a X
a E X
Dowód:
( * )
( * )( ) {( )}
* ( ) {( )}
* ( )
E a X
a X
P
a X
P
a E X
( )
E a
a
Dowód:
( )
*
({ })
*1
E a
a
P
a
a
(
) 0
E X
Dowód:
(
)
(
(
))
( )
(
)
0
E X
E X
E X
E
Wartość oczekiwana wyznaczana za pomocą rozkładu prawdopodobieństwa ma postać:
( )
( )
( )
* (
)
* ( )
x
k X
k X
E X
k P X
k
k f k
Dowód:
{
* ( )
}
x
X
X
( )
( )
( )
( )
( )* ({ })
( )* ({ })
* ({ })
({ })
(
)
x
x
x
x
x
x X
x X
x X
E X
X
P
X
P
X P
x
P
x
P X
x
INNE TWIERDZENIA:
( )
(
)
( )* (
)
k X
E
X
k
P X
k
Niech
1
( ) 2 | ( ) |
i
D G
E G
:
f RxR
R
będzie funkcją określoną dla zmiennych losowych X
i Y.
Wtedy
( , )( )
( ( ), ( ))
f X Y
f X
Y
Dla zmiennych losowych X, Y i funkcji f określonej jak powyżej zachodzi:
( )
( )
( ( , ))
( ,
)
k X
l Y
E f X Y
k l Y l
Wniosek:
( )
( )
( , )
* * (
,
)
k X
l Y
E X Y
k l P X
k Y l
- 6 -
(
)
( )* ( )
E XY
E X
E Y
Wariancją zmiennej losowej X nazwiemy liczbę:
2
2
2
2
( )
( )
( )
(
) (
)
(
)
( )
((
) )
x
k X
k X
V X
k
P X
k
k
f k
E X
Odchyleniem standardowym nazwiemy liczbę:
( )
V x
Wariancja zmiennej losowej X jest równa:
2
2
2
(
)
( )
E X
E X
Odchylenie standardowe:
2
2
(
)
( )
E X
E X
DOWÓD:
Własności wariancji:
1)
2
(
)
( )
V aX
a V X
Dowód:
2) (
)
( )
V X a
V X
Dowód:
3) Dla niezależnych zmiennych losowych:
1
2
1
(
...
)
( )
n
n
i
i
V X
X
X
V X
Dowód:
ROZKŁAD Poissona
( , )
(
)
!
k
X
Poissona k
P X
k
e
k
Twierdzenie Poissona:
Niech lim
n
n
np
.
lim ( ,
, )
( , )
n
n
B n p k
Poisson k
Twierdzenie Poissona daje dobre przybliżenie rozkładu dwumianowego rozkładu Poissona,
gdy n jest duże, p
n
jest małe, a
średnie, tzn gdy
10
p
,
100
n
,
1
*
[
,10]
10
n
n p
,
wtedy:
( ,
, )
( , )
n
B n p k
Poisson k
( )
E X
( )
V X
STANDARYZACJA ZMIENNEJ LOSOWEJ
Standaryzacja klasyczna zmiennej losowej X polega na przekształceniu zmiennej losowej y
według wzoru:
X
T
Ustandaryzowana zmienna X , otrzymana zmienna losowa T ma rozkład o wartości
oczekiwanej równej 0 i odchyleniem standardowym równym 1.
( )
E X
( )
V X
1
1
( )
(
)
(
)
( ( )
) 0
X
E T
E
E X
E X
FUNKCJA f GĘSTOŚCI ZMIENNEJ LOSOWEJ X
1)
( )
1
R
f x dx
2) f jest niewymierna
(
)
( )
b
a
P a X
b
f x dx
- 7 -
ROZKŁAD NORMALNY
2
2
(
)
2
1
( )
2
X
x
f x
e
CENTRALNE TWIERDZENIE GRANICZNE
Załóżmy, że mamy dany ciąg niezależnych zmiennych losowych
1
2,
,
...,
n
x x
x o jednakowym
rozkładzie i zmienną losową
1
2
...
n
n
Z
x
x
x
.
Wtedy
(
,
,
_
)
n
Z
N n
n przy n
gdzie
i
to charakterystyki zmiennych
losowych
1
{ }
n
i i
X
.
Wniosek:
Dla rozkładu dwumianowego załóżmy, że X ma rozkład
( , , )
X
B n p k
Wtedy
( ,
)
X
N np npq
dla
n
. (
p
i
pq
)
GRAFY
Grafem nieskierowanym G nazywamy trójkę
( ( ), ( ), ( ))
G
V G E G
G
, gdzie:
( )
V G - jest niepustym zbiorem wierzchołków grafu G
( )
E G - jest niepustym zbiorem krawędzi
( )
G
- jest to funkcja działająca na krawędziach przypisującym im pary z punktu P
( )
( )
G
E G
P
zaś
{ , }
( )
P
p q
V G
jest funkcją incydencji grafu G.
Grafem skierowanym G (diagrafem) nazywamy trójkę
( ( ), ( ), ( ))
G
V G E G
G
, gdzie:
( )
V G - jest niepustym zbiorem wierzchołków grafu G
( )
E G - jest niepustym zbiorem krawędzi
( )
G
- jest to funkcja działająca na krawędziach przypisującym im pary z punktu P
( )
( )
( )
G
E G
V G
.
W grafie G o krawędzi takiej, że ( ) { , }
e
p q
mówimy, że łączy wierzchołki p i q. (końce
krawędzi e) zaś e – jest incydentną dla wierzchołków p i q.
W diagrafie o krawędzi takiej, że ( ) ( , )
e
p q
mówimy, że jest krawędzią od wierzchołka
p do wierzchołka q ( p – początek krawędzi e ; q – koniec krawędzi e )
Jeżeli p
q to e nazywamy krawędzią zwykłą w przeciwnym wypadku pętlą.
Krawędzie
1
2
e
e
nazywamy wielokrotnymi jeśli
1
2
( )
( )
e
e
.
Graf G nazywamy prostym jeśli nie posiada pętli i krawędzi wielokrotnych.
Wierzchołkiem izolowanym nazwiemy wierzchołek, który nie jest końcem żadnej krawędzi.
Drogą grafu G nazywamy dowolny ciągi krawędzi
1
2
, ,...,
n
e e
e
spełniający zależność:
1
( ) { ,
}
i
i
i
e
x x
Mówimy, że droga ta ma długość n. Jeżeli
1
1
n
x
x
to droga ta jest zamkniętą.
Drogę nazwiemy drogą prostą, jeśli wszystkie krawędzie ją tworzące są różne.
Drogę zamkniętą o ciągu wierzchołków
1
2
1
, ,..., ,
n
x x
x x
o długości co najmniej 1 nazywamy
cyklem, jeśli wszystkie wierzchołki
1
2
, ,...,
n
x x
x
są różne.
Grafem acyklicznym nazywamy graf nie posiadający cykli.
W grafie G mówimy, że wierzchołki P i Q są sąsiednie, jeśli na krawędzi e ( ) { , }
e
P Q
.
- 8 -
Macierzą sąsiedztwa grafu G o n wierzchołkach
1
2
, ,...,
n
v v
v nazywamy macierz
nxm
M
,
której każdy wyraz
ij
M jest liczbą krawędzi od wierzchołka
i
V do
j
V .
Macierz kwadratowa
nxm
M
jest symetryczna
T
M
M
MNOŻENIE MACIERZY
*
nxm
mxk
nxk
A
B
C
1
1
1
m
ij
ll lj
i n
l
j k
C
a b
Dla dowolnego grafu G o n wierzchołkach
1
2
, ,...,
n
v v
v ilość dróg o długości P z wierzchołka
i
V do
j
V jest równa elementom
ij
m macierzy M
P
, gdzie M jest macierzą sąsiedztwa grafu G.
PODGRAF
Uzupełnić.
Stopniem wierzchołka V (deg(V)) nazywamy liczbę dwuwierzchołkowych krawędzi z V
jako jednym z wierzchołków + podwojoną liczbę pętli o wierzchołku V. Liczbę
( )
x
D G
oznaczamy liczbę wierzchołków grafu G stopnia X.
Graf G nazwiemy regularnym jeśli jego wierzchołki będą tego samego stopnia.
Graf G prosty nazywamy pełnym, jeśli 2 każde różne wierzchołki mamy połączone
krawędzią. Graf pełny jest regularnym.
Suma stopni wierzchołków grafu jest 2 razy większa od liczby krawędzi, czyli:
a.)
( )
deg( ) 2 | ( ) |
w V G
w
E G
b.)
1
( ) 2 | ( ) |
i
D G
E G
Dowód: Każda krawędź dodaje 2 do sumy stopni krawędzi E.
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
- 9 -
II TWIERDZENIA EULERA
Graf spójny o dokładnie 2 wierzchołkach stopnia nieparzystego lub bez wierzchołków stopnia
nieparzystego nazywamy cyklem Eulera.