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