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 - 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 - 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 - 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ć.

METODY PRZELICZANIA OBIEKTÓW KOMBINATORYCZNYCH:

1. Prawo mnożenia

Niech A₁,A₂,...,A_n będą skończonymi zbiorami.

Liczba ciągów (a₁,a₂,...,a_n), gdzie a_i
A_i, i = 1,2,...,n wynosi:

|A₁|·|A₂|·...·|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₁, A₂, … , 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₁ do A_n :

3. Ogólne prawo mnożenia

Jeżeli pewna procedura może być rozbita na n kolejnych kroków, z r₁ wynikami w pierwszym kroku, r₂ wynikami w drugim kroku, ..., r_n wynikami w n - tym kroku, to w całej procedurze mamy r₁·r₂·...·r_n łącznych wyników (rozumianych jako uporządkowane ciągi wyników cząstkowych).

4. I wzór V₅ (czyt. „fał pinć”) obliczający wszystkie dotychczasowe wzory wartości zmiennych jakie poznałeś. : )
   

REKURENCYJNA FUNKCJA 2-PARAMETRYCZNA

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.
dla B = f(A)

Zasada bijekcji: niech A i B będą skończonymi zbiorami. Jeżeli istnieje bijekcja f (przepis)
to | A| = | B|

DWUMIAN NEWTONA

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) =

Gdy n = m

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:

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.

Zdarzeniem ­- nazywamy dowolny podzbiór przestrzeni zdarzeń.

Prawdopodobieństwem (funkcją prawdopodobieństwa) nazywamy funkcję
spełniającą następujące warunki:

1)
(skończona przestrzeń zdarzeń)

2)

(ilość zdarzeń elementarnych w przestrzeni, liczebność
)

Jeżeli w
mamy zdarzenia jednakowo prawdopodobne to

Klasyczna definicja:
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.)
Dowód:

b.)
Dowód:

c.)
Dowód:

d.)

Dowód:

e.)

Dowód:

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:
.

Zdarzenia A i B nazwiemy niezależnymi, gdy
.

REKURENCJA

Do uzupełnienia.

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

Niech D(n) oznacza liczbę nieporządków rzędu „n” :

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:

TWIERDZENIE I WZÓR SYLWESTRA

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 :
.

Można powiedzieć, że dystrybuanta akumuluje wartości rozkładu prawdopodobieństwa
.

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ę:

WŁASNOŚCI WARTOŚCI OCZEKIWANEJ WRAZ Z DOWODAMI:

Dowód:

Dowód:

Dowód:

Dowód:

Dowód:

Wartość oczekiwana wyznaczana za pomocą rozkładu prawdopodobieństwa ma postać:

Dowód:

INNE TWIERDZENIA:

Niech

będzie funkcją określoną dla zmiennych losowych X i Y.

Wtedy

Dla zmiennych losowych X, Y i funkcji f określonej jak powyżej zachodzi:

Wniosek:

Wariancją zmiennej losowej X nazwiemy liczbę:

Odchyleniem standardowym nazwiemy liczbę:

Wariancja zmiennej losowej X jest równa:

Odchylenie standardowe:

DOWÓD:

Własności wariancji:

1)
Dowód:

2)
Dowód:

3) Dla niezależnych zmiennych losowych:

Dowód:

ROZKŁAD Poissona

Twierdzenie Poissona:

Niech
.

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
,
,
, wtedy:

STANDARYZACJA ZMIENNEJ LOSOWEJ

Standaryzacja klasyczna zmiennej losowej X polega na przekształceniu zmiennej losowej y według wzoru:

Ustandaryzowana zmienna X , otrzymana zmienna losowa T ma rozkład o wartości oczekiwanej równej 0 i odchyleniem standardowym równym 1.

FUNKCJA f GĘSTOŚCI ZMIENNEJ LOSOWEJ X

1)

2) f jest niewymierna

ROZKŁAD NORMALNY

CENTRALNE TWIERDZENIE GRANICZNE

Załóżmy, że mamy dany ciąg niezależnych zmiennych losowych
o jednakowym rozkładzie i zmienną losową
.

Wtedy
gdzie
i
to charakterystyki zmiennych losowych
.

Wniosek:

Dla rozkładu dwumianowego załóżmy, że X ma rozkład
Wtedy
dla
. (
i
)

GRAFY

Grafem nieskierowanym G nazywamy trójkę
, gdzie:

- jest niepustym zbiorem wierzchołków grafu G

- jest niepustym zbiorem krawędzi

- jest to funkcja działająca na krawędziach przypisującym im pary z punktu P

zaś
jest funkcją incydencji grafu G.

Grafem skierowanym G (diagrafem) nazywamy trójkę
, gdzie:

- jest niepustym zbiorem wierzchołków grafu G

- jest niepustym zbiorem krawędzi

- jest to funkcja działająca na krawędziach przypisującym im pary z punktu P

.

W grafie G o krawędzi takiej, że
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
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
nazywamy wielokrotnymi jeśli
.

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
spełniający zależność:

Mówimy, że droga ta ma długość n. Jeżeli
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
o długości co najmniej 1 nazywamy cyklem, jeśli wszystkie wierzchołki
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
.

Macierzą sąsiedztwa grafu G o n wierzchołkach
nazywamy macierz
, której każdy wyraz
jest liczbą krawędzi od wierzchołka
do
.

Macierz kwadratowa
jest symetryczna

MNOŻENIE MACIERZY

Dla dowolnego grafu G o n wierzchołkach
ilość dróg o długości P z wierzchołka
do
jest równa elementom
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ę
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.)

b.)

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

II TWIERDZENIA EULERA

Graf spójny o dokładnie 2 wierzchołkach stopnia nieparzystego lub bez wierzchołków stopnia nieparzystego nazywamy cyklem Eulera.

- 4 -

---