Matematyka Dyskretna cz. II
Ciągi liczbowe, indukcja, rekurencja, równania różnicowe, grafy,
kombinatoryka, funkcje tworzÄ…ce.
Zadania dla studentów informatyki.
Katarzyna Lubnauer
Maria Wolska
CiÄ…gi liczbowe, indukcja matematyczna
1. Oblicz:
a) 5!
10!
b)
7!
(n + 2)!
c)
n!
2. Oblicz:
n
k
a) , n = 1,2,3,4 ,
"3
k =1
2n
b) j, n = 1,2,5,
"
j=n
10
i
c)
"(-1) ,
i=1
3
2
d) ,
"k
k =0
m
e) (2k +1 - 2k ),
"
k =0
5
f)
"(2n +1),
n=1
8
g) j -1),
"(
j=4
m
k +1
h) , m = 1,2,3 .
"
k
k=1
3. Wykaż indukcyjnie, że
n
a) = n, n " N ,,,
"i 1+ n
2
i=1
n
2
b) =
"i (n +1)(2n +1)n, n " N ,
6
i=1
n
c) - 2) = (3n +1)n, n " N ,
"(6i
i=1
2
2n-1
d) +1) = 3n2 , n " N .
"(2i
i=1
4. Wykaż indukcyjnie, że:
a) 11n - 4n jest podzielne przez 7 dla n " N ,
b) 5n - 4n -1 jest podzielne przez 16 dla n " N ,
c) 5n+1 + 2 Å" 3n +1 jest podzielne przez 4 dla n " N ,
d) 8n+2 + 92n+1 jest podzielne przez 73 dla n " N .
5. Wykaż indukcyjnie, że jeżeli płaszczyznę podzielimy skończoną ilością prostych to można
ją pokolorować dwoma kolorami tak aby po obu stronach każdej prostej w każdym punkcie
były różne kolory.
6. Rozważmy zdanie p(n):  n2 + 5n +1 jest liczbą parzystą .
a) Udowodnij, iż z prawdziwości zdania p(k) wynika prawdziwość zdania p(k+1) dla
każdego k naturalnego.
b) Dla jakich n zdanie p(n) jest prawdziwe?
3
Notacja duże  O
7. Znajdz
najmniejsze k naturalne dla którego f (n) = O(nk ):
a) f (n) = 13n2 + 4n - 73
b) f (n) = n2 + n
5
c) f (n) = (n3 + 3)
3
d) f (n) = n6 + n4
e) f (n) = n2 log n
8. Znajdz
najmniejszy z pośród ciągów a:
4 3
1,log2 n,..., n, n, n, n, n log2 n, n n, n2 , n3,...,2n ,3n ,4n ,..., n!, nn ,
spełniający warunek f (n) = O(a(n)) dla :
a) f (n) = 3n n
b) f (n) = n3 log2 n
c) f (n) = 2n+2 + 33n + n3
d) f (n) = log2 n75
20
e) f (n) = (n + 1) n .
4
Rekurencja
1. Udowodnij, że jeżeli s0 = c, sn = asn-1, dla n e" 1, oraz a,c " R+ ,to sn = anc .
2. Podaj wzór jawny dla ciągu s, gdzie s0 = s1 = 1, sn = 4sn-2 dla n e" 2.
3. Wez
my ciÄ…g zdefiniowany rekurencyjnie: s0 = s1 = 1, sn = sn-1 + sn-2 , dla n e" 2 . Znajdz

jego postać jawną korzystając z odpowiedniego twierdzenia.
4. W każdym z poniższych przypadków znajdz
postać jawną ciągu s:
a) s0 = 3, s1 = 3, sn = sn-1 + 2sn-2 dla n e" 2
b) s0 = 2, s1 = -1, sn = - sn-1 + 6sn-2 dla n e" 2
c) s0 = 1, s1 = 8, sn = 4sn-1 - 4sn-2 dla n e" 2
d) s0 = 1, s1 = -3, sn = -2sn-1 + 3sn-2 dla n e" 2
e) s0 = 2 oraz sn = 5sn-1 dla n e" 1
2
5. Definiujemy rekurencyjnie ciÄ…g s0 = 1 i sn+1 = dla n " N .
sn
a) Wypisz kilka pierwszych wyrazów tego ciągu.
b) Jaki jest zbiór wartości ciągu s.
6. Wez
my ciÄ…g (1,4,16,64,256,...).
a) Podaj wzór jawny na n-ty wyraz tego ciągu jeśli a0 = 1.
b) Podaj definicje rekurencyjnÄ… tego ciÄ…gu.
7. Definiujemy rekurencyjnie ciąg za pomocą wzorów
a0 = a1 = 1 oraz an = an-1 + 2an-2 , dlan e" 2 .
a) Znajdz
a6 .
b) Wykaż iż wszystkie elementy tego ciągu są nieparzyste.
5
Równania różnicowe
1. Wielomian ma w punktach x: -1 , 1 , 3 , 5 odpowiednio wartości: 3 , -1 , 19 , 111. Znajdz

ten wielomian stosując wzór interpolacyjny Newtona.
2. Wielomian ma w punktach x: 0 , 1 , 2 , 3 , 4 odpowiednio wartości: 1 , 1 ,17 , 85 , 265 .
Znajdz
ten wielomian stosując wzór interpolacyjny Newtona.
3. Dane są wartości funkcji f(x) dla x: 1 , 2 , 3 , 4 , 5 i wynoszą odpowiednio: 1 , 5 , 9 , 83 ,
115. Oblicz "4 f (1) stosujÄ…c:
a) stosując tablice różnic,
b) stosując wzór na n-tą różnicę.
4. Oblicz "f (x) dla h=1:
a) f (x) = ex
b) f (x) = ex - 3
c) f (x) = 3x
d) f (x) = sin x
e) f (x) = cos x
1
f) f (x) =
x
g) f (x) = x2 - 5x
h) f (x) = x2 - 5x + 2
5. Rozwiąż równania różnicowe dla h=1:
a) "f (x) = ex ,
1 1
öÅ‚
b) "f (x) = 2sin cosëÅ‚ x + ,
ìÅ‚ ÷Å‚
2 2
íÅ‚ Å‚Å‚
c) "f (x) = 2(3x),
1
d) "f (x) = ,
x(x +1)
1
e) "f (x) = x + ,
2
f) "f (x) = 4x + 3.
SporzÄ…dz
wykresy funkcji f dla warunków początkowych:
6
a) "f (x) = ex , f (0) = 0 ,
1 1
öÅ‚
b) "f (x) = 2sin cosëÅ‚ x + , f ( ) = 3 ,
ìÅ‚ ÷Å‚
2 2
íÅ‚ Å‚Å‚
c) "f (x) = 2(3x), f (1) = 0 ,
1
d) "f (x) = , f (2) = 1,5,
x(x +1)
1
e) "f (x) = x + , f (2) = 5 ,
2
f) "f (x) = 4x + 3, f (0) = 4 .
6. Rozwiąż równania różnicowe dla h=1:
x +1
ëÅ‚ln öÅ‚
a) "f (x) = ex + ex(e -1)ln(x +1),
ìÅ‚ ÷Å‚
x
íÅ‚ Å‚Å‚
x x+1
b) "f (x) = x2a (a -1)+ (2x -1)a ,
c) "f (x) = 2(3x)+ 3(4x).
Wsk. Skorzystaj z wzoru na "( f (x)g(x)).
7. Rozwiąż równanie różnicowe liniowe jednorodne:
"f (x)+ f (x)(1- e) = 0 .
8. Rozwiąż równanie różnicowe liniowe jednorodne:
1
"f (x)- f (x) = 0 .
1+ x
Znajdz
rozwiązanie szczegółowe dla warunku początkowego: f (0) = 3.
9. Rozwiąż równanie różnicowe liniowe jednorodne:
1
"f (x)+ f (x) = 0 .
2 + x
Znajdz
rozwiązanie szczegółowe dla warunku początkowego: f (0) = 2 .
10. Rozwiąż równanie różnicowe liniowenie jednorodne:
1
"f (x)+ f (x) = x .
2 + x
Znajdz
rozwiązanie szczegółowe dla warunku początkowego: f (0) = 0 .
7
Grafy
1. Podaj opis grafu i tabelę funkcji ł dla następujących grafów skierowanych:
2. Narysuj graf skierowany posiadający zbiór wierzchołków V(G) i zbiór krawędzi E(G),
którego funkcja ł dana jest tabelą:
a) V(G) = {w, x, y, z}, E(G) = {a,b,c, d,e, f , g}
k a b c d e f g
(x,w) (w,x) (x,x) (w,z) (w,y) (w,z) (z,y)
Å‚ (k)
b) V(G) = {w, x, y, z}, E(G) = {a,b,c,d,e, f , g,h}
k a b c d e f g h
(x,x) (w,x) (x,w) (w,w) (z,y) (y,z) (z,z) (y,y)
Å‚ (k)
c) V(G) = {w, x, y, z}, E(G) = {a,b,c,d,e, f , g,h,i, j, k,l}
s a b c d e f g h i j k l
(x,y) (y,x) (w,x) (w,z) (z,w) (x,w) (z,x) (x,z) (y,z) (z,y) (y,w) (w,y)
Å‚ (s)
3. Dla grafów G1,G2 ,G3,G4 znajdz
2
a) drogi długości 4 prowadzące od wierzchołka x do y,
b) drogi długości 4 prowadzące od wierzchołka y do w
c) drogi długości 5 prowadzące od wierzchołka x do z.
8
4. Narysuj grafy relacji R1, R2 , R3 gdzie S = {1,2,3,4} oraz niech Ri relacja w zbiorze S
określona następująco:
a) (x, y)" R1 Ô! x + y d" 5
b) (x, y)" R2 Ô! x + y = 4
c) (x, y)" R3 Ô! x + y jest parzyste
d) (x, y)" R1 Ô! x d" y
5. Dla grafów G1,G2 ,G3,G4 , znajdz
macierze sÄ…siedztwa:
9
6. Dla grafów G1,G2 ,G3,G4 ,z zadania powyżej, korzystając z ich macierzy sąsiedztwa
znajdz
ilość dróg długości 2 oraz 3 pomiędzy wierzchołkami
a) x i y,
b) x i z.
10
Kombinatoryka i zliczanie
8 8 52 52
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
1. Oblicz ìÅ‚
ìÅ‚3÷Å‚,ìÅ‚0÷Å‚,ìÅ‚50÷Å‚,ìÅ‚1 ÷Å‚ .
÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
2. W kolejce do dziekanatu stoi 10 studentów.
a) Na ile sposobów mogą być ustawieni?
b) Na ile sposobów mogą być ustawieni jeśli wiemy że Marek stoi zaraz za Jankiem?
c) Na ile sposobów mogą być ustawieni jeśli wiemy że Marek jest bliżej końca kolejki
niż początku?
3. Niech zbiór A = {1,2,3,4,...,10}, B = {2,4,6,8,...,100}. Policz:
a) Ile jest podzbiorów 4 elementowych zbioru A.
b) Ile jest podzbiorów zbioru A złożonych z 3 liczb parzystych i 2 nieparzystych.
c) Ile jest 4 elementowych podzbiorów zbioru A zawierających co najmniej 2 liczby
parzyste.
d) Ile jest 3 elementowych podzbiorów zbioru A zawierających co najwyżej 1 liczbę
parzystÄ….
e) Ile jest elementów w zbiorze A *" B oraz A× B .
f) Ile jest podzbiorów zbioru A× B .
4. W auli odbywa się zebranie dotyczące wyboru języków przez studentów. Każdy student
musi wybrać co najmniej 1 i nie może wybrać więcej niż 2 języki. 50 studentów chce uczyć się
angielskiego, 25 niemieckiego, 13 francuskiego, a 5 włoskiego. Żaden ze studentów chcących
uczyć się włoskiego nie chce uczyć się innego języka, 15 spośród uczących się angielskiego
chce uczyć się też niemieckiego, a 3 francuskiego. Tylko 1 student zamierza uczyć się
niemieckiego i francuskiego. Ilu studentów przyszło na spotkanie?
5. W grupie1 jest 16 studentów i 20 studentek. Na ile sposobów możemy wybrać z nich
zespół 2 osobowy złożony z 1 studentki i 1 studenta. Na ile sposobów możemy podzielić tę
grupę na zespoły 2 osobowe mające rozwiązać ten sam problem. A na ile sposobów można
grupę podzielić na 6 równolicznych zespołów do zrobienia 6 różnych zadań?
6. W urnie jest 16 ponumerowanych kul niebieskich, 8 ponumerowanych kul zielonych i 4
ponumerowane kule białe. Losujemy z urny 6 kul. Ile możemy uzyskać wyników losowania
a) Składających się z 3 kul zielonych, dwóch niebieskich i 1 białej.
b) Składających się z kul w jednym kolorze.
c) ZawierajÄ…cych co najmniej 4 kule niebieskie
11
d) ZawierajÄ…cych kule we wszystkich kolorach.
7. W alfabecie języka informatycznego B-- jest tylko 5 liter. Co najwyżej ile wyrazów 3
literowych jest w języku B--? Ile jest w nim wszystkich wyrazów nie dłuższych niż 5 liter?
8. Tablica rejestracyjna w samochodzie składa się z 2-3 ustalonych liter zależnych od
miejsca rejestracji pojazdu oraz ciągu 4 losowo wybranych cyfr (0,1,...,9) lub liter łacińskich
(A,B, Z). Ile można samochodów zarejestrować w mieście A
odzi?
9. Ile krawędzi zawiera pełny graf skierowany o 10-ciu wierzchołkach?
10. !2 identycznych kul umieszczamy w 4 szufladach. Ile rozróżnialnych wyników możemy
otrzymać jeśli:
a) nie mamy żadnych ograniczeń?
b) pierwsza szuflada pozostanie pusta?
c) w każdej szufladzie będzie co najmniej 1 kula?
d) w jednej z szuflad będzie co najmniej 7 kul?
e) w każdej szufladzie będą co najmniej 2 kule?
11. n ponumerowanych kul, n e" 4 rozmieszczamy w 3 szufladach na ile sposobów możemy je
rozmieścić jeżeli:
a) nie mamy żadnych ograniczeń,
b) wszystkie kule wpadajÄ… do jednej szuflady,
c) co najmniej jedna szuflada pozostaje pusta,
d) co najmniej dwie szuflady pozostajÄ… puste,
e) do pierwszej szuflady wpadły tylko kule 1,2,3.
12. Ile możemy stworzyć liczb czterocyfrowych:
a) złożonych z samych cyfr nieparzystych?
b) o różnych cyfrach składowych?
c) parzystych?
d) większych od 4999?
13. W I lidze jest 16 zespołów grających każdy z każdym 2 razy w sezonie. Ile odbędzie się
meczy w sezonie?
14. W mieście X o kształcie prostokąta jest k+1 ulic prowadzących z zachodu na wschód i
prowadzących i n+1 ulic prowadzących z północy na południe. Na ile sposobów możemy
przejechać z północno-zachodniego krańca miasta do krańca południowo-wschodniego,
wybieramy zawsze najkrótszą drogę.
15. W trójkącie prostokątnym, przyprostokątne podzielono na k równych części, a przez
punkty podziału przeprowadzono proste prostopadłe do nich (rysunek). Korzystając z
12
powstałej siatki przejdz
z wierzchołka przy kącie prostym do przeciwprostokątnej poruszaj się
tylko w prawo i do góry.. Na ile sposobów możesz to zrobić?
n
n
ëÅ‚ öÅ‚
Wykaż przy okazji równość: 2n = ÷Å‚
"ìÅ‚k Å‚Å‚
ìÅ‚ ÷Å‚
k =0
íÅ‚
16. Na ile sposobów możemy wylosować n kul spośród 2n wśród których jest n
ponumerowanych kul białych i n ponumerowanych kul czarnych. Wykorzystaj ten model do
2
n
2n n
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
wykazania równoÅ›ci: ìÅ‚ ÷Å‚ = ÷Å‚ .
"ìÅ‚
ìÅ‚n ÷Å‚ ìÅ‚k ÷Å‚
k =0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
13
Funkcje tworzÄ…ce
1. Ile podzbiorów zbioru [n]= {1,2,3,...,n} ,wliczając zbiór pusty, nie zawiera sąsiednich
liczb?
2. Niech f(x) będzie wykładniczą funkcją tworzącą ciągu D postaci:
n
n
D1 = 0, Dn = nDn-1 + (-1)
Stosując metodę funkcji tworzących wyznacz postać jawną ciągu Dn .
3. Dla ciągu rekurencyjnego danego układem warunków:
(P) a1 = 1
Å„Å‚
,
òÅ‚
(R) an = 2an-1 +1 n > 1
ół
wypisz kilka pierwszych wyrazów, odgadnij wzór ogólny i wykaż go indukcyjnie.
4. Dla ciągu rekurencyjnego danego układem warunków:
(P) a1 = 1
Å„Å‚
,
òÅ‚
(R) an = 2an-1 +1 n > 1
ół
znajdz
funkcje tworzÄ…cÄ… i przy jej pomocy znajdz
postać jawną ciągu.
5. Dla ciągu rekurencyjnego danego układem warunków:
(P) a1 = 1
Å„Å‚
,
òÅ‚
(R) an = 3an-1 + 2 n > 1
ół
wypisz kilka pierwszych wyrazów, odgadnij wzór ogólny i wykaż go indukcyjnie.
6. Dla ciągu rekurencyjnego danego układem warunków:
(P) a1 = 1
Å„Å‚
,
òÅ‚
(R) an = 3an-1 + 2 n > 1
ół
znajdz
funkcje tworzÄ…cÄ… i przy jej pomocy znajdz
postać jawną ciągu.
14