Matematyka dyskretna (tryb zaoczny)  cz. I
TEORIA GRAFÓW
Z - zbiór liczb całkowitych
Z = {...,-2,-1,0,1,2,...}
Z+ - zbiór liczb całkowitych dodatnich {1,2,...}
Z- - zbiór liczb całkowitych ujemnych {...,-2,-1}
R - zbiór liczb rzeczywistych
Funkcje całkowitoliczbowe f : R Z
1) Funkcja podłoga ( floor )
= max{n : n " Z '" n d" x}
ðÅ‚xûÅ‚
= 2
ðÅ‚2ûÅ‚
= 1
ðÅ‚1.75ûÅ‚
= -3
ðÅ‚- 2.75ûÅ‚
= 2
ðÅ‚eûÅ‚
= -4
ðÅ‚- Ä„ ûÅ‚
2) Funkcja sufit ( ceiling )
= min{n : n " Z '" n e" x}
îÅ‚xÅ‚Å‚
Najmniejsza liczba całkowita, która jest większa bądz
równa x
= 1
îÅ‚0.5Å‚Å‚
= -2
îÅ‚- 2.75Å‚Å‚
= 4
îÅ‚Ä„ Å‚Å‚
jeżeli n " N , to =
ðÅ‚nûÅ‚ îÅ‚nÅ‚Å‚
jeżeli n " N , to = = 1
îÅ‚nÅ‚Å‚ ðÅ‚nûÅ‚
[x] - część całkowita x
[x]=
ðÅ‚xûÅ‚
- `" x
ðÅ‚xûÅ‚ ðÅ‚- ûÅ‚
Własności:
1. x = -
ðÅ‚- ûÅ‚ îÅ‚xÅ‚Å‚
2. 1- x < d" x d" < x +1
ðÅ‚xûÅ‚ îÅ‚xÅ‚Å‚
3. x " R , n " Z
= n Ô! n d" x < n +1
ðÅ‚xûÅ‚
4. = n Ô! x -1 < n < x
ðÅ‚xûÅ‚
5. = n Ô! n -1 < x d" n
îÅ‚xÅ‚Å‚
6. = n Ô! x d" n < x +1
îÅ‚xÅ‚Å‚
7. + n = + n n " Z
ðÅ‚x ûÅ‚ ðÅ‚xûÅ‚
8. + n = + n n " Z
îÅ‚x Å‚Å‚ îÅ‚xÅ‚Å‚
= + 3 = 2 + 3 = 5
ðÅ‚e + 3ûÅ‚ ðÅ‚eûÅ‚
= 2 + = 2 - 3 = -1
îÅ‚2 - Ä„ Å‚Å‚ îÅ‚- Ä„ Å‚Å‚
= -3
îÅ‚- Ä„ Å‚Å‚
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
1
Matematyka dyskretna (tryb zaoczny)  cz. I
Niech x, y " R
+
ðÅ‚x + yûÅ‚ ðÅ‚xûÅ‚ ðÅ‚yûÅ‚
= = 3
ðÅ‚1.45 +1.95ûÅ‚ ðÅ‚3.40ûÅ‚
+ = 1+1 = 2
ðÅ‚1.45ûÅ‚ ðÅ‚1.95ûÅ‚
--
Mantysa liczby, część ułamkowa
{x}= m(x) = x -
ðÅ‚xûÅ‚
0 d" {x}< 1
x = + {x}
ðÅ‚xûÅ‚
np.
{3.25}= 3.25 - = 3.25 - 3 = 0.25
ðÅ‚3.25ûÅ‚
{- 3.25}= -3.25 - 3.25 = -3.25 - (- 4) = 0.75
ðÅ‚- ûÅ‚
Przykłady zastosowań:
m
n " N+ - długość słowa w zapisie dwójkowym
10 2
1 1 m = 1
2 10 m = 2
m = n +1 = (n +1)Å‚Å‚
3 11 m = 3
ðÅ‚log ûÅ‚ îÅ‚log
2 2
4 100 m = 3 n = 8 m = ? = 4
+1 = +1 = 4
5 101 m = 3
ðÅ‚log 8ûÅ‚ ðÅ‚3ûÅ‚
2
=
6 110 m = 3
ðÅ‚log 8ûÅ‚ ðÅ‚log 23ûÅ‚= ðÅ‚3log 2ûÅ‚
2 2 2
(8 = 4
7 111 m = 3
îÅ‚log +1)Å‚Å‚ = îÅ‚3.1699Å‚Å‚
2
n = 32000 m = ?
+1 = +1 = 14 +1 = 15
ðÅ‚log 32000ûÅ‚ ðÅ‚14.9658...ûÅ‚
2
f : R R funkcja rosnąca określona na liczbach rzeczywistych
x1 < x2 Ò! f (x1) < f (x2 )
f (x)ûÅ‚ = f (ðÅ‚x )ûÅ‚
ðÅ‚ ðÅ‚ ûÅ‚
f (x)Å‚Å‚ = f (îÅ‚x )Å‚Å‚
îÅ‚ îÅ‚ Å‚Å‚
np.
x > 0
f (x) = x
4.75 4 = 2
ðÅ‚ ûÅ‚= ðÅ‚ ðÅ‚4.75ûÅ‚ûÅ‚= ðÅ‚ ûÅ‚= ðÅ‚2ûÅ‚
15.99 16 = 4
îÅ‚ Å‚Å‚= îÅ‚ îÅ‚15.99Å‚Å‚Å‚Å‚= îÅ‚ Å‚Å‚= îÅ‚4Å‚Å‚
10.24 10
ðÅ‚ ûÅ‚= ðÅ‚ ðÅ‚10.24ûÅ‚ûÅ‚= ðÅ‚ ûÅ‚= 3
--
Liczby Kuuth a
Liczby zdefiniowane wzorem rekurencyjnym
k0 = 1
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
2
Matematyka dyskretna (tryb zaoczny)  cz. I
ëÅ‚ öÅ‚
kn+1 = 1+ minìÅ‚2 Å" kïÅ‚ n śł ,3Å" kïÅ‚ n śł ÷Å‚
ìÅ‚ ÷Å‚
ïÅ‚ śł ïÅ‚ śł
2 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
k2 = k1+1 = 1+ minìÅ‚2 Å" kïÅ‚ 1 śł ,3Å" kïÅ‚1 śł ÷Å‚ = 1+ min(2 Å" k0 ,3Å" k0 ) = 1+ 2 = 3
ìÅ‚ ÷Å‚
ïÅ‚ śł ïÅ‚ śł
2 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
k3 = k2+1 = 1+ minìÅ‚2 Å" kïÅ‚ 2 śł ,3Å" kïÅ‚ 2 śł ÷Å‚ = 1+ min(2 Å" k1,3Å" k0 ) = 1+ 3 = 4
ìÅ‚ ÷Å‚
ïÅ‚ śł ïÅ‚ śł
2 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
k1 = k0+1 = 1+ minìÅ‚2 Å" kïÅ‚ 0 śł ,3Å" kïÅ‚ 0 śł ÷Å‚ = 1+ min(2 Å" k0 ,3Å" k0 ) = 1+ 2 = 3
ìÅ‚ ÷Å‚
ïÅ‚ śł ïÅ‚ śł
2 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
íÅ‚ Å‚Å‚
n, m " Z
n n
îÅ‚ Å‚Å‚ îÅ‚ -1 n - 2 n
Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ - (m -1)
Å‚Å‚
+ + + ... + = n
ïÅ‚mśł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
m m m
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
np. n = 18 m = 4 m składników
18 18
îÅ‚ Å‚Å‚ îÅ‚ -1 18 - 2 18 - 3
Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
+ + + = Å" 5 + + + = 5 + 5 + 4 + 4 = 18
îÅ‚4 Å‚Å‚ îÅ‚4.25Å‚Å‚ îÅ‚4Å‚Å‚ îÅ‚3.75Å‚Å‚
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
4 4 4 4
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
--
S  zbiór liczbowy
S × S - produkt kartezjaÅ„ski dwóch zbiorów
A , B - zbiory
A× B = {(a,b): a " A,b " B}
S × S = {(a,b): a " S,b " S}
R ‚" S × S
Relacja binarna = dowolny podzbiór produktu kartezjańskiego
(a,b)" R = aRb
element a jest w relacji binarnej R z elementem b
--
Relacja kongruencji (relacja przystawania) mod p , gdzie p " Z
(m - n) jest wielokrotnoÅ›ciÄ… liczby p, tzn. że istnieje liczba k taka, że (m - n) = k Å" p
m a" n(mod p)
p = 6
m = 33
n = 15
33 a" 15(mod 6)?
18 = 3Å" 6
k p
(m - n) = k Å" p
(33 -15) = k Å" 6
18 = k Å" 6
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
3
Matematyka dyskretna (tryb zaoczny)  cz. I
18
k = = 3
6
Te dwie liczby (33, 15) przystajÄ… do siebie mod 6
33 a" 12(mod 7)? tak
33 a" 40(mod 7)? tak
33 a" 19(mod 7)? tak
Dwie liczby przystajÄ… do siebie, jeżeli istnieje takie k, że (m - n) = k Å" p (m a" n(mod p))
Liczba m przystaje do liczby n mod p , jeżeli obie te liczby są podzielne przez p (mają taką
samÄ… resztÄ™ z dzielenia)
r  reszta z dzielenia
m = k Å" p + r
p > r e" 0
0 d" r < p
m = 17 m = -17
p = 3 p = 3
17 = 5 Å" 3 + 2 -17 = -6 Å" 3 +1
n = j Å" p + r
m - n = k Å" p + r - ( j Å" p + r) = k Å" p + j Å" p = (k - j)Å" p
(m - n) = k Å" p załóżmy, że m = l Å" p + r1 n = j Å" p + r2
m - n = (l - j)Å" p + (r1 - r2 )
r1 - r2 = 0
r1 = r2
0 d" r1 < p
0 d" r2 < p
- p < r1 - r2 < p
Podstawowe własności relacji przystawania
1.
m " Z p " Z p > 1
üÅ‚
własności zwrotności
żł
m a" m(mod p)
þÅ‚
m jest w relacji przystawania z samym sobÄ…
2. Jeżeli m a" n(mod p), to n a" m(mod p) - własność symetrii
33 a" 15(mod 6)
13 - 33 = k Å" 6
33 -15 = k Å" 6
-18 = k Å" 6
18 = k Å" 6
18
18
- = k
= k
6
6
k = -3
k = 3
3. Jeżeli m a" n(mod p) oraz n a" s(mod p), to wówczas m a" s(mod p) - własność
przechodniości
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
4
Matematyka dyskretna (tryb zaoczny)  cz. I
np.
33 a" 15(mod 6) 15 a" 9(mod 6) 33 a" 9(mod 6)
33 -15 = k Å" 6 15 - 9 = k Å" 6 33 - 9 = k Å" 6
18 = k Å" 6 6 = k Å" 6 24 = k Å" 6
18 6 24
= k = k = k
6 6 6
k = 3 k = 1 k = 4
Każda relacja, która jest zwrotna, symetryczna i przechodnia jest relacją równoważności.
--
x " S
[x] - zbiór wszystkich elementów zbioru S, które są w relacji R z elementem x.
(R  relacja równoważności)
x, y " S
[x] [y] albo [x]= [y] albo [x]'" [y] = 0
[x] = {m : x a" n(mod p)}
p
p  ilość klas
0 d" r d" 1
np.
p = 2
0 - (-4) = 4 = 2 Å" 2
[0] = {...,-4,-2,0,2,4,...}
2
2 - (-4) = 6 = 3Å" 2
[2] = {...,-4,-2,0,4,6,...}
2
[4] = {...,-4,-2,0,4,6,...}
2
[4] - klasa wyznaczona przez 4, gdzie p = 2
2
[0] = [2] = [4] = ... - zbiór liczb parzystych
2 2 2
[1] = [3] = [5] = ... - zbiór liczb rzeczywistych
2 2 2
p = 3 [ ]
3
r = 0
{...,-9,-6,-3,0,3,6,9,...}
r = 1 {...,-8,-5,-2,1,4,7,10,...}
r = 2 {...,-7,-4,-1,2,5,8,11,...}
[& ]
f (n) = O(g(n)) Ô! istnieje C > 0 takie, że f (n) = C Å" g(n) dla dost. dużych wartoÅ›ci n
3) Jeżeli f (n) = O(a(n)) i g(n) = O(b(n))Ò! f (n)Å" g(n) = O(a(n)Å" b(n))
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
5
Matematyka dyskretna (tryb zaoczny)  cz. I
Istnieje takie C, że f (n) d" C Å" a(n)
Istnieje takie D, że g(n) d" D Å" a(n)
f (n)Å" g(n) = f (n)Å" g(n) d" C Å" a(n) Å" D Å" b(n) = C Å" D Å" a(n) Å" b(n) = E Å" a(n)Å" b(n)
f (n)Å" g(n) d" E Å" a(n)Å" b(n)
f (n)Å" g(n) = O(a(n)Å" b(n))
4) Jeżeli O(a(n))+ O(b(n)) = O(max(a(n), b(n)))
f (n) = O(a(n)) to znaczy, że istnieje takie C, że f (n) d" C Å" a(n)
g(n) = O(b(n)) to znaczy, że istnieje takie D, że g(n) d" D Å" a(n)
f (n)+ g(n) d" f (n) + g(n) d" C Å" a(n) + D Å" g(n) d"
d" C Å" max{a(n), b(n)}+ D Å" max{a(n),b(n)}= (C + D)Å" max{a(n), b(n)}
a(n) d" max{a(n), b(n)}
b(n) d" max{a(n),(b(n))}
f (n)+ g(n) = O(max{a(n), b(n)})
f (n) = O(a(n)) g(n) = O(b(n))
5) O(a(n)) = O(b(n)) = O(a(n)Å" b(n))
2 2
Jeżeli a(n) = b(n) to [O(a(n))] = O([a(n)] )
2
np. O(n2)= [O(n)]
--
Notacja &!
f (n) = &!(g(n)) Ô! gdy istnieje takie C, że f (n) e" C Å" g(n) dla dostatecznie dużych n
1
f (n) d" C Å" g(n) :
2
1
g(n) d" Å" f (n) = D Å" f (n)
C
g(n) d" D Å" f (n) Ò! g(n) = O( f (n))
f (n) = &!(g(n)) Ô! g(n) = O( f (n))
--
Notacja Åš (teta)
f (n) = Åš(g(n)) Ô! f (n) = O(g(n)) oraz f (n) = &!(g(n))
Jeżeli np. g(n) = 1 to istnieje C > 0 takie, że f (n) d" C Å" g(n) = C
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
6
Matematyka dyskretna (tryb zaoczny)  cz. I
Istnieje D > 0 takie, że f (n) e" D Å" g(n) = D
--
Własność o
f (n) = o(g(n)) Ô! dla każdego µ > 0 istnieje n0 zależne od µ takie, że dla każdego n > n0
f (n) d" µ Å" g(n)
f (n) , gdy n "
0
( f (n) dąży do 0, gdy n dąży do " )
1 10 1 1
µ = d" Å" Å"100n2
10 n2 100 4
--
Liczby pierwsze
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41
nk
n =
"Pk
k
2 = 21 Å" 30 Å" 50 Å" 70 Å"...
4 = 22 Å" 30 Å" 50 Å" 70 Å"...
6 = 21 Å" 31 Å"50 Å" 70 Å"...
Każdą liczbę można tak przedstawić
min(mk ,nk )
NWD(m, n) = największy wspólny dzielnik
"Pk
k
Ile jest liczb pierwszych?
Dowód: załóżmy, że jest skończona ilość liczb pierwszych (k)
2,3,5,..., Pk
M = 2 Å" 3Å"...Å" Pk +1
M nie dzieli siÄ™ przez 2
M nie dzieli siÄ™ przez 3
&
M nie dzieli siÄ™ przez Pk
Co to znaczy? Albo M jest liczbą pierwszą (większą od Pk ), czyli nieprawda, że Pk jest
ostatnią liczbą pierwszą, albo istnieje liczba P > Pk , która jest liczbą pierwszą i jest
dzielnikiem liczby M.
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
7
Matematyka dyskretna (tryb zaoczny)  cz. I
--
Liczby Euklidesa (e)
e1 = 1+1 = 2 - liczba pierwsza
e2 = 2 +1 = 3 - liczba pierwsza
(5 nie jest liczbÄ… Euklidesa)
e3 = e1 Å" e2 +1 = 7 - liczba pierwsza
e4 = e1 Å" e2 Å" e3 +1 = 43 - liczba pierwsza
e5 = e1 Å" e2 Å" e3 Å" e4 +1 = 2 Å" 3Å" 7 Å" 43 +1 = 1807 - nie liczba pierwsza
1807 = 13Å"139 (13 i 139 to liczby pierwsze)
e6 = e1 Å" e2 Å" e3 Å" e4 Å" e5 +1 = 3263443 - liczba pierwsza
e7 = 10650056950807 = 547 Å" 607 Å"1033Å" 31051 (547, 607, 1033 i 31051 to liczby
pierwsze)
Zbadano dotychczas do e17 (wszystkie do e17 sÄ… liczbami pierwszymi)
E = 1.264
1
ïÅ‚E 2n + śł
= an
ïÅ‚
2śł
ðÅ‚ ûÅ‚
5 5
ïÅ‚E 21 śł ïÅ‚1.2642 + śł
n = 1 + = = = = 2 = a1
ðÅ‚1.5977696 + 0.5ûÅ‚ ðÅ‚2.097696ûÅ‚
ïÅ‚
10śł ïÅ‚ 10śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2
4
n = 2 1.2642 + 0.5 = = 3 = a2
ðÅ‚ ûÅ‚ ðÅ‚1.264 + 0.5ûÅ‚= ðÅ‚3.0526...ûÅ‚
n
Istnieje P takie, że n-ta liczba pierwsza jest postaci Pn = P2
ðÅ‚ ûÅ‚
P  n-ta liczba pierwsza
Pn
1) lim = 1
x"
n Å" ln n
2) Ą(x) - ilość liczb pierwszych nieprzekraczających liczby x
Ä„(x)
lim = 1
x"
x
ln x
3 x 1
3) ln x - < < ln x - Å"Ä„(x) x e" 67
2 Ä„(x) 2
ëÅ‚ln x - 3 1
öÅ‚ ëÅ‚ln öÅ‚
Å"Ä„(x) < x < x - ÷Å‚
Å"Ä„(x)
ìÅ‚ ÷Å‚ ìÅ‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
x x
< Ä„(x) <
1 3
ln x - ln x -
2 2
np.
x = 67 ile jest liczb pierwszych < 67?
3 67 1
ln 67 - < < ln 67 -
2 Ä„(67) 2
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
8
Matematyka dyskretna (tryb zaoczny)  cz. I
67 1
2.705 < < 3.705 Å"
Ä„(67) 67
67
< Ä„(67) < 24.769
2.705
Ä„(67) = 19
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
19 20
x = 80 ile jest liczb pierwszych < 80?
Ä„(80) = 22
80 80
< Ä„(x) <
1 3
ln80 - ln80 -
2 2
20.618 < Ä„(x) < 27.759
20.618 < 22 < 27.759
n-ta liczba pierwsza:
3 1
ëÅ‚ln öÅ‚ ëÅ‚ln öÅ‚
n Å" (n)+ ln(ln(n))- ÷Å‚ ìÅ‚
< Pn < n Å" (n)+ ln(ln(n))- ÷Å‚
n > 20
ìÅ‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
np. dla n = 20 :
3 1
ëÅ‚ln öÅ‚ ëÅ‚ln öÅ‚
20 Å" (20)+ ln(ln(20))- ÷Å‚ ìÅ‚
< P20 < (20)+ ln(ln(20))- ÷Å‚
ìÅ‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3 1
ëÅ‚H" öÅ‚ ëÅ‚3 öÅ‚
20 Å" 3 + ln(3)- ÷Å‚ ìÅ‚
< P20 < 20 Å" + ln(3)- ÷Å‚
ln(3) H" 1.0986 H" 1.1
ìÅ‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ëÅ‚4.1- 3
öÅ‚ ëÅ‚4.1- 1
öÅ‚
20 Å" < P20 < 20 Å"
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
20 Å" 2.6 < P20 < 20 Å" 3.6
32 < P20 < 72
Setna liczba pierwsza:
3 1
ëÅ‚ln öÅ‚ öÅ‚
100 Å" (100)+ ln(ln(100))- ÷Å‚ ìÅ‚
< P100 < 100 Å"ëÅ‚ln(100)+ ln(ln(100))- ÷Å‚
ìÅ‚
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
463.236 < P100 < 563.23
--
Liczby względnie pierwsze:
m n = m jest względnie pierwsze w stosunku do n
Jeżeli NWD(m, n) = 1
mk nk
m = n = dla każdego k min(mk , nk ) = 0
"Pk "Pk
k k
Drzewo liczb względnie pierwszych
Mediant ułamków, np.
2 2
m m m + m
, mediantem tych ułamków nazywamy (mediant `" suma ułamków)
2 2
n n n + n
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
9
Matematyka dyskretna (tryb zaoczny)  cz. I
Jeżeli dwie liczby są względnie pierwsze to&
m n Ò! NWW(m, n) = m Å" n
NWW  największa wspólna wielokrotność
Własności m n:
a a" b(mod m Å" n) Ô! [a a" b(mod m) oraz a a" b(mod n)]
a a" b(mod n) - istnieje k takie, że (a - b) = k Å" n
a a" b(mod m) Ô! (a mod n) = (b mod n)
mod = reszta z dzielenia
np.
101mod 4 = 1
201mod 4 = 1
101mod 25 = 1
201mod 25 = 1
101 a" 201(mod 4)
101 a" 201(mod 25)
101 a" 201(mod(4 Å" 25)) 101 a" 201(mod100)
a a" b(mod m Å" n) Ô! [a a" b(mod m)'" a a" b(mod n)]
Mamy liczbę m. Ile jest liczb n, które są mniejsze od m oraz są względnie pierwsze od n (m
n) (ile jest ułamków nieskracalnych)?
TocjentÕ(n) f (n) = liczba Eulera
- f (1) = 1
- jeżeli p jest liczbą rzeczywistą, to f (p) = p -1
- jeżeli m nie jest liczbą pierwszą (jest liczbą złożoną), to f (m) < m -1
--
Własności funkcji Eulera
1. Jeżeli P jest liczbą pierwszą, a k > 1, to f (Pk )= Pk - Pk -1
2. Jeżeli m da siÄ™ przedstawić w postaci m1 Å" m2 , przy czym m1 jest wzglÄ™dnie pierwsze
w stosunku do m2 , to f (m) = f (m1)Å" f (m2 )
m = m1 Å" m2 m1 m2 f (m) = f (m1)Å" f (m2 )
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
10
Matematyka dyskretna (tryb zaoczny)  cz. I
f (m) jest odpowiedzią na postawione wcześniej pytanie.
np.
f (2) = 2 -1 = 1 1 < 2
1 2
f (3) = 3 -1 = 2 1,2 < 3 , - nieskracalne ułamki
3 3
1 3
f (4) = f (22)= 22 - 21 = 4 - 2 = 2 ,
4 4
f (5) = 5 -1 = 4
1 5
f (6) = f (2 Å" 3) = f (2)Å" f (3) = 1Å" 2 = 2 ,
6 6
f (20) = f (4 Å" 5) = f (4)Å" f (5) = f (22)Å" f (5) = 2 Å" 4 = 8
n = f (d)
"
d
n
n=12
Dzielniki: d = 1,2,3,4,6,12
d = 1 f (d) = 1
d = 2 f (2) = 1
d = 3 f (3) = 2 2 z 3 w mianowniku
d = 4 f (4) = 2 2 z 4 w mianowniku
d = 6 f (6) = 2
d = 12 f (12) = f (22 Å" 3)= f (4)Å" f (3) = 4
1+1+2+2+2+4=12
Spr.:
0 1 2 3 4 5 6 7 8 9 10 11
12 12 12 12 12 12 12 12 12 12 12 12
0 1 1 1 1 5 1 7 2 3 5 11
12 12 6 4 3 12 2 12 3 4 6 12
d = 1 d = 2
--
Liczby Fibonacci ego
def .
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 n e" 2
F2 = F1 + F0 = 1+ 0 = 1
F3 = 1+1 = 2
F4 = 2 +1 = 3
F5 = 3 + 2 = 5
F6 = 5 + 3 = 8
F7 = 8 + 5 = 13
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
11
Matematyka dyskretna (tryb zaoczny)  cz. I
F8 = 13 + 8 = 21
F9 = 21+13 = 34
Własności:
2
1. Jeżeli n > 0, to Fn+1 Å" Fn-1 - (Fn ) = -1n
2 n
Fn+1 Å" Fn-1 - (Fn ) = (-1)
Dowodzenie metodÄ… indukcji matematycznej
1. sprawdzenie wzoru dla najmniejszej wartości n
2. zakładając prawdziwość wzoru dla n = k należy pokazać, że wzór jest prawdziwy dla
wzoru n = k +1
n = 1
2 1
F2 Å" F0 - (F1) = (-1)
1Å" 0 -12 = -1
-1 = -1
L = P
2 n
ZaÅ‚ożenie: Fn+1 Å" Fn-1 - (Fn ) = (-1)
2 k +1
Musimy pokazać, że Fk +2 Å" Fk - (Fk +1) = (-1)
2 k +1
Fk +2 - Fk - (Fk +1) = (-1)
2 2 2
L = Fk +2 Å" Fk - (Fk +1) = Fk +2 Å" Fk - (Fk + Fk -1) = Fk +2 Å" Fk - Fk2 - 2F Å" Fk -1 - (Fk -1) =
2 k
= Fk +2 Å" Fk - (Fk ) - Fk Å" Fk -1 - (Fk + Fk -1)Å" Fk -1 = Fk +2 Å" Fk - Fk2 - Fk Å" Fk -1 -(Fk2 + (-1) )=
2 2 k 2 2 2 k
= (Fk +1 + Fk )Å" Fk - (Fk ) - Fk Å" Fk -1 - (Fk ) - (-1) = Fk +1 Å" Fk + (Fk ) - (Fk ) - Fk Å" Fk -1 - (Fk ) - (-1) =
k k k k +1
= Fk Å"(Fk +1 - Fk -1 - Fk )- (-1) = Fk Å"[Fk +1 - (Fk + Fk -1)]- (-1) = -(-1) = (-1) = P
L = P
n = 6 n = 7
2 6 2 7
F6+1 Å" F6-1 - (F6 ) = (-1) F8 Å" F6 - (F7 ) = (-1)
F7 Å" F5 - 82 = 1 21Å"8 -132 = -1
13Å" 5 - 64 = 1 168 -169 = -1
65 - 64 = 1 -1 = -1
1 = 1 L = P
L = P
Kolejne własności:
2. Dla każdego n i każdego k > 0 , Fn+k = Fk Å" Fn+1 + Fk -1 Å" Fn
k = n F2n = Fn - Fn-1 Å" Fn = Fn Å"(Fn+1 + Fn-1)
n = 4 F8 = F4 Å" F5 + F3 21 = 3Å"(5 + 2) F8 = 7 Å" F4
F3n = Fn+2n = F2n Å" Fn+1 + F2n-1 Å" Fn = Fn Å"(Fn+1 + Fn-1)Å" Fn+1 + F2n-1 - Fn = Fn[(Fn+1 + Fn-1)Å" Fn+1 + F2n-1]
FkÅ"n jest wielokrotnoÅ›ciÄ… Fn
--
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
12
Matematyka dyskretna (tryb zaoczny)  cz. I
Funkcja tworząca dla ciągów liczbowych
a0 , a1, a2 ,..., an - ciÄ…g liczbowy
"
F(Z ) = Å" zi tzw. funkcje tworzÄ…ce dla ciÄ…gów liczbowych
"ai
i=0
Dla jakich z, dla których suma istnieje
ai = 1
1,1,1,...
Jak wyglÄ…da funkcja tworzÄ…ca dla tego ciÄ…gu?
a1
S = S" = q < 1
1- q
"
1
F(z) = zi = 1+ 2 + 22 + 23 + ... = przy założeniu, że z < 1
"1Å"
1- z
i=0
(i)
F - (z)
ai = z = 0
i!
Jak wyglÄ…da taki szereg dla ciÄ…gu Fibonacci ego?
0
F0 = 0 Å" Z F0 = 0
F1 = 1 Å" Z1 F1 Å" Z = Z
2 2 2 2
F2 = F1 + F0 = 1 Å" Z F2 Å" Z = F1 Å" Z + F0 Å" Z
3 3 3 2
F3 = F2 + F1 = 2 Å" Z F3 Å" Z = F2 Å" Z + F1 Å" Z
4 4 4 4
F4 = F3 + F2 = 3 Å" Z F4 Å" Z = F3 Å" Z + F2 Å" Z
5 5 5 5
F5 = F4 + F3 = 5 Å" Z F5 Å" Z = F4 Å" Z + F3 Å" Z
2 3 4
F0 + F1 Å" Z + F2 Å" Z + F3 Å" Z + F4 Å" Z + ... =
2 3 2 2
Z(1+ F1 Å" Z + F2 Å" Z + F3 Å" Z + ...)+ Z (F0 + F1 Å" Z + F2 Å" Z + ...)
2 2
F(Z) = F(1- F0 + F0 + F1 Å" Z + F2 Å" Z + ...)+ Z Å"(F2 )
2
F(Z) = Z + Z Å"F(Z)+ Z Å" F(Z)
1
2
F(Z) = dla z takich, że 1- Z - Z `" 0
2
1- Z - Z
2 2
1- Z - Z = 0 Z + Z -1 = 0 " = 1- 4 Å"(-1) = 5 " = 5
1- 5 1- 5
Z1 = Z2 =
2 2
1+ 5 1- 5
Ta funkcja jest dla Z `" i dla Z `"
2 2
Liczba Ś - liczba  złotego podziału
n
1
Ć
Fn = (Åšn -(Åš) )
5
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
13
Matematyka dyskretna (tryb zaoczny)  cz. I
5 5
ëÅ‚ öÅ‚
5 5
1 (1+ 5) (1- 5) 1
ìÅ‚ ÷Å‚ îÅ‚ Å‚Å‚
F5 = - = Å" (1+ 5) -(1- 5)
ïÅ‚ śł
ìÅ‚
ðÅ‚ ûÅ‚
25 25 ÷Å‚
5 5 Å" 32
íÅ‚ Å‚Å‚
--
n
Dwumian Newtona (pozwala wyliczyć (a + b) )
n
n
n
(a + b) = ìÅ‚ ÷Å‚ Å" ak Å" bn-k
"ëÅ‚ öÅ‚
ìÅ‚k ÷Å‚
k =0
íÅ‚ Å‚Å‚
def . def .
n
ëÅ‚ öÅ‚ n!
Symbol Newtona - ìÅ‚ ÷Å‚ = 0! = 1
ìÅ‚k ÷Å‚
k!Å"(n - k)!
íÅ‚ Å‚Å‚
n
n n n n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
n
(a + b) = ìÅ‚ ÷Å‚ Å" ak Å" bn-k = ìÅ‚ Å" ak Å" bn + ìÅ‚ Å" ak Å" bn-1 + ìÅ‚ ÷Å‚ Å" ak Å" bn-2 + ... + ìÅ‚ Å" ak Å" b0
"ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ ìÅ‚0÷Å‚ ìÅ‚1÷Å‚ ìÅ‚ ìÅ‚n÷Å‚
÷Å‚ ÷Å‚ ÷Å‚
k 2÷Å‚
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
2
n 2 2 2
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
2
(a + b) = ìÅ‚ ÷Å‚ Å" ak Å" bn-k = ìÅ‚ Å" a2 Å" b2 + ìÅ‚ Å" a1 Å" b1 + ìÅ‚ Å" a2 Å" b0 = b2 + 2ab + a2
"ëÅ‚ öÅ‚
ìÅ‚k ÷Å‚ ìÅ‚0÷Å‚ ìÅ‚1÷Å‚ ìÅ‚2÷Å‚
÷Å‚ ÷Å‚ ÷Å‚
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3 3
n 3
3
(a + b) = ìÅ‚ ÷Å‚ Å" ak Å" bn-k = ìÅ‚ ÷Å‚ Å" ak Å" b3-k =
"ëÅ‚ öÅ‚ "ëÅ‚ öÅ‚
ìÅ‚k ÷Å‚ ìÅ‚k ÷Å‚
k =0 k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3 3 3 3
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
= ìÅ‚ Å" a0 Å" b3-0 + ìÅ‚ Å" a1 Å" b3-1 + ìÅ‚ Å" a2 Å" b3-2 + ìÅ‚ Å" a3 Å" b3-3 =
ìÅ‚0÷Å‚ ìÅ‚1÷Å‚ ìÅ‚2÷Å‚ ìÅ‚3÷Å‚
÷Å‚ ÷Å‚ ÷Å‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3! 3! 3! 3!
= Å" a0 Å" b3 + Å" a1 Å" b2 + Å" a2 Å" b1 + Å" a3 Å" b0 =
0!Å"(3 - 0)! 1!(3 -1)! 2!(3 - 2)! 3!(3 - 3)!
3! 3! 3! 3!
= Å" b3 + Å" a Å" b2 + Å" a2 Å" b + Å" a3 = b3 + 3ab2 + 3a2b + a3
1Å" 3! 1Å" 2! 2!Å"1 3!Å"1
5 5
ëÅ‚ öÅ‚
5 5
1 (1+ 5) (1- 5) 1
ìÅ‚ ÷Å‚ îÅ‚ Å‚Å‚
F5 = Å" - = Å" (1+ 5) -(1- 5) =
ïÅ‚ śł
ìÅ‚
ðÅ‚ ûÅ‚
25 25 ÷Å‚
5 5 Å" 32
íÅ‚ Å‚Å‚
1
= Å"
5 Å" 32
îÅ‚ 5 5 5 4 5 3 5 2 5 1 5 0 Å‚Å‚
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
Å" Å"10 Å"(- 5) + ìÅ‚ Å"11 Å"(- 5) + ìÅ‚ Å"12 Å"(- 5) + ìÅ‚ Å"13 Å"(- 5) + ìÅ‚ Å"14 Å"(- 5) + ìÅ‚ Å"15 Å"(- 5) =
ïÅ‚ìÅ‚ ÷Å‚ śł
ìÅ‚0÷Å‚ ìÅ‚1÷Å‚ ìÅ‚2÷Å‚ ìÅ‚3÷Å‚ ìÅ‚4÷Å‚ ìÅ‚5÷Å‚
÷Å‚ ÷Å‚ ÷Å‚ ÷Å‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ðÅ‚ ûÅ‚
îÅ‚ 5 5 5 3 5
1 ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ 1
= Å" Å" ìÅ‚ Å"( 5) + 2 Å" ìÅ‚ Å"12 Å"( 5) + 2 Å" ìÅ‚ Å"14 Å"( 5)Å‚Å‚ = Å"[25 5 + 50 5 + 5 5]=
ïÅ‚2 ìÅ‚0÷Å‚ śł
÷Å‚ ìÅ‚2÷Å‚ ìÅ‚4÷Å‚
÷Å‚ ÷Å‚
5 Å" 32 16 5
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ðÅ‚ ûÅ‚
1 80
= Å"80 5 = = 5
16
16 5
3
( 5) = 5 5
5 2 5
ëÅ‚ öÅ‚ 5! ëÅ‚ öÅ‚ 80 ëÅ‚ öÅ‚ 5!
ìÅ‚ = ìÅ‚ = = 5 ìÅ‚ =
ìÅ‚0÷Å‚ ìÅ‚5÷Å‚ ìÅ‚4÷Å‚
÷Å‚ ÷Å‚ ÷Å‚
0!Å"5! 16 4!Å"1!
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
1
Ć
F20 = Å"(Åš20 - Åš20)= 6765 F45 = 1134903170
5
Dowolna liczba n daje się przedstawić w postaci pewnej sumy liczb Fibonacci ego
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
14
Matematyka dyskretna (tryb zaoczny)  cz. I
n = Fk + Fk + ... + Fk k1 > k2 > ... > kr
1 2 r
1000000 = F30 + F26 + F24 + F12 + F10 = 832040 +121393 + 46368 +144 + 55
n = Å"10k (n) = Å" 2k (bk = 0 lub 1)
"bk 2 "bk
k =0 k =0
n  liczba dziesiętna
n2 - liczba w systemie dwójkowym
m
(n) = Å" Fk bk = 0 lub 1
F "bk
k =2
Fm < n '" Fm+1 > n
(1) = 1
F
(2) = 10
F
(3) = 100
F
(6) = 1Å" F5 +1Å" F2 (m = 5 , bo F5 < 6 '" F6 > 6) = 1001
F
(10)F = 1Å" F6 +1Å" F3 = 10010 m = 6
F6F5F4F3F2
(n)F = bm Å" bm-1 Å"...Å" b2
--
Elementy kombinatoryki (podstawy kombinatoryki):
Mamy n elementów. Permutacja  każde ustawienie n elementów.
n = 1 a
n = 2 ab ba
n = 3 abc acb bac bca cab cba
Ilość permutacji - n!
Permutacje z powtórzeniami (pewne elementy mogą się powtarzać).
n = 3 aab aba baa
n1 - ilość powtórzeń 1 elementu;
n2 - ilość powtórzeń 2 elementu;
&
nk - ilość powtórzeń n-tego elementu.
n  ilość elementów
Kombinacją n elementów po k elementów nazywamy każdy k-elementowy podzbiór, przy
czym dwie kombinacje są sobie równe jeżeli złożone są z tych samych elementów, chociaż
umieszczonych nie na tych samych miejscach.
n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ n!
ìÅ‚ ÷Å‚ - ilość wszystkich kombinacji ìÅ‚ ÷Å‚ =
ìÅ‚k ÷Å‚ ìÅ‚k ÷Å‚
k!Å"(n - k)!
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
15
Matematyka dyskretna (tryb zaoczny)  cz. I
6 z 49 (Duży Lotek)
49
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ = 13983816
ìÅ‚ ÷Å‚
6
íÅ‚ Å‚Å‚
Szansa trafienia  trójki ?
49
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ = 246820
ìÅ‚ ÷Å‚
3
íÅ‚ Å‚Å‚
Podstawowe własności symbolu Newtona:
n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ n! n!
1. ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ = =
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
k n - k (n - k)!Å"[n - (n - k)]! (n - k)!Å"k!
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n
ëÅ‚ -1 n -1 n
öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
2. ìÅ‚ ÷Å‚ + ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚ ìÅ‚
k k -1÷Å‚ ìÅ‚k ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
(n -1)! (n -1)!
+
k!Å"(n -1- k)! (k -1)!Å"[n -1- (k -1)]!
(n -1)! (n -1)! (n -1)! 1 1
ëÅ‚ öÅ‚
= + = Å" + =
ìÅ‚ ÷Å‚
k!Å"(n - k -1)! (k -1)!Å"(n - k)! (k -1)!Å"(n - k -1)! k n - k
íÅ‚ Å‚Å‚
n
/ /
(n -1)! n - k + k n! ëÅ‚ öÅ‚
= Å" = = ìÅ‚ ÷Å‚
ìÅ‚k ÷Å‚
(k -1)!Å"(n - k -1)! k Å"(n - k) k!Å"(n - k)!
íÅ‚ Å‚Å‚
0
ëÅ‚ öÅ‚
ìÅ‚
ìÅ‚0÷Å‚
÷Å‚
íÅ‚ Å‚Å‚
1 1
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ìÅ‚
ìÅ‚0÷Å‚ ìÅ‚1÷Å‚
÷Å‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
2 2 2
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ìÅ‚ ìÅ‚
ìÅ‚0÷Å‚ ìÅ‚2÷Å‚ ìÅ‚2÷Å‚
÷Å‚ ÷Å‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3 3 3 3
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ìÅ‚ ìÅ‚ ìÅ‚
ìÅ‚0÷Å‚ ìÅ‚1÷Å‚ ìÅ‚2÷Å‚ ìÅ‚3÷Å‚
÷Å‚ ÷Å‚ ÷Å‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n
m n
ëÅ‚ öÅ‚ ëÅ‚ -1 n
öÅ‚
- k Å" ìÅ‚ ÷Å‚ = n Å" ìÅ‚ ÷Å‚ Ile wynosi ìÅ‚ ÷Å‚ = 2n ?
"ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ ìÅ‚k -1÷Å‚ ìÅ‚k ÷Å‚
n
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n
n n
ëÅ‚ öÅ‚ ëÅ‚ -1 n
öÅ‚
n
- (n - k)Å" ìÅ‚ ÷Å‚ = n Å" ìÅ‚ ÷Å‚ (a + b) = ìÅ‚ ÷Å‚ Å" ak Å" bn-k
"ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚k ÷Å‚
k k
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
n n
ëÅ‚ öÅ‚ ëÅ‚ -1
n öÅ‚
- ìÅ‚ ÷Å‚ = Å" ìÅ‚ ÷Å‚ a = 1 b = 1
ìÅ‚k ÷Å‚ ìÅ‚k -1÷Å‚
k
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
k
n
n m n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ - k n
öÅ‚
- ìÅ‚ Å" ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚ Å" ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ - przy co drugim zmienia siÄ™ znak
"(-1) Å" ëÅ‚ öÅ‚
ìÅ‚m÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚k ÷Å‚ ìÅ‚m - k ÷Å‚ ìÅ‚k ÷Å‚
÷Å‚
k
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Wyższa Szkoła Komunikacji i Zarządzania w Poznaniu
16