elementy matematyki dyskretnej dla finansistow

Spis treści

Symbole i oznaczenia.

Wstęp.

Modele algorytmiczne — warunek dopóki.

Indukcja i dowodzenie jednoczesne.

Definicje rekurencyjne.

Ciągi rekurencyjne.

Przeliczanie.

Modele kombinatoryczne.

6.1

Inne problemy kombinatoryczne. . . . . . . . . . . . . . . . . . . . . . . .

Funkcje tworzące.

Grafy.

Izomorfizmy grafów.

10 Własności grafów.

10.1 Drogi a krawędzie. Drogi wewnątrz grafu. . . . . . . . . . . . . . . . . . .

11 Zasada włączania - wyłączania.

12 Zasada Dirichleta.

12.1 Teoretyczne podstawy metody. . . . . . . . . . . . . . . . . . . . . . . . .

12.2 Zastosowanie metody modelowania w zadaniach. . . . . . . . . . . . . . .

13 Równania rekurencyjne.

13.0.1 Renumeracja i przesunięcie o stałą wyrazów ciągu geometrycznego.

13.1 Modelowanie rekurencyjne z wykorzystaniem liczb Fibonacciego. . . . . .

13.1.1 Definicja i własności ciągu liczb Fibonacciego. . . . . . . . . . . . .

13.1.2 Wzór Bineta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13.2 Inne własności ciągu liczb Fibonacciego. . . . . . . . . . . . . . . . . . . .

SPIS TREŚCI

13.2.1 Przykłady zadań rozwiązanych metodą modelowania rekurencyjne-

go z wykorzystaniem liczb Fibonacciego. . . . . . . . . . . . . . . .

13.3 Metoda modelowania rekurencyjnego w zadaniach. . . . . . . . . . . . . .

13.3.1 Zadania z kombinatoryki. . . . . . . . . . . . . . . . . . . . . . . .

13.3.2 Zadania z rachunku prawdopodobieństwa. . . . . . . . . . . . . . .

13.3.3 Zadania algebraiczne.

. . . . . . . . . . . . . . . . . . . . . . . . .

14 Modelowanie okrężne.

15 Zadania.

15.1 Zadania do rozdziałów. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15.1.1 Rozdziały 1–2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15.1.2 Rozdziały 3–4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

100

15.1.3 Rozdział 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

101

15.1.4 Rozdziały 5–6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

104

15.1.5 Rozdziały 7–9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

111

15.1.6 Rozdział 14. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

115

15.2 Zestawy kolokwialne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

116

15.2.1 Zestaw 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

116

15.2.2 Zestaw 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

117

15.2.3 Zestaw 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

119

Symbole i oznaczenia.

i ∈ 1, n ⇔ i ∈ {1, 2, . . . , n}

a | b – a dzieli b

bxc – część całkowita z liczby x

µ(A), |A| – moc (miara) zbioru A

n
k

– symbol Newtona

– kombinacja bez powtórzeń

– kombinacja z powtórzeniami

– wariacja bez powtórzeń

– wariacja z powtórzeniami

– liczba kombinacji bez powtórzeń

– liczba kombinacji z powtórzeniami

– liczba wariacji bez powtórzeń

– liczba wariacji z powtórzeniami

– liczba permutacji

,...,n

– liczba permutacji z powtórzeniami

(A | B) – zdarzenie A pod warunkiem zajścia zdarzenia B.

Symbole i oznaczenia.

Wstęp.

Elementy matematyki dyskretnej dla finansistów adresowane są przede wszystkim do osób
o elementarnym przygotowaniu z analizy matematycznej, algebry i podstaw matematyki.
Mogą to być studenci matematyki finansowej, ekonometrii czy tez ekonomiści specjalizu-
jący się w inżynierii finansowej, teorii ryzyka lub teorii inwestycji.

Taki wybór adresatów przesądził o nietypowym układzie podręcznika. Nie zawiera on

rozbudowanej dla potrzeb informatyków teorii grafów i sieci. Natomiast większy ciężar
kładziony jest na konstrukcje dotyczące modelowania matematycznego, w tym: kombi-
natorycznego, rekurencyjnego, szufladkowego, przeliczeniowego i okrężnego. Dość silnie
są podkreślone także zastosowania i problemy z zakresu rachunku prawdopodobieństwa.
Taki układ został przyjęty ze względu na potrzeby praktyki.

W zagadnieniach inżynierii i matematyki finansowej wyjściowymi badanymi obiektami

są ciągi i szeregi, na przykład ciągi Fibonacciego wykorzystywane w teorii fal Elliota, a
więc obiekty charakterystyczne dla matematyki dyskretnej. Jednakże relacje między nimi
wymagają odpowiedniego do potrzeb opracowania modeli, hierarchizacji, strukturalizacji,
badania n-tych stanów, na przykład przez przeliczanie lub sumowanie. Dotyczy to zarów-
no konstrukcji deterministycznych jak i losowych. Dlatego dość istotnym wydaje się być
aspekt konstruowania modeli probabilistycznych — fundamentalnych dla analizy z zakre-
su finansów — oczywiście ograniczono się tu przede wszystkim do prawdopodobieństwa
klasycznego w oparciu o konstrukcje przestrzeni dyskretnych.

W niektórych problemach istotne jest także wyznaczanie granic analizowanych ciągów

i szeregów. Jednakże narzucające się tutaj naturalne przejście do metod analizy matema-
tycznej nie wydaje się niezbędne. Techniki badania granic (np. ciągów rekurencyjnych)
są typowym elementem wykładu analizy matematycznej i nie zostały szerzej włączone do
niniejszego podręcznika.

Zasygnalizowane tu zostały jedynie niektóre bardziej zaawansowane techniki modelo-

wania kombinatorycznego, bez rozwinięcia metod analizy kombinatorycznej.

Konstrukcją spinającą, którą przyjąłem dla „przyjaznego” przejścia do metod anali-

tycznych, jest badanie funkcji tworzących. Są to swoiste generatory, które w oparciu o
źródłowe ciągi pozwalają na zastosowanie technik analizy funkcji do zintergowanych wiel-
kości pomocniczych, jakimi są właśnie funkcje tworzące. Również to podejście zawiera
elementy modelowania okrężnego, szczególnie wtedy, gdy poszukujemy pewnych charak-
terystyk parametrycznych badanego modelu, na przykład chcemy wyznaczyć wartości
przeciętne czy miarę zmienności danego skwantyfikowanego procesu. Dlatego ostatni roz-
dział części teoretycznej w zasadzie mógłby być traktowany jako dotatek. Jednakże, ze
względu na jego szczególną rolę, został ujęty jako zamykający wykład.

Do podręcznika dołączone są także przykładowe zadania w układzie uporządkowanym

stosownie do kolejnych działów wykładu oraz zestawy zadań kolokwialnych.

Wstęp.

Zarówno konstrukcja merytoryczna podręcznika jak i dobór zadań oparte są o wiele ist-

niejących podręczników i zbiorów. Przykładowo, struktura merytoryczna analizowanych
problemów wybrane przykłady i techniki dowodzenia w rozdziałach: 1, 2, 7, 8, 9 były
wzorowane na klasycznej monografii [1]. Jednakże wiele problemów i zadań ma charakter
autorski. Dotyczy to również ogólnej koncepcji i formalizacji modelowania matematycz-
nego.

Rozdział 1

Modele algorytmiczne —
warunek dopóki. ([1])

Wykłady dotyczą ciągów: zdań logicznych, kroków algorytmu, wartości elementów. Chce-
my, by przechodząc od elementu ciągu do następnego, zawsze przy zachowaniu założeń
otrzymać poprawne wyniki.

Zaczniemy od analizy modułu algorytmu dopóki, dopóki zachodzi w którym jest po-

wtarzany zdefiniowany krok tak długo jak zachodzi wyrózniony warunek dopóki.

Twierdzenie 1.1 ∀m ∈ N

∀n ∈ N ∃q ∈ N

∃r ∈ 0, n − 1

m = qn + r

Dowód. Udowodnimy to twierdzenie, wykorzystując pętlę dopóki, wyznaczając warto-

ści q i r.

Konstrukcja werbalna algorytmu:

1. Dla ustalonych m i n zgadujemy parę wartości q i r, takich że zachodzi m = qn + r.

2. Poprawiamy krok po kroku te wartości zachowując prawdziwość warunku m =

qn + r, kończąc poprawianie gry r ∈ 0, n − 1

Konstrukcję można rozpocząć przyjmując na przykład q = 0 i r = m. O ile m > n

to para (q, r) nie spełnia założenia r ∈ 0, n − 1, natomiast już w tej konstrukcji, na
początku równość m = qn + r pozostaje prawdziwa i będzie taka, gdy zwiększymy q o 1
i zmniejszymy r o n. Powtarzając tę procedurę qn + r = (q + 1)n + (r − n) powinniśmy
otrzymać r ∈ 0, n − 1.

Algorytm dzielenia (całkowitoliczbowego).

Wejście { Dane: m ∈ N

n ∈ N }

Wyjście { Wyniki: q ∈ N

r ∈ 0, n − 1 takie, że qn + r = m }

Wygodniej zapisać q, r ∈ N

qn + r = m ∧ r < n.

Początek inicjujący algorytm:

q:=0
r:=m

Zasadnicza część, pętla:

ROZDZIAŁ 1. Modele algorytmiczne — warunek dopóki.

DOPÓKI r>=n WYKONUJ
q:=q+1
r:=r-n
KONIEC

Rysunek 1.1: Schemat blokowy algorytmu.

Ogólna postać pętli, dopóki g wykonuj S:

Sprawdź, czy warunek g jest prawdziwy. Jeśli g jest prawdziwy, to wykonaj komplet

instrukcji opisany przez S i wróć do sprawdzenia g, w przeciwnym przypadku przejdź do
nowej instrukcji za pętlą.

Zdefiniujmy kilka pojęć:

Warunek g jest zdaniem w sensie logiki, nazywamy go warunkiem dozoru pętli.

S jest ciągiem kroków nazywanym treścią pętli. S może zmieniać wartość logiczną g
(tzw. pętle warunkowe formalnie zawierają warunek — na przykład wartość liczby
kroków).

Wykonanie kroków S w pętli nazywamy przebiegiem pętli lub iteracją. Pętla kończy
się, gdy warunek dozoru g nie jest spełniony i kontynuacja działania następuje poza
pętlą.

DOPÓKI A niepusty WYKONUJ
wybierz x z A
usun x z A

A może być na przykład zbiorem krawędzi grafu, czy wierzchołków sympleksu. Jeśli

A < ℵ

to wykonywanie pętli się zakończy po odrzuceniu wszystkich wierzchołków, jeśli

A jest co najmniej przeliczalny, to wykonywanie pętli się nie zakończy.

W tabeli zobrazujemy wyniki kolejnych pętli dla dzielenia m = 28 n = 9. Algorytm nie

wchodzi w pętlę dopóki po raz czwarty bo warunek dozoru nie jest spełniony po trzecim
przebiegu.

Nasuwają się następujące pytania:

numer iteracji

r n

prawda

fałsz

Tabela 1.1:

1. Czy algorytm zatrzyma się po jakimś czasie?

2. Czy kiedy już się zatrzyma, to otrzymane wyniki są poprawne?

Na pytanie pierwsze odpowiedź brzmi tak, gdyż początek był trywialny (0, m). W każdym
przebiegu pętli wykonujemy q = q + 1, r = r − n w skończonym czasie, czyli wystarczy
wykazać, że algorytm wykona skończenie wiele przebiegów. Kluczowe są zmiany r: m, m−
n, m−2n, . . . na początku r = m  0, ponieważ każdy niepusty podzbiór liczb naturalnych
ma element najmniejszy, to malejące ciągi lizb naturalnych muszą być skończone. Stąd
po k wykonaniach pętli (dla q > k) mamy m − kn = r < n (wybieramy najmniejsze k o
tej własności).

Czyli algorytm zatrzymuje się, co jednakże z poprawnością wyników?

Definicja 1.1.1 Zdanie p jest niezmiennikiem pętli dopóki g, wykonuj S wtedy gdy, speł-
nia ono warunek: jeśli zdania g i q są prawdziwe, zanim wykonamy S, to zdanie p będzie
prawdziwe po wykonaniu S.

Twierdzenie 1.2 Załóżmy, że p jest niezmiennikiem pętli dopóki g, wykonuj S oraz,
że zdanie p jest prawdziwe, kiedy wchodzimy w pętle. Wówczas zdanie p jest prawdziwe po
każdej iteracji pętli. Jeśli pętla kończy się, to po jej zakończeniu zdanie p jest prawdziwe,
a zdanie g fałszywe.

Dowód. Uzasadniajmy nie wprost, p jest prawdziwe na początku. Niech p będzie fałszy-

we po n-tej iteracji po raz pierwszy. Czyli n  1 i zdanie p było prawdziwe po zakończeniu
n − 1 przebiegu (początek to iteracja o numerze 0) zdanie g również było prawdziwe, gdyż
wykonaliśmy n-tą iterację. Ponieważ p jest niezmiennikiem pętli, to musi być prawdziwe.
Sprzeczność.

W dowodzie rozpatrywaliśmy zbiór: A = { n ∈ N: zdanie p jest fałszywe po n-tym

przebiegu }. Z założenia zbiór A jest niepusty i ma element najmniejszy, co daje sprzecz-
ność.

Rozważmy następujący algorytm dzielenia:

{ Dane: m ∈ N

n ∈ N }

{ Wyniki: q ∈ N

r ∈ N

takie, że qn + r = m oraz r ∈ 0, n − 1 }

POCZĄTEK
q:=0
r:=m
{qn+r=m oraz r>=0}
DOPÓKI r>=n WYKONUJ
q=:q+1

ROZDZIAŁ 1. Modele algorytmiczne — warunek dopóki.

r=:r-n
KONIEC

Stwierdzenie 1.2.1 qn + r = m i r  0 jest niezmiennikiem pętli

Dowód. Warunek jest prawdziwy przed wejściem w pętle dopóki z doboru q i r. Po-

nadto, jeśli qn + r = m i r n i po wykonaniu treści pętli dostajemy q

i r

takie,

że

n + r

= (q + 1)n + (r − n) = qn + r = m

oraz r‘ = r − n  0 Czyli stwierdzenie to pozostaje prawdziwe po wykonaniu pętli. Tak
więc

1. Pętla kończy się.

2. Z twierdzenia 1.2 po zakończeniu pętli zdania m = qn + r oraz r  0 są prawdziwe,

a zdanie r n jest fałszywe czyli r < n.

Koniec dowodu.

Przykład. Rozważmy procedure wyliczania wartości n!!.
Wzór

0!! = 1!! = 1
n!! = (n − 2)!!n

{ Dane: n ∈ N

}

{ Wyniki: s ∈ N taka, że s = „silnia silnia”= n!! }

POCZĄTEK
s:=1 {s:=m!!}
JEŚLI 2 dzieli n TO m:=1
W PRZECIWNYM PRZYPADKU m:=0
DOPÓKI m<n-1 WYKONUJ
m:=m+2
s:=sm
KONIEC

Planowanym niezmiennikiem pętli jest s = m!!. Jeśli s = m!! na początku pętli dopóki,

to:

nowe

= s

stare

nowe

= m!!(m + 2) = (m + 2)!! = (m

nowe

)!!

Co było wymagane na końcu pętli. Pętla kończy się, gdy m = n.

Uwaga. W powyższym algorytmie obliczyliśmy oprócz n!! także (n − 2)!!, (n − 4)!!,

. . . .

Możemy zmodyfikować porządek mnożenia, unikając trudniejszego sformułowania wa-

runku początkowego:

{ Dane: n ∈ N

}

{ Wyniki: p ∈ N takie, że p = n!! }

POCZĄTEK
p:=1
m:=n
{m!!p=n!!}
DOPÓKI m>1 WYKONUJ
p:=pm
m:=m-2

Sprawdzenie niezmiennika pętli: na początku jest on prawdziwy i jest m!!p = n!! więc:

nowe

!!p

nowe

= (m − 2)!!pm = m!!p = n!!

Warunek dozoru pętli powoduje, że pętla kończy się gdy m = 3 lub m = 2 (o ile n > 1).
Jeśli zaś n ∈ {0, 1}, to n!! = 1 = m!!p dla wszystkich n ∈ N

. Powyższy algorytm oblicza

w trakcie działania wyrażenia postaci n, n(n − 2), n(n − 2)(n − 4), . . . .

Uwaga. W algorytmie dzielenia występowała zmienna zwiększająca się o 1 w każdym

przebiegu pętli. Nie było jednak wiadome, ile przebiegów wykonamy. W poprzednim algo-
rytmie m przyjmowało wartości 0, 2, 4, . . . , n lub 1, 3, 5, . . . , n w tej kolejności, wiadome
było kiedy algorytm się zatrzyma. Tego typu przewidywalne zwiększanie o 1, 2 lub inną
ustaloną liczbę można opisać przy pomocy następującej notacji:

Definicja 1.2.1 Instrukcja algorytmiczna: dla k od m do n z krokiem r wykonuj S, powo-
duje podstawienie liczb m, m+r, m+2r, . . . , n zamiast k, w takiej kolejności i wykonanie
S za każdym razem (o ile krok jest tak dobrany że m + qr = n).

Fragment algorytmu,

s:=1
DLA k OD 1 DO n WYKONAJ
s:=sk

daje wynik s = n!. Używając pętli dopóki możemy to zapisać:

k=m
DOPÓKI k=<n WYKONUJ
{S} k=k+1

Uwaga. Fragment S nie może zmieniać wartości k.
Przykład. Pętla dopóki.

k:=1
DOPÓKI k=<4 WYKONUJ
k:=k^2
wypisz} k
k:=k+1
KONIEC

Przykład. Pętla ze stałym krokiem (bezwarunkowa).

POCZĄTEK
DLA k OD 1 DO 4 WYKONUJ
k:=k*k
wypisz k
KONIEC

ROZDZIAŁ 1. Modele algorytmiczne — warunek dopóki.

numer iteracji

wypisz k

k ¬ 4

prawda

fałsz

Tabela 1.2:

numer iteracji

wypisz k

Tabela 1.3:

Przykład. Algorytm obliczania sumy.

k=m

= a

+ a

m+1

+ . . . + a

n ∈ N

Algorytm:

s:=0
DLA k OD m DO n WYKONUJ
s:=s+a(k)

Na przykład

k=1

+ . . . +

Uwaga. Nie zawsze da się prosto zastosować pętle bezwarunkowe. Trzeba znać liczbę

przebiegów pętli.

Rozdział 2

Indukcja i dowodzenie
jednoczesne. ([1], [4])

Omówimy tutaj konsekwencje twierdzenia 1.2 o niezmiennikach pętli, w konstrukcji in-
dukcyjnej (poprawność wynika z dobrego uporządkowania zbioru N).

Przykład. Wykażmy, że 14 | 37

700

− 37

100

i znajdźmy wynik dzielenia (liczbę ponad

1000-cyfrową). Z nieparzystości 37 mamy 2 | 37

700

− 37

100

wystarczy wykazać, że 7 |

700

− 37

100

, lecz jeżeli q = 3

100

to 7 | q

− q i zamiast liczyć możemy spróbować

wykazać, że ∀n ∈ N 7 | n

− n (sprawdzamy doświadczalnie dla małych q ∈ N),

7 | 1

− 1 = 0

7 | 2

− 2 = 126

7 | 3

− 3 = 2184

7 | 4

− 4 = 16380

7 | 15

− 15 = 170859360

Konstruujemy pętlę, która ma sprawdzić czy n

−n jest podzielne przez 7 dla n ∈ 1, 37

100

POCZĄTEK
n:=1
DOPÓKI n<37^100 WYKONUJ
JEŚLI n^7-n jest podzielne przez 7 TO
n:=n+1
KONIEC

Niezmiennikiem pętli jest: n

−n podzielne przez 7. Pętla sprawdza, czy warunek zachodzi

i jeżeli jest prawdziwy, to przechodzi do następnego n. Sprawdziliśmy, że 7 | 1

− 1, stąd

na początku wchodząc w pętlę przewidywany niezmiennik jest prawdziwy. Twierdzimy,
że algorytm się kończy (dla n = 37

100

) oraz, że podane zdanie jest niezmiennikiem pętli.

Rozważmy k-ty przebieg pętli k < 37

100

. Jeśli 7 - k

− k to nie nastąpi wykonanie

treści pętli, algorytm nie zatrzyma się. Jeśli zaś 7 | k

− k, to z treści pętli k ⇒ k + 1,

algorytm sprawdza warunek dozoru k + 1 < 37

100

i następnie warunek podzielności dla

ROZDZIAŁ 2. Indukcja i dowodzenie jednoczesne.

k + 1. Wystarczy pokazać, że w każdej iteracji zdanie warunkowe jest prawdziwe. Zapewni
to wykonanie i zatrzymanie algorytmu. Czy 7 | (k + 1)

− (k + 1)?

(k + 1)

− (k + 1) =

+ 7k

+ 21k

+ 35k

+ 21k

+ 7k + 1 − k − 1 =

− k + 7k(k

+ 3k

+ 5k

+ 3k + 1)

Stąd algorytm możemy uprościć, nie musi sprawdzać zdania warunkowego, podzielność
jest zagwarantowana. Czyli w iteracji zwiększamy jedynie n o 1 aż dla n = 37

100

pętla

kończy się. W początkowej wersji algorytm musiałby sprawdzać podzielność dla wszyst-
kich liczb 1

−1, 2

−2, 3

−3, . . . , (37

100

−1)

−(37

100

−1). Jednakże jedyną liczbą, którą

należało sprawdzić była 1

− 1. Dla wszystkich pozostałych wykazaliśmy algebraicznie,

że o ile 7 | k

− k ⇒ 7 | (k + 1)

− (k + 1) i nie było potrzeby wykonywania w praktyce

naszego algorytmu, posłużył on jedynie do wykazania, że 7 | 37

700

− 37

100

Analogicznie możemy pokazać, że ∀n ∈ N 7 | n

− n stosując powyższe rozumowanie

do nie kończącej się pętli.

n:=1
DOPÓKI n>=1 WYKONUJ
JEŚLI 7 dzieli n^7-n TO
n:=n+1

Uogólnijmy to rozumowanie. Weźmy skończony ciąg zdań:

p(m), p(m + 1), . . . , p(n) gdzie p(k), k ∈

hm, ni

m < n

m, n ∈ N. W przykładzie

powyżej, było to 7 | k

− k dla k ∈ 1, 37

100

Ponadto wiemy że:

1. Zdanie p(m) jest prawdziwe.

2. Zdanie p(k + 1) jest prawdziwe jeżeli zdanie p(k) jest prawdziwe i k ∈ m, n − 1

Wówczas wszystkie zdania p(k), k ∈ m, n są prawdziwe. Uzasadnienie możemy zrealizować
przy pomocy pętli:

k:=m
{zdanie p(k) jest prawdziwe}
DOPÓKI k należy do <m,n-1> WYKONUJ
JEŚLI p(k) jest prawdziwe TO
k:=k+1

Z 2 wynika, że zdanie p(k) jest prawdziwe, jest niezmiennikiem pętli i pętla kończy się
dla k=n. Czyli zachodzi p(k) ⇒ p(k + 1), stąd p(k) jest prawdziwe na końcu każdego
przebiegu pętli. Z dobrego uporządkowania N wynika, że jeśli kiedykolwiek zdanie p(k)
będzie fałszywe, to musi istnieć najmniejsze i dla którego jest nieprawdziwe. Lecz z 1 i 2
otrzymujemy, że i /

∈ m, n.

Tą techniką wykazaliśmy:

Twierdzenie 2.1 Zasada skończonej indukcji matematycznej. Niech p(k), k ∈ m, n bę-
dzie skończonym ciągiem zdań. Jeśli

1. zdanie p(m) jest prawdziwe oraz

2. zdanie p(k + 1) jest prawdziwe, jeżeli zdanie p(k) jest prawdziwe, k ∈ m, n − 1.

To wszystkie zdania są prawdziwe.

Zastępując warunek k ∈ m, n warunkiem k ∈ N ∧ k m mamy

Twierdzenie 2.2 Zasada indukcji matematycznej. Niech p(m), p(m + 1), . . . , będzie
ciągiem zdań. Jeżeli

1. zdanie p(m) jest prawdziwe oraz

2. zdanie p(k + 1) jest prawdziwe jeżeli zdanie p(k) jest prawdziwe k m, k ∈ N to

∀k ∈ N;

k m zdania p(k) są prawdziwe.

Definicja 2.2.1 Punkt pierwszy w każdej z postaci zasady indukcji jest warunkiem po-
czątkowym.

Definicja 2.2.2 Punkt drugi nazywamy krokiem indukcyjnym.

Jeśli wykażemy oba punkty to mamy zakończony dowód indukcyjny.

W dowodach indukcyjnych nie dowodzimy bezpośrednio prawdziwości zdania p(k +

1). Dowodzimy implikacji p(k) ⇒ p(k + 1) jeżeli teraz p(k) jest prawdziwe, to z reguły
odrywania p(k+1) jest prawdziwe. Czyli w pewnym sensie dowodzimy nieskończenie wielu
twierdzeń, p(1), p(1) ⇒ p(2), p(2) ⇒ p(3), . . . . W technice dowodu nie musimy wykonywać
pętli. Pętla została wykorzystana do dowodu (2.2) zasady indukcji matematycznej. Mamy
tylko sprawdzić oba warunki.

Przykład. Udowodnić indukcyjnie, że

...i

= n gdzie sumowanie przebiega po

wszystkich niepustych (różnych) podzbiorach {i

, i

, . . . , i

} zbioru {1, 2, . . . , n}, (i

< . . . < i

Dowód. Indukcja względem n.
Warunek 1. Dla n = 1 tylko {1} 6= ∅, {1} ⊂ {1} odpowiada mu suma

1
1

= 1.

Warunek 2. Załóżmy, że twierdzenie jest prawdziwe dla pewnej liczby n  1. Każdy

niepusty pozdbiór zbioru {1, 2, . . . , n, n + 1} jest:

suma mnogościową {n + 1} i niepustego podzbioru zbioru {1, 2, . . . , n}

zbiorem jednoelementowym {n + 1}

podzbiorem zbioru {1, 2, . . . , n}

Stąd suma

...i

brana po wszystkich niepustych podzbiorach zbioru {1 , 2, . . ., n,

n + 1}, wynosi

n + 1

n +

1 + n

+ n =

n + 1 + n(n + 1)

n + 1

(n + 1)

n + 1

= n + 1

Gdyż w pierwszym składniku korzystamy z założenia indukcyjnego i wyłączamy wspól-
nyczynnik

n+1

Przykład. Złe użycie indukcji. ∀n  2

2 | n.

Warunek 1 Sprawdzamy dla n = 2 :

2 | 2.

Warunek 2.

2 | 2, 2 | 3, . . . , 2 | (k − 1), 2 | k

k  2

ROZDZIAŁ 2. Indukcja i dowodzenie jednoczesne.

Stąd 2 | (k + 1) bo 2 | (k − 1) ⇒ (k − 1) = c2, c ∈ N

⇒ k + 1 = 2 + (k − 1) =

2(c + 1) ⇒ c

= c + 1

∃c

∈ N k + 1 = 2c

Przykład. Ciąg (x

) jest określony wzorem:

= c

c ∈ N

n+1

= cx

p(c

− 1)(x

− 1)

n ∈ N

Wykażemy, że ∀n

∈ N.

Sprawdzamy dla pierwszych dwóch wyrazów warunek 1.

= c

= 2c

− 1 ∈ N

Zakładamy, że (warunek 2)

∀k ∈ 1, n

∈ N ⇒ x

n+1

∈ N

n+1

− cx

− 1)(x

− 1)

czyli

n+1

− cx

)

= (c

− 1)(x

2
n

− 1)

(2.1)

analogicznie renumerując

n − 1 → n

− cx

n−1

)

= (c

− 1)(x

2
n−1

− 1)

2
n

− 2cx

n−1

+ c

2
n−1

= c

2
n−1

− c

− x

2
n−1

+ 1

2
n

+ c

− 1 = 2cx

n−1

− x

2
n−1

2
n

− x

2
n

− c

+ 1 = c

2
n

− 2cx

n−1

+ x

2
n−1

− 1)(x

2
n

− 1) = (cx

− x

n−1

)

(2.2)

Porównując 2.1 i 2.2 mamy (x

n+1

−cx

)

= (cx

−x

n−1

)

z definicji ciągu x

n+1

 cx

ponadto c ∈ N oraz (x

) jest niemalejący to cx

 x

n−1

stąd mamy x

n+1

− cx

− x

n−1

⇒ x

n+1

= 2cx

− x

n−1

∈ N.

Zapiszmy dotychczas poznaną zasadę indukcji matematycznej (twierdzenie 2.2) ina-

czej.

Stwierdzenie 2.2.1 Niech m ∈ Z oraz p(n) niech będzie ciągiem zdań dla n ∈ Z, n m.
Jeśli

1. zdanie p(m) jest prawdziwe oraz

2. dla k > m zdanie p(k) jest prawdziwe, jeśli zdanie p(k − 1) jest prawdziwe

To zdanie p(n) jest prawdziwe dla każdego n ∈ Z, n m.

Twierdzenie 2.3 Druga zasada indukcji matematycznej. Niech n ∈ Z oraz niech p(n)
będzie ciągiem zdań zdefiniowanych na zbiorze {n ∈ Z n m} jeśli

1. zdanie p(m) jest prawdziwe oraz

2. dla k > m zdanie p(k) jest prawdziwe, jeśli wszystkie zdania p(m), . . . , p(k − 1) są

prawdziwe.

To zdanie p(n) jest prawdziwe ∀n ∈ Z n m.

Sprawdzenie warunku 2.

Mamy

k =m + 1

p(m) ⇒ p(m + 1)

k =m + 2

p(m) ∧ p(m + 1) ⇒ p(m + 2)

Uwaga. Zasady indukcji matematycznej używamy gdy prawdziwość zdań w (warunku

2) wynika z poprzednich, lecz nie bezpośrednio poprzedzających zdań.

Stwierdzenie 2.3.1 Każda liczba całkowita n  2 może być zapisana jako iloczyn liczb
pierwszych, przy czym jeśli n ∈ P to iloczyn traktujemy jako n, czyli tę liczbę.

Dowód. Zauważmy, że do wykazania że 2

132049

można tak zapisać (jako iloczyn 2 . . . 2

| {z }

132049

nie potrzebujemy korzystać z liczby poprzedniej czyli 2

132049

−1 która jest liczba pierwszą i

ma 39751 cyfr. Czyli pierwsza zasada indukcji (twierdzenie 2.2) nie będzie tu bezpośrednio
przydatna.

Warunek 1. Bierzemy p(2), jest to liczba pierwsza, czyli „iloczyn” z definicji.
Warunek 2. Bierzemy k  2 i zakładamy, że zdanie p(n) jest prawdziwe dla wszystkich

n ∈ 2, k − 1. Mamy wykazać, że p(k) jest prawdziwe jeśli k ∈ P, to jest to prawda. Jeśli
k /

∈ P, to k = ij gdzie i, j ∈ N − {1} czyli 2 ¬ i < k oraz 2 ¬ j < k, lecz p(i) i p(j)

są z założenia (twierdzenie 2.2) zdaniami prawdziwymi czyli i i j są iloczynami liczb
pierwszych, więc ij jest również iloczynem liczb pierwszych.

Uwaga. Konstrukcja egzystencjalna dowodu nie wymaga stałego kroku (różnego od

jeden) dlatego nie jest konieczne sprawdzanie w warunku 1 innych zdań niż p(2).

Uwaga. Są sytuacje, gdy ogólny dowód kroku indukcyjnego nie funkcjonuje dla skoń-

czenie wielu początkowych wartości k. Te wartości muszą być wówczas sprawdzane od-
dzielnie, czyli włączamy je w konstrukcję warunku drugiego. To uogólnienie można sfor-
mułować następująco:

Twierdzenie 2.4 Druga zasada indukcji matematycznej. Niech m ∈ Z, niech p(n) będzie
ciągiem zdań zdefiniowanych dla n ∈ Z, n m niech l ∈ N

. Jeśli

1. wszystkie zdania p(m), . . . , p(m + l) są prawdziwe oraz

2. dla k > m + l zdanie p(k) jest prawdziwe, jeśli wszystkie zdania p(m), . . . , p(k − 1)

są prawdziwe

To zdanie p(n) jest prawdziwe dla każdego n ∈ Z, n m.

Poprzednią wersję pierwszej zasady otrzymujemy dla l = 0, jeśli zaś l > 0 to renumeracja
ciągu sprowadza sformułowanie do poprzedniej postaci drugiej zasady.

Uwaga. Obie wersje zasady indukcji matematycznej można sformułować dla ciągów

skończonych jako zasady skończonej indukcji matematycznej.

Twierdzenie 2.5 Wykażemy równoważność obu postaci zasady indukcji matematycznej
w wersji nieskończonej.

ROZDZIAŁ 2. Indukcja i dowodzenie jednoczesne.

Dowód. Z drugiej wynika pierwsza, bo jeśli zachodzi p(m) ∧ . . . ∧ p(k − 1) to zachodzi

p(k − 1). Z pierwszej wynika druga. Udowodnimy przez zaprzeczenie.

1. Warunek 1. p(m), . . . , p(m + l) są prawdziwe.

2. Warunek 2. Dla k > m+l zdanie p(k) jest prawdziwe, jeśli zdania p(m), . . . , p(k −1)

są prawdziwe i zdanie p(n) jest fałszywe dla pewnego n m.

Konstruujemy zbiór S = {n ∈ Z n m oraz zdanie p(n) jest fałszywe } 6= ∅ Na mocy
zasady dobrego uporządkowania, zbiór S ma element najmniejszy n

z warunku 1: n

m + l. Ponieważ p(n) jest prawdziwe dla n ∈ m, n

, to p(n

) jest prawdziwe na mocy

pierwszej postaci, to n

∈ S sprzeczność. Więc p(n) jest prawdziwe dla n m.

Rozdział 3

Definicje rekurencyjne. ([1], [2],
[5], [10], [11])

Definicja 3.0.1 Mówimy że model ma konstrukcję rekurencyjną, jeżeli:

1. Określony jest pewien skończony zbiór obiektów modelu (zwykle jeden lub kilka pierw-

szych obiektów).

2. Pozostałe obiekty są zdefiniowane za pomocą poprzednich.

Wzór definiujący obiekt nazywamy: wzorem, równaniem lub zależnością rekurencyjną.

Punkt 1 to warunek zawierający początek lub krok początkowy definicji, a punkt 2

definiuje następne obiekty jako reguła rekurencyjna.

Przykład. Badamy ciąg s(n) =

n
k=0

1. s(0) = 1

2. s(n + 1) = s(n) +

(n+1)!

Gdzie z kolei ciąg n! = s(n) jest zdefiniowany rekurencyjnie dla n ∈ N

1. s(0) = 1

2. s(n + 1) = (n + 1)s(n)

Wygodę stosowania definicji rekurencyjnej bez ciągłego obliczania na przykład n! daje

konstrukcja:

Q(0)

Q(n + 1)

n + 1

Q(n)

Kilka początkowych wartości umieściliśmy w tabeli 3.1.

Uwaga. Nie znamy wzoru ogólnego! Wyrazy, na przykład Q(55) istnieją, chyba, że

któryś krok wymaga czynności niedozwolonej matematycznie. Dla dowodu skorzystajmy
z zasady dobrego uporządkowania N.

S = {n ∈ N Q(n) = 0 ∨ Q(n) nie jest określony}

ROZDZIAŁ 3. Definicje rekurencyjne.

n = 0

Q(1) =

1
1

= 1

n = 1

Q(2) =

2
1

= 2

n = 2

Q(3) =

3
2

n = 3

Q(4) =

8
3

Tabela 3.1:

Pokażemy, że S = ∅. W przeciwnym przypadku, istniałby najmniejszy element m ∈ S.

Z warunku 1 Mamy m 6= 0, to m − 1 ∈ N

, Q(m − 1) 6= 0 i Q(m − 1) jest określona. Z

warunku 2 mamy Q(m) =

Q(m−1)

6= 0 czyli m /

∈ S ⇒ S = ∅ (przez sprzeczność), czyli

Q(n) jest dobrze określona dla n ∈ N

Uwaga. W powyższym dowodzie korzystaliśmy z faktu, że Q(n + 1) zależy tylko od

Q(n). Jeżeli konstrukcja zależy od innych niż tylko poprzedzający wyrazów, to dowód
można poprawić modyfikując warunek 1, również z zasady dobrego uporządkowania albo
z rozszerzonej wersji zasady indukcji matematycznej (twierdzenie 2.4).

Uwaga. Istnieją konstrukcje rekurencyjne bardziej efektywne, gdy nie trzeba wyliczać

wszystkich wyrazów poprzednich, a tylko niektóre.

Przykład.

T (1)

T (n)

dla

n  2

Wówczas

T (99) = 2T

= 2T (49) =

2 · 2T (24) = 2

T (12) = 2

T (6) = 2

T (3) =

= 2

T (1) = 2

Potrzebne są wartości T (49), T (24), T (12), T (6), T (3), nie ma potrzeby obliczać innych.

Przykład. Ciąg Fibonacciego.

F (0)

F (1) = 1

F (n)

F (n − 1) + F (n − 2)

dla

n ∈ N, n 2

Oczywiście wzór rekurencyjny nie ma sensu dla n = 1 stąd F (1) musi być zdefiniowane
w warunku 1. Początkowe wyrazy ciągu podajemy w tabeli 3.2.

Przykład. Jak zdefiniować ciąg 1, 1, 1, 2, 2, 2, 3, 3, 3, . . .

Q(0) = Q(1) = Q(2) = 1

Q(n) = Q(n − 3) + 1

n  3

F(n)

Tabela 3.2: Wartości ciągu Fibonacciego.

Przykład. Niech ω = {a, b}, będzie alfabetem złożonym z dwóch liter. Niech s

oznacza

liczbę słów długości n, w których nie występują kolejne dwie litery a, a. Oznaczmy przez

zbiór słów zawartych w ω

{

ω × ω × . . . × ω nie zawierających dwóch kolejnych liter

a: A

= ∅, A

= ω, A

= ω

− {(a, a)}. Przyjmujemy długość 0 słowa pustego. Liczba

słów o długości zero to s

= 1 (założenie), s

= 2, s

= 3, aby przeliczyć liczbę słów

spełniających warunek, czyli wyznaczyć s

załóżmy, że n  2 i przyjmujemy konstrukcje

rekurencyjną przy pomocy słów krótszych. Jeżeli słowo należące do A

kończy się literą

b, to może je poprzedzać dowolna litera, czyli dowolne słowo z A

n−1

. Jeśli jest to a, to

musi ją poprzedzać b czyli słowo z A

n−2

a po nim b. Stąd:

= s

n−1

+ s

n−2

oraz

= 1

= 2

Łatwo zauważyć, że s

= F (n + 1), n ∈ N. Można także, przerachować słowa zawierające

powtórzenia a. Jest ich 2

− F (n + 1), z czego 2

2 · . . . · 2
|

}

n możliwości wyboru

to liczba wszystkch

słów o długości n.

ROZDZIAŁ 3. Definicje rekurencyjne.

Rozdział 4

Ciągi rekurencyjne. ([1], [3], [5],
[6], [7], [10], [11], [13], [17], [21])

Definicja 4.0.2 Ciąg (a

) nazywamy ciągiem rekurencyjnym rzędu k, jeżeli istnieje licz-

ba naturalna k i liczby rzeczywiste (lub zespolone), γ

, γ

, . . ., γ

, takie, że poczynając od

pewnej wartości m wskaźnika n, dla wszystkich następnych wartości wskaźnika n, zachodzi
związek

n+k

= γ

n+k−1

+ γ

n+k−2

+ . . . + γ

(4.1)

Powyższy związek nazywamy równaniem rekurencyjnym rzędu k.

Tak więc ciąg rekurencyjny ma tę własność, że poczynając od pewnego miejsca każ-

dy jego wyraz wyraża się przy pomocy wzoru 4.1 przez stale tę samą ilość k wyrazów
poprzedzających.

Rozważmy ciąg rekurencyjny zdefiniowany następująco:

= c

, c

∈ R (lub innego ciała liczbowego)

n+2

= αa

n+1

+ βa

n ∈ N

Definiujemy równanie charakterystyczne dla tego ciągu w postaci:

= αx + β

lub

− αx − β = 0

(4.2)

Zbadajmy najpierw przypadki szczególne:

β = 0

α 6= 0

=⇒

= c

n+1

= αa

n ∈ N to

= αa

= α

i przez indukcję

n+1

= α

jeżeli

= αc

= α

ROZDZIAŁ 4. Ciągi rekurencyjne.

α = 0 ∧ β 6= 0

=⇒

= c

n+2

= βa

= βc

= βa

= βc

= β

i przez indukcję

= β

n ∈ N

2n+1

= β

Weźmy α, β 6= 0, stąd możemy postawić hipotezę, że rozwiązania mogą przyjąć postać
wzoru ogólnego a

= bq

, z b jako stałą lub kombinacji liniowej takich wyrażeń. Ponadto,

w takiej sytuacji określmy q:

n+2

= αq

n+1

+ βq

/ : q

q 6= 0

czyli

− αq − β = 0

Czyli q jest rozwiązaniem równania charakterystycznego. Załóżmy że q ∈ R.

Twierdzenie 4.1 Przyjmijmy zależność rekurencyjną w postaci:

n+2

= αa

n+1

+ βa

n ∈ N

= c

, a

= c

(4.3)

Dla której równanie charakterystyczne ma postać:

− αx − β = 0

α, β 6= 0

(4.4)

Jeśli równanie charakterystyczne ma dwa różne pierwiastki q

6= q

= k

+ k

(4.5)

Wartości stałych wyznaczamy z układu liniowego

= k

+ k

= k

+ k

Jeżeli istnieje jeden podwójny pierwiastek q to

= k

+ k

(4.6)

i k

, k

wyznaczamy z układu

= k

q + k

q ⇒ k

= −c

Dowód 4.5. Układ

= k

+ k

= k

+ k

ma zawsze rozwiązanie ponieważ q

6= q

. Zależność rekurencyjna to a

n+2

= αa

n+1

+ βa

Wystarczy pokazać, że ciąg zdefiniowany w punkcie 4.5 spełnia tę zależność. Ponieważ

= αq

+ β

i = 1, 2

n+2

= αq

n+1

+ βq

i = 1, 2

Gdyż q

spełniały równanie charakterystyczne 4.2, sprawdzamy kombinacje liniową (in-

dukcja)

αa

n+1

+ βa

α(k

n+1

+ k

n+1

) + β(k

+ k

) =

(αq

n+1

+ βq

) + k

(αq

n+1

+ βq

) =

n+2

+ k

n+2

= a

n+2

n ∈ N

Dowód 4.6. Równanie charakterystyczne ma postać:

(x − q)

= 0

− 2qx + q

= x

− αx − β ⇒ α = 2q

β = −q

Równanie rekurencyjne przyjmuje postać:

n+2

= 2qa

n+1

− q

n ∈ N

= c

= k

= c

= (k

+ k

q 6= 0

= c

= −c

Wystarczy pokazać, że dowolny ciąg określony wzorem 4.6 spełnia zależność

n+2

= 2qa

n+1

− q

lecz

2qa

n+1

− q

2q(k

n+1

+ k

(n + 1)q

n+1

) − q

+ k

) =

(2q

n+2

− q

n+2

) + k

(2(n + 1)q

n+2

− nq

n+2

) =

n+2

+ k

(n + 2)q

n+2

= a

n+2

n ∈ N

Uwaga. Dowód jest również prawdziwy dla q

, q

∈ R, (∈ C−R), lecz o ile α, β, c

, c

∈

R to ∀n ∈ N

∈ R.

ROZDZIAŁ 4. Ciągi rekurencyjne.

Przykład. Niech a

n+2

= a

n+1

+ 2a

, a

= a

= 3

n ∈ N

. Równanie charaktery-

styczne x

− x − 2 = 0 ma pierwiastki: q

= 2, q

= −1, stosujemy punkt 4.5 twierdzenia

4.1 i:

= k

+ k

(−1)

= 3 = k

+ k

= 3 = 2k

− k

⇒ k

= 2

= 1

czyli

= 2 · 2

+ (−1)

= 2

n+1

+ (−1)

n ∈ N

Przykład. Ciąg Fibonacciego.

= a

= c

= 1

n+2

= a

n+1

+ a

n ∈ N

czyli α = β = 1, to równanie charakterystyczne x

− x − 1 ma dwa pierwiastki

1 +

√

1 −

√

Stosujemy punkt 4.5 twierdzenia 4.1 skąd:

= k

1 +

√

+ k

1 −

√

n ∈ N

lub dla wygody k

+ k

. Wyznaczmy k

, k

1 = k

+ k

1 = k

1 +

√

+ k

1 −

√

+ k

√

− k

) =

√

− k

)

otrzymujemy więc

+ k

= 1

− k

√

= 1 +

√

⇒ k

5 +

√

= 1 −

1 +

√

5 −

√

stosując twierdzenie 4.1 punkt 4.5 mamy:

= k

+ k

√

−

√

n+1

− q

n+1

)

F (n) =

√

1 +

√

n+1

−

1 −

√

n+1

∈ N

Łatwo zauważyć przez oszacowanie

√

5 − 1

⇒ ∀n

√

1 −

√

n+1

F (n) ∼

√

(

1 +

√

)

n+1

dla dużych n

Przykład.

mamy ciąg

= 1

= −3

n+2

= 6a

n+1

− 9a

n ∈ N

równanie charakterystyczne:

− 6x + 9 = 0 ⇒ α = −6

β = 9

Mamy podwójny pierwiastek q = 3 stąd z punktu 4.6 z twierdzenia 4.1 wynika:

= k

+ k

n ∈ N

dla n = 0, 1 odpowiednio 1 = k

, −3 = 3k

+ 3k

, k

= −2 czyli

= 3

− 2n3

= 3

(1 − 2n)

n ∈ N

Wiele algorytmów wykorzystuje sortowanie, podział pliku (zbioru) na części, wykona-

nie działań w podczęściach a następnie agregowanie wyników. Wyliczając jednostkowe,
porównywalne operacje potrzebne do wykonania algorytmu przy zadanej wielkości n zbio-
ru mamy układ:

2 | n ⇒ Q(n) = 2Q

+ R(n)

R(n) – działania agregujące wyniki.

Twierdzenie 4.2 Niech a

będzie ciągiem spełniającym zależność rekurencyjną:

= 2a

+ r(n)

n ∈ N

(4.7)

wówczas:

= 2

k−1

m=0

r(2

)

k ∈ N

(4.8)

Uwaga. Gdy a

= 2a

+ a + bn gdzie a, b stałe, to:

= 2

+ (2

− 1)a +

zaś dla n = 2

mamy (szczególna postać):

= na

+ (n − 1)a +

n log

Dowód. Sprawdzamy warunek 1.

k = 0

0
2

= a

= 2

k − 1 < 0 ⇒

k−1

m=0

(. . .) = 0

ROZDZIAŁ 4. Ciągi rekurencyjne.

Warunek 2.

= 2

k−1

m=0

r(2

)

dla k ∈ N

mamy:

k+1

= a

2·2

= 2a

+ r(2

) =

jest to zależność rekurencyjna i z założenia 2 wynika, że

= 2

k+1

k−1

m=0

r(2

)

+ r(2

) =

k+1

k−1

m=0

r(2

)

2 · 2

r(2

)

k+1

m=0

r(2

)

W szczególnym przypadku, gdy f (n) = a + bn można podstawić ten wynik, lub bezpo-
średnio sprawdzić że:

= 2

+ (2

− 1)a +

k ∈ N

Uwaga, wzór z twierdzenia 4.2 nie podaje wszystkich wyrazów ciągu. Jednakże na

przykład, dla monotonicznych ciągów pozwala na oszacowania wielkości a

Rozdział 5

Przeliczanie. ([1], [4], [6], [7],
[10], [11], [18], [19], [20], [21])

Bedziemy rozważać modele przeliczające zbiory skończone

X = µ(X) < ∞. Konstrukcja

modelu polega na dobraniu takiej wzajemnie jednoznacznej funkcji f : X → Y , że Y jest
zbiorem o znanej strukturze kombinatorycznej, to znaczy znamy µ(Y ).

Definicja 5.0.1 Modelowanie zastępujące zbiór X o skomplikowanej strukturze, zbiorem
o zdefiniowanej strukturze, realizowane w sposób wzajemnie jednoznaczny (nawet dla zbio-
rów o większej mocy) nazywamy modelowaniem wzajemnie jednoznacznym lub przelicze-
niowym (dla zbiorów skończonych).

Ograniczmy się do zbiorów skończonych X = {x

, x

, . . . , x

}. Zbiorowi X odpowiada

wówczas zbiór indeksów I

= {1, 2, . . . n}. W niektórych przypadkach, gdy nie powoduje

to kłopotów interpretacyjnych (X ⇔ I

) utożsamia się powyższe zbiory.

Definicja 5.0.2 Niech I

= {1, 2, . . . , n} = 1, n, zbiór {i

, i

, . . . , i

} składający się z do-

wolnych elementów zbioru I

nazywamy ciągiem k-elementów zbioru I

(lub k-tką zbioru

). Analogicznie dla zbioru X, µ(X) = n.

Możemy w k-tkach wprowadzić rozróżnienie ze względu na to, czy ma znaczenie kolejność
elementów k-tki, oraz czy mogą powtarzać się elementy w k-tce. Oznaczamy:

= { zbiór nieuporządkowanych k-tek bez powtórzeń }

k ∈ 0, n

= { zbiór nieuporządkowanych k-tek z powtórzeniami }

k ∈ N

= { zbiór uporządkowanych k-tek bez powtórzeń }

k ∈ 0, n

= { zbiór uporządkowanych k-tek z powtórzeniami }

k ∈ N

Elementy zbiorów

i e

nazywamy kombinacjami z n elementów po k, odpowiednio bez

i z powtórzeniami. Elementy zbiorów

i e

nazywamy wariacjami, z n elementów po k

odpowiednio bez i z powtórzeniami.

Dla k = n zbiór

nazywamy zbiorem permutacji n elementów, gdzie przez per-

mutację rozumiemy konkretne ustawienie (ciąg uporządkowany n elementowy). Operacja
permutowania polega na przestawieniu elementów permutacji.

ROZDZIAŁ 5. Przeliczanie.

Dla przedstawienia liczebności elementów wyżej wymienionych zbiorów wprowadzamy

oznaczenia:

µ(

k
n

) = C

µ(e

k
n

) = e

µ(

k
n

) = V

µ(e

k
n

) = e

µ(

) = P

Indukcyjnie łatwo dowodzimy:

Twierdzenie 5.1

= n!

(5.1)

= n

(5.2)

(n − k)!

= n(n − 1)(n − 2) · . . . · (n − k + 1)

(5.3)

Twierdzenie 5.2

k!(n − k)!

(5.4)

n + k − 1

(5.5)

Dowód 5.4. Otrzymujemy natychmiast z twierdzenia 5.1 punkt 5.3 utożsamiając per-

mutację k-elementów (nie rozróżniamy kolejności)

Dowód 5.5. Niech X = {a

, a

, . . ., a

}, a

6= a

, i 6= j, i, j ∈ 1, n. Uzupełniamy

zbiór X o k − 1 nowych elementów a

n+1

, a

n+2

, . . ., a

n+k−1

tworzymy zbiór X

∗

= {a

, . . ., a

, a

n+1

, . . ., a

n+k−1

}, a

6= a

, i 6= j, i, j ∈ 1, n + k − 1. Wybieramy dowolny

k-elementowy ciąg uporządkowany {a

, a

, . . ., a

} z powtórzeniami elementów zbioru

X, gdzie i

 i

 . . . i

. Temu ciągowi (czyli k-tce) przyporządkowujemy następujący

ciąg k elementowy (k-tkę): {a

, a

, . . ., a

+k−1

Ta konstrukcja tworzy funkcję wzajemnie jednoznaczną pomiędzy zbiorem wszystkich

k-tek z powtórzeniami utworzonych z elementów zbioru X a zbiorem wszystkich k-tek
bez powtórzeń utworzonych z elementów zbioru X

∗

, czyli

= C

n+k−1

Przykład.

n = 2

X = {a, b}

k = 3 to do X

∗

dodajemy zbiór {c, d}

(a, a, a) → (a, b, c)

(a, a, b) → (a, b, d)

(a, b, b) → (a, c, d)

(b, b, b) → (b, c, d)

Twierdzenie 5.3 Niech ∀

i ∈ 1, k A

, a

, . . . , a

, n

∈ N. Zbiór k-tek upo-

rządkowanych postaci

1
i

, a

2
i

,. . ., a

k
i

gdzie a

1
i

∈ A

, a

2
i

∈ A

,. . . , a

k
i

∈ A

jest

iloczynem kartezjańskim A

× A

× . . . × A

= ×

k
i=1

wówczas µ(A

× A

× . . . × A

) =

· . . . · n

k
i=1

Dowód. Dowód metodą indukcji względem k. Z definicji k = 1, µ(A

) = n

. Dla k = 2

tworzymy macierz jak w poniższej tabeli. Stąd mamy µ(A

× A

) = n

. Analogicznie

. . .

, a

)

, a

)

, a

)

. . .

, a

)

, a

)

, a

)

, a

)

. . .

, a

)

. .

, a

)

, a

)

, a

)

. . .

, a

)

Tabela 5.1:

zwiększając wymiar produktu kartezjańskiego z k do k +1, mając A

∗

= A

×A

×. . .×A

∗

= A

× A

× . . . × A

× A

k+1

i zachowując konstrukcję tablicy jak dla k = 2

µ(A

∗
1

× A

∗
2

) = (n

· . . . · n

k+1

i=1

2Wniosek z twierdzenia 5.3:

µ(A

) = µ(A × A × . . . × A

}

) = n

co daje konstrukcję twierdzenia 5.1 punkt 5.2.

Twierdzenie 5.4 Niech A

∗

, a

, . . ., a

, a

, . . ., a

p
1

, a

p
2

, . . ., a

gdzie

p
i=1

= n. Tworzymy zbiór wszystkich permutacji elementów zbioru A

∗

, przy

czym traktujemy elementy a

, a

,. . ., a

jako nierozróżnialne dla i ∈ 1, p. Otrzymane

ciągi nazywamy permutacjami z powtórzeniami o długości n, utworzonymi z elementów
zbioru A =

, a

,. . ., a

} w których element a

powtarza się n

razy. Oznaczamy zbiór

tych permutacji przez e

,...,n

. Wówczas

µ(e

,...,n

) = e

,...,n

! · . . . · n

(5.6)

Dowód. Element a

możemy umieścić na C

różnych sposobów na n

ze wszystkich

n miejsc permutacji. Niezależnie od tego, każdemu z tych sposobów odpowiada C

n−n

różnych sposobów na jakie można wybrać n

z pozostałych n − n

miejsc, w których

umieszczamy element a

, i konstruujemy tak dalej aż do p-tego kroku, gdy a

umieszczamy

na C

n−n

−n

−...−n

p−1

= C

= 1 sposobów na pozostałych n − n

− n

− . . . − n

p−1

= n

ROZDZIAŁ 5. Przeliczanie.

miejscach, stąd:

µ( e

·...·n

) =

!(n − n

(n − n

!(n − n

− n

(n − n

− n

!(n − n

− n

· . . . ·

(n − n

− . . . − n

p−1

!0!

! · . . . · n

Przykład. Rozmieszczamy kule w szufladach.

1. Ułożono k nierozróżnialnych kul w n rozróżnialnych szufladach. Obliczyć liczbę

sposobów rozmieszczenia, gdy każda z szuflad może zawierać co najwyżej jedną
kulę.

(model Fermiego-Diraca)

2. Rozmieszczono k nierozróżnialnych kul w n rozróżnialnych szufladach. Obliczyć licz-

bę sposobów rozmieszczenia, gdy nie ma ograniczenia na liczbę kul w szufladzie

(model Bosego-Einsteina)

n+k−1

= e

3. Rozmieszczamy k rozróżnialnych kul w n rozróżnialnych szufladach. Oblicz liczbę

sposobów rozmieszczenia, jeżeli nie ma ograniczenia na liczbę kul, które mogą się
znaleźć w jednej szufladzie.

(model Maxwella-Boltzmanna)

4. Rozmieszczamy k rozróżnialnych kul w n rozróżnialnych szufladach. Oblicz liczbę

sposobów rozmieszczenia, jeśli jedna szuflada może zawierać co najwyżej jedną kulę.

Przykład. Udowodnić w oparciu o wzajemnie jednoznaczne modelowanie przeliczenio-

we, że

n
k

n−k

n
k

n−1
k−1

n−1

3. V

= V

n−1

+ kV

k−1

n−1

4. e

= e

n−1

+ e

k−1

n−1

+ . . . + e

n−1

+ e

n−1

5. e

= n e

k−1

Rozdział 6

Modele kombinatoryczne. ([1],
[2], [4], [5], [6], [9], [24])

W tym rozdziale zajmiemy się symetrycznym błądzeniem przypadkowym, fluktuacjami
przy rzutach monetą oraz modelami kombinatorycznymi.

Przykład. Rozważmy n kolejnych rzutów idealną monetą. Gracz „Grzegorz” w każdym

rzucie (doświadczeniu) wygrywa lub przegrywa kolejną jednostkową stawkę. Ciąg {s

, s

. . ., s

} reprezentuje łącznie zyski lub straty Grzegorza, na przykład nadwyżki orłów

nad reszkami. Jeśli s

= 0 zachodzi remis, s

= 1 wygrana a s

= −1 przegrana. Dla

uproszczenia przyjmujemy, że Grzegorz ma przewagę jeżeli s

> 0 lub s

= 0 ∧ s

n−1

> 0.

Pytanie na intuicję. Czy w długim ciągu rzutów Grzegorz powinien prowadzić przez

około połowę ciągu, a jego przeciwnik Gaweł przez pozostałą część czyli również przez
mniej więcej połowę.?

Definicja 6.0.1 Niech x ∈ N, y ∈ Z. Drogą {s

, s

, . . ., s

} od punktu (0, 0) do (x, y)

nazywamy łamaną, której wierzchołki mają odcięte w 1, x i rzędne s

, s

∈ Z s

= 0,

= y oraz s

− s

i−1

= ε = ±1, i ∈ 1, x.

Rysunek 6.1: Elementy łamanej.

Jeśli p spośród ε

, i ∈ 1, x jest równe 1, zaś q równych −1 to

x = p + q
y = p − q

⇒ p =

x + y

(gdy

2 | x + y)

q =

x − y

(6.1)

Dowolny punkt (x, y) można połączyć drogą wychodzącą z (0, 0) wtedy i tylko wtedy gdy
x,y spełniają powyższe równanie.

Drogi można przeliczyć jednoznacznie, wybierając miejsca w ciągu (1, 1, −1, −1, 1,

−1, . . .) z ε = 1 lub ε = −1 czyli odpowiednio p miejsc z 1 albo q miejsc z −1 w ciągu

ROZDZIAŁ 6. Modele kombinatoryczne.

p + q = x miejsc. Przyjmując L(x, y) = 0 gdy x, y nie spełnia warunków 6.1 to różnych
wyborów dróg mamy:

L(x, y) =

p + q

x+y

x−y

Wówczas istnieje dokładnie L(x, y) różnych dróg z (0, 0) do (x, y).

Poprzez translację wynika, że liczba dróg wiodących z punktu kratowego (x

, y

) do

punktu (x, y), 0 < x

< x, |y

| ¬ x

, |y| ¬ x, 2 | x

+ y

, 2 | x + y, jest równa liczbie

dróg z początku układu współrzędnych (0, 0) do punktu (x − x

, y − y

) czyli jest równa

L(x − x

, y − y

Lemat 6.0.1 (Zasada odbicia) Niech punkty kratowe A(x

, y

), B(x, y), 0 < x

x, y

> 0, y > 0 i A

= (x

, −y

) punkt symetryczny względem osi odciętych do A.

Wówczas liczba dróg z A do B, które dotykają lub przecinają oś odciętych jest równa
liczbie wszystkich dróg wiodących z punktu A

do B.

Rysunek 6.2: Model zasady odbicia.

Dowód. Budujemy relację wzajemnie jednoznaczną. Każdej drodze z A do B która

dotyka lub przecina oś odciętych przyporządkowujemy drogę z A

do B w taki sposób że,

jeżeli droga z A do B dochodzi po raz pierwszy do osi odciętych w punkcie C, to konstru-
ujemy element drogi A

C jako odbicie symetryczne AC względem osi odciętych. Pozostała

część drogi pozostawiamy bez zmian. Czyli mamy model wzajemnie jednoznaczny.

Możemy definiować:

Drogi dodatnie – wierzchołki leżą nad osią odciętych.

Drogi nieujemne – wierzchołki nie leża pod osią odciętych.

Drogi ujemne – wierzchołki leżą pod osią odciętych.

Drogi niedodatnie – wierzchołki nie leża nad osią odciętych.

Lemat 6.0.2 Liczba dróg dodatnich łączących początek układu współrzędnych (0, 0) z
punktem (x, y), 0 < y ¬ x jest równa

y
x

L(x, y) gdzie L(x, y) oznacza liczbę wszystkich

dróg z (0, 0) do (x, y).

Dowód. Dla wszystkich dróg dodatnich po wierzchołku (0, 0) następuje punkt (1, 1)

dlatego też szukana liczba dróg jest równa liczbie dróg dodatnich wiodących z (1, 1) do
(x, y), ta zaś jest równa różnicy między liczbą wszystkich dróg z (1, 1) do (x, y) a liczbą

Rysunek 6.3: Ilustracja dowodu.

wszystkich tych dróg z (1, 1) do (x, y) które dotykają lub przecinają oś odciętych. Odjem-
nik z zasady odbicia (lemat 6.0.1) można zastąpić przez liczbę wszystkich dróg wiodących
z A

do B(x, y), czyli razem liczba dróg dodatnich wynosi:

L(x − 1, y − 1) − L(x − 1, y − 1 + 2) =

x − 1

x+y

− 1

−

x − 1

x+y

−

x−y

L(x, y)

2Z symetrii wynika ponadto, że liczba dróg ujemnych wiodących do punktu (x, −y), y > 0
wynosi

y
x

L(x, y).

Przykład. Problem balotowania (tzw. twierdzenie o głosowaniu) J. Bertrand (1881).

Jeśli dwaj kandydaci R i S otrzymali w wyborach odpowiednio r i s głosów r > s to jaka
jest szansa na to, że przy zliczaniu głosów kandydat R będzie cały czas wyprzedzał pod
względem liczby głosów kandydata S.

Problem sprowadza się do obliczenia liczby dróg dodatnich z (0, 0) do punktu (r +

s, r − s), gdzie r + s to suma głosów a r − s przewaga R nad S. Na podstawie lematu 6.0.2
znamy liczbę dróg dodatnich która wynosi

r−s
r+s

L(r + s, r − s). Stąd szanse stałej przewagi

kandydata R nad S przy zliczaniu głosów są ilorazem tej liczby przez liczbę wszystkich
dróg L(r + s, r − s) i wynoszą

r−s
r+s

Przykład. Dwaj równorzędni gracze w grze bez remisów grają mecz złożony z 10 partii.

Mecz zakończył się zwycięstwem gracza A w stosunku 6 : 4. Jakie są szanse, że zwycięzca
prowadził po każdej partii? Stosując lemat 6.0.2 i poprzedni przykład mamy

6−4
6+4

= 0,2

Rozważmy problem dualny do lematu 6.0.2. Rozpatrujemy wszystkie drogi z (0, 0)

do (x, y) które posiadają tę własność, że rzędne wszystkich wierzchołków pośrednich są
mniejsze od y. Nazywamy je drogami osiągającymi po raz pierwszy poziom y w chwili x
lub drogami pierwszego osiągnięcia y.

Lemat 6.0.3 Liczba dróg wychodzących z początku układu współrzędnych (0, 0) i osiąga-
jących po raz pierwszy poziom y > 0 w chwili x jest równa

y
x

L(x, y).

Dowód. Rozpatrzmy relację równoważności między zbiorami dróg spełniających za-

łożenia lematu i dróg dualnych. Drogą dualną do {s

, s

, . . ., s

= y}, s

< y, i ∈

1, x − 1 nazywamy drogę odwróconego porządku, przesuniętą do punktu (0, 0) czyli s

∗

= s

− s

x−1

, . . . , s

∗
i

= s

− s

x−i

, . . . , s

∗

= s

oczywiście s

∗
i

> 0 dla i ∈ 1, x inaczej

∗

= ε

, s

∗

= ε

+ ε

x−1

, s

∗

= ε

+ ε

x−1

+ ε

x−2

, . . . , to stosownie do lematu 6.0.2 dla

dróg dodatnich mamy liczbę dróg dualnych (odwróconych) wynoszącą

y
x

L(x, y). Stąd z

ROZDZIAŁ 6. Modele kombinatoryczne.

wzajemnej jednoznaczności liczba dróg osiągających po raz pierwszy poziom y > 0 wynosi

y
x

L(x, y).

Lemat 6.0.3 dotyczy dróg, których wierzchołek jest najwyższy (geometrycznie). Droga

i dualna do niej łączą te same punkty i powstają w wyniku obrotu o 180

◦

jedna z drugiej

(względem „środka łamanej”).

Rysunek 6.4: Droga i dualna do niej.

Wniosek. Uwzględniając symetrie, liczba wszystkich dróg które osiągną po raz pierw-

szy poziom −y, y > 0 jest równa

y
x

L(x, y).

Lemat 6.0.4 Liczba dróg dodatnich wychodzących z punktu (0, 0) i kończących się w
punktach o odciętej x > 1 jest równa:

(

x−1

dla

2 | x

x−1

dla

2 - x

(6.2)

Dowód. Szukamy liczby wszystkich dróg dodatnich prowadzących z (0, 0) do zbioru

B = {(x, y):

y > 0}, wszystkie te drogi zawierają punkt (1, 1). Liczba dróg z (1, 1) do B

jest równa:

(

x
y=2

L(x − 1, y − 1)

dla

2 | x

x
y=1

L(x − 1, y − 1)

dla

2 - x

Zaś liczba dróg z (1, −1) do B wynosi:

(

x−2
y=2

L(x − 1, y + 1)

dla

2 | x

x−2
y=1

L(x − 1, y + 1)

dla

2 - x

Na podstawie lematu 6.0.1 znamy liczbę dróg dodatnich z (0, 0) do B:

(

x
y=2

L(x − 1, y − 1) −

x−2
y=2

L(x − 1, y + 1)

x
y=1

L(x − 1, y − 1) −

x−2
y=1

L(x − 1, y + 1)

(

L(x − 1, 1) +

x
y=4

L(x − 1, y − 1) −

x−2
y=2

L(x − 1, y + 1)

L(x − 1, 0) +

x
y=3

L(x − 1, y − 1) −

x−2
y=1

L(x − 1, y + 1)

(

L(x − 1, 1)

L(x − 1, 0)

(

x−1

dla

2 | x

x−1

dla

2 - x

6.1. Inne problemy kombinatoryczne.

Wniosek. Ogólna liczba dróg dodatnich i ujemnych wychodzących z początku układu

współrzędnych i kończących się w punktach o odciętej x > 1 jest równa:

(

2n−1

= 2

dla

x = 2n

dla

x = 2n + 1

6.1

Inne problemy kombinatoryczne.

([18])

Niech w będzie wielomianem jednej zmiennej, wówczas h(w) jest z definicji jego współ-

czynnikiem przy zmiennej w pierwszej potędze. Na przykład w(x) = c

+ c

x + . . . + c

to h(w) = c

Istotną rolę odgrywać będzie następujące twierdzenie,

Twierdzenie 6.1 Niech a ∈ R i k ∈ N. Wtedy

x + a







(−1)

a+k+1

(

k−1

)

a ∈ 0, k − 1

a
k

k−1
j=0

a−j

a /

∈ 0, k − 1

(6.3)

Dowód. Z definicji symbolu Newtona mamy

x + a

[x + a][x + (a − 1)] · . . . · [x + (a − k + 1)]

(6.4)

Oznaczmy kolejne czynniki w iloczynie 6.4 przez: (x + a

)(x + a

) · . . . · (x + a

). Po

wykonaniu mnożenia otrzymamy wielomian, którego współczynnik przy x jest sumą k
czynników w postaci a

· . . . · a

j−1

· . . . · a

. Rozważmy dwa przypadki:

1. Niech jedna z liczb a

, . . ., a

, na przykład a

, jest zerem. Wtedy wszystkie iloczyny

zawierające czynnik a

są równe 0 i współczynnik przy x redukuje się do jednego

iloczynu a

· . . . · a

j−1

· a

j+1

· . . . · a

. W szczególnoście dla rozważanego wielomianu

x+a

, przy podstawieniu

x + a = x + a

, x + (a − 1) = x + a

, . . . , x + (a − k + 1) = x + a

oraz założeniu, że a ∈ 0, k − 1 otrzymujemy:

a(a − 1) · . . . · 2 · 1 · (−1) · . . . · (a − k + 1) =

a!(k − a − 1)!(−1)

a−k+1

(−1)

a−k+1

a!(k−a−1)!

(−1)

a−k+1

k−1

(−1)

a+k+1

k−1

2. Niech każda z liczb a

, . . . , a

jest różna od 0. Wspomnianą wcześniej sumę iloczy-

nów możemy w tym przypadku przekształcić następująco

j=1

· . . . · a

j−1

· a

j+1

· . . . · a

j=1

· . . . · a

j−1

· a

j+1

· . . . · a

= a

· . . . · a

j=1

ROZDZIAŁ 6. Modele kombinatoryczne.

Stad dla naszego wielomianu

x+a

mamy:

a(a − 1) · . . . · (a − k + 1)

j=1

a − j + 1

a(a − 1) · . . . · (a − k + 1)

k−1

j=0

a − j

To kończy dowód twierdzenia.

Z powyższego twierdzenia wynika, że h przyporządkowuje wyrażeniu kombinatorycz-

nemu również wyrażenie komobinatoryczne.

Przykład.

(−1)

0+2+1

2−1

= −

x + 1

(−1)

1+4+1

4−1

= −

Przykład. Zastosujemy przekształcenie h dla kilku tożsamości kombinatorycznych.

k=1

x + n

− 1

n ∈ N x ∈ R

Zajmiemy się lewą stroną równości:

k=1

(−1)

k+1

k−1

k=1

(−1)

k+1

W konsekwencji otrzymalismy nową tożsamość kombinatoryczną:

k=1

(−1)

k+1

k=1

n ∈ N

k=1

x + k

x + n + 1

− 1,

n ∈ N,

x ∈ R

Stosując twierdzenie dla lewej strony równości otrzymujemy:

k=1

x + k

k=1

x + k

k=1

k−1

j=0

k − j

k=1

j=1

6.1. Inne problemy kombinatoryczne.

Podobnie przekształcamy stronę prawą:

x + n + 1

− 1

= h

x + n + 1

− h(1) =

n + 1

n−1

j=0

n + 1 − j

= (n + 1)

n+1

j=2

n ∈ N

Stąd otrzymujemy nową tożsamość

k=1

j=1

= (n + 1)

n+1

j=2

n ∈ N

(6.5)

Przykład. Zastosowanie tożsamości 6.5. Dla n = 5 nowo wyprowadzona równość przyj-

muje postać:

k=1

j=1

= 6

j=2

a stąd

1 +

= 6

ROZDZIAŁ 6. Modele kombinatoryczne.

Rozdział 7

Funkcje tworzące. ([2], [5], [6],
[7])

Definicja 7.0.1 Jeżeli A(s) =

∞
n=0

, a

∈ R; n ∈ N

, jest zbieżny dla |s| < s

funkcję A(s) nazywamy funkcją tworzącą ciągu {a

}

Wniosek. Jeżeli ciąg (a

) jest ograniczony, to powyższy szereg jest zbieżny co najmniej

dla |s| < 1.

Przykłady.

1. a

= 1

n ∈ N

⇒ A(s) =

1−s

2. a

= a

= 0

= 1

n  2 ⇒ A(s) =

1−s

3. a

n ∈ N

⇒ A(s) = e

4. Dla ustalonego k ∈ N, n ∈ 0, k

⇒ A(s) = (1 + s)

5. Jeżeli f oznacza liczbę oczek wyrzuconą przy rzucie symetryczną kostką do gry, to

rozkład prawdopodobieństwa zmiennej losowej f ma funkcję tworzącą:

s + s

+ . . . + s

1 − s

Niech f będzie zmienną losową o która przyjmuje wartości nieujemne i całkowite.

Oznaczymy:

P (f = n) = p

P (f > n) = q

n ∈ N

To wówczas:

= p

n+1

+ p

n+2

+ . . . =

∞

k=n+1

n  0

ROZDZIAŁ 7. Funkcje tworzące.

Funkcje tworzące ciągów (p

) i q

są następujące:

P (s) =

∞

n=0

Q(s) =

∞

n=0

Jednakże P (1) = 1, stąd szereg P (s) jest zbieżny bezwzględnie co najmniej dla |s| ¬ 1.
Współczynniki w Q

są ograniczone, stąd Q(s) jest zbieżny co najmniej dla |s| < 1.

Lemat 7.0.1 Dla −1 < s < 1 zachodzi wzór:

Q(s) =

1 − P (s)

1 − s

(7.1)

Dowód. W szeregu (1 − s)Q(s) współczynnik przy s

wynosi:

− q

n−1

= −p

n  1

= p

+ p

+ . . . = 1 − p

n = 0

i stąd:

(1 − s)Q(s) = 1 − P (s)

Badając pochodną:

(s) =

∞

n=0

n−1

zbieżne dla

|s| < 1

(7.2)

Dla s=1 P

(1) =

∞
n=1

= E(f ). Jeżeli istnieje ta wartość oczekiwana to P

(s) jest

ciągła dla |s| ¬ 1. Jeżeli dla s → 1 P

(s) → ∞ to mówimy, że f ma nieskończoną wartość

oczekiwaną P

(1) = E(f ) = ∞.

Twierdzenie 7.1 Wartość oczekiwana zmiennej losowej f o wartościach całkowitych
nieujemnych wyraża się wzorem:

E(f ) =

n=1

∞

n=0

= P

(1) = Q(1)

(7.3)

Dowód. Stosując do równania 7.1 twierdzenie o wartości średniej mamy:

Q(s) = P

(ϑ)

s < ϑ < 1

Q(s) % E(f )

s → 1

Stąd wynika wzór 7.3.

Przyjmijmy dla uproszczenia następującą definicję wariancji:

Definicja 7.1.1

(f ) = E(f

) − E

(f ) = E

(f − E(f ))

Różniczkując równanie 7.2 po s mamy:

(1) =

∞

n=1

n(n − 1)p

= E[f (f − 1)] = E(f

) − E(f )

(7.4)

Wyliczjąc z równania 7.1, 1 − P (s) = (1 − s)Q(s) i różniczkując, mamy:

(s) = Q(s) − (1 − s)Q

(s)

(s) = 2Q

(s) − (1 − s)Q

(s)

(1) = 2Q

(1)

Dla wyliczenia wariancji wystarczy dodać E(f ) − E

(f ), czyli z zależności 7.3 i 7.4

otrzymujemy:

(f ) = P

(1) + P

(1) − P

(1) = 2Q

(1) + Q(1) − Q

(1)

W przypadku nieskończonej wariancji P

(s) → ∞ dla s → 1.

Twierdzenie 7.2 Jeżeli niezależne zmienne losowe f

i f

mają funkcje tworzące od-

powienio P

(s) i P

(s), to zmienna losowa f = f

+ f

ma funkcję tworząca P (s) =

(s) · P

(s).

Dowód. Niech P (f

= n) = p

i P (f

= n) =

i n ∈ N, stąd

(s) =

∞

n=0

(s) =

∞

n=0

Zdarzenie (f

= j, f

= k) ma prawdopodobieństwo p

. Zdarzenie f = n jest sumą

zdarzeń rozłącznych.

[

t=0

= t, f

= n − t)

Stąd, prawdopodobieństwo

= P (f = n) =

t=0

n−t

(7.5)

Mnożąc wyraz po wyrazie P

i łącząc składniki przy jednakowych potęgach otrzymu-

jemy współczynnik c

przy s

w rozwinięciu P

(s)P

(s) dany wzorem 7.5. Czyli:

P (s) =

∞

n=0

= P

(s)P

(s)

Definicja 7.2.1 Kompozycja. Niech (a

), (b

) są ciągami, ciąg (c

) = (a

) · (b

) zdefi-

niowany wzorem 7.5 nazywamy kompozycją ciągów (a

) i (b

Wniosek. Kompozycja jest operacją łączną i przemienną.
Wniosek. Jeżeli zmienne f

, . . ., f

, mają jednakowy rozkład prawdopodobieństwa

) wówczas rozkład zmiennej f =

m
i=1

oznaczamy (p

)

∗

)

∗

= (p

)

(m−1)

∗

· (p

)

ROZDZIAŁ 7. Funkcje tworzące.

Przykład. Rozkład dwumianowy.

b(k, n, p) =

n−k

Funkcja tworząca:

P (s) =

k=0

(ps)

n−k

= (q + ps)

Z faktu, że funkcja tworząca rozkładu dwumianowego jest n-tą potęgą q+ps wynika, że

(b(k,n,p)) jest rozkładem sumy f = f

+ . . . + f

gdzie n to liczba niezależnych zmiennych

losowych o wspólnej tworzącej q + ps, każda ze zmiennych f

przyjmuje wartość 0 z

prawdopodobieństwem q oraz 1 z prawdopodobieństwem p. Stąd otrzymujemy:

Wniosek. Własność multiplikatywności:

(b(k, n, p)) = (b(k, 1, p))

∗

E(f ) = np

(f ) = npq

Rozdział 8

Grafy. ([1], [5], [8])

Definicja 8.0.2 Graf skierowany G składa się ze zbiorów W (G) i E(G) gdzie W (G) 6= ∅
oznacza zbiór wierzchołków grafu G, zaś E(G) zbiór krawędzi grafu G i funkcji δ. Ponadto
δ:E(G) −→ W (G) tak że, jeśli e ∈ E(G) czyli jest krawędzią grafu G, to δ(e) = (w

, w

gdzie w

nazywamy początkiem krawędzi grafu, zaś w

końcem krawędzi grafu. Mówimy też

że krawędź e wiedzie od w

do w

. Można dla uproszczenia przyjąć że, |W (G)|, |E(G)| <

∞.

Definicja 8.0.3 Wykres grafu skierowanego G, składa się z punktów odwzorowujących
wierzchołki W (G) oraz strzałek odwzorowujących skierowane krawędzie E(G), czyli wio-
dących od w

do w

Rysunek 8.1: Graf skierowany.

Uwaga. Nie ma krawędzi wielokrotnych! Funkcja δ:E(G) → W

(G) jest funkcja róż-

nowartościową.

ROZDZIAŁ 8. Grafy.

δ(E)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

, w

)

Tabela 8.1:

Definicja 8.0.4 Drogą w grafie skierowanym nazywamy uporządkowany ciąg krawędzi
(e

, e

, . . ., e

) taki, że jeśli δ(e

) = (w

, w

i+1

), to wtedy δ(e

i+1

) = (w

i+1

, w

i+2

) i ∈

1, n − 1, gdzie e

∈ E(G), w

∈ W (G), wówczas długość drogi określamy jako n gdy

wiedzie ona od wierzchołka w

do w

n+1

Drogę nazywamy zamkniętą, gdy w

= w

n+1

. Drogę zamkniętą długości n  1 z wierz-

chołkami (w

, w

, . . ., w

, w

) nazywamy cyklem jeśli w

6= w

dla i 6= j, i, j ∈ 1, n

Definicja 8.0.5 W grafie G wierzchołki x, y nazywamy sąsiednimi w sensie y sąsiaduje
z x, wtedy gdy istnieje e ∈ E(G) takie, że δ(e) = (x, y).

Definicja 8.0.6 R

⊂ W

(G) nazywamy relacją sąsiedztwa wtedy i tylko wtedy, gdy

∀

(x, y) ∈ R

y jest wierzchołkiem sąsiednim do x.

Uwaga. R

nie musi być ani zwrotna (wszystkie pętle) ani symetryczna.

Uwaga. Różne grafy skierowane mogą mieć tą samą relację sąsiedztwa.
Uwaga. Jeżeli grafy skierowane nie posiadają krawędzi wielokrotnych, to istnieje funk-

cja wzajemnie jednoznaczna przekształcająca grafy skierowane na relacje sąsiedztwa.

Definicja 8.0.7 Graf nieskierowany składa się z W (G) i E(G) oraz funkcji δ:E(G) −→
W

(G). Przy czym W (G) to zbiór wierzchołków, a E(G) zbiór krawędzi. Jeśli e

6= e

δ(e

) = δ(e

) to e

i e

nazywamy krawędziami wielokrotnymi.

Wykres grafu składa się z punktów odwzorowujących wierzchołki W (G) i łuków odwzo-
rowujących krawędzie E(G).

Drogę nazywamy prostą, jeżeli wszystkie jej krawędzie są różne. e

6= e

, i 6= j i, j ∈

1, n.

Uwaga. W drodze prostej mogą wystąpić wielokrotne wierzchołki.
Graf nie zawierający cykli w sensie teoriomnogościowym nazywamy grafem acyklicz-

nym.

Definicja 8.0.8 Podgrafem G

,δ

) grafu G (W ,E,δ) nazywamy taki graf, że

W (G

) ⊂ W (G), E(G

) ⊂ E(G) δ |

E(G)

≡ δ

Drogę nazywamy acykliczną, gdy podgraf składający się z wierzchołków W i krawędzi E
tej drogi jest acykliczny.

Przykład. Droga e

z ciągiem wierzchołków jest droga zamkniętą i nie jest drogą

Rysunek 8.2: Graf G

prostą. Nie jest także cyklem. Graf G

jest acykliczny.

Przykład. Droga e

o długości 4 jest drogą zamkniętą i jest drogą prostą. Graf

Rysunek 8.3: Graf G

zawiera dwa cykle.

Twierdzenie 8.1 Każda droga zamknięta e

. . . e

o długości większej niż 3, taka że

6= w

, i 6= j i, j ∈ 1, n jest cyklem.

Dowód. Rozważmy drogę zamkniętą. Wystarczy wykazać, że e

6= e

dla i 6= j, lecz

kiedy w

= w

, to droga e

. . . e

n−1

jest drogą prostą, czyli e

6= e

dla i 6= j i, j ∈

1, n − 1 ponadto δ(e

) = {w

, w

} oraz δ(e

) = {w

, w

i+1

} i ∈ 1, n − 1 to e

6= e

i ∈ 1, n − 1. Stąd droga e

. . . e

jest drogą prostą.

Twierdzenie 8.2 Droga e

. . . e

o wierzchołkach w

. . . w

n+1

jest prosta i acyklicz-

na, wtedy i tylko wtedy, gdy w

6= w

i 6= j, i, j ∈ 1, n + 1.

Dowód. ⇐ Rozważmy drogę która ma wszystkie wierzchołki różne, analogicznie jak w

dowodzie twierdzenia 8.1. Jest to droga prosta. W cyklu, jeden z wierzchołków musi być
początkiem jednej i końcem innej krawędzi, więc musi się powtórzyć. Jeśli wierzchołki się
nie powtarzają, są różne, to droga jest acykliczna.

⇒ Załóżmy przez zaprzeczenie, że w ciągu wierzchołków w

. . . w

n+1

występują

powtórzenia, na przykład w

= w

dla i < j i, j ∈ 1, n + 1. Z zasady dobrego upo-

rządkowania, istnieje minimalne j spełniające ten warunek. Wówczas ciąg wierzchołków
w

. . . w

j−1

spełnia warunek w

6= w

k 6= l k, l ∈ i, j − 1. Stąd droga w

i+1

. . . w

j−1

jest cyklem, co daje sprzeczność bo droga w

. . . w

n+1

była acykliczna.

Twierdzenie 8.3 Jeśli w, v ∈ W (G); w 6= v i istnieje w grafie G droga wiodąca z w do
v, to istnieje w tym grafie acykliczna droga wiodąca z w do v.

ROZDZIAŁ 8. Grafy.

Dowód. Ze zbioru wszystkich dróg wiodących z w do v w grafie G, wybieramy naj-

krótszą drogę o długości którą oznaczamy n i ciąg jej wierzchołków w

. . . w

n+1

; gdzie

= w a w

n+1

= v. Gdyby wierzchołki w

6= w

i 6= j i, j ∈ 1, n + 1 to droga byłaby pro-

sta i acykliczna z konstrukcji, gdyby zaś ∃i < j w

= w

i, j ∈ 1, n + 1 to droga wiodąca

od w

do w

i+1

. . . w

jest zamknięta. Konstruujemy drogę w

. . . w

j+1

. . . w

n+1

która wiedzie z w do v i jej długość jest mniejsza od n, co daje sprzeczność i wierzchołki
są różne.

Wniosek. Jeśli e ∈ E(G) i e jest krawędzią w zamkniętej drodze prostej w grafie G, to

istnieje cykl do którego należy ta krawędź.

Dowód. Jeśli e

jest pętlą mamy przypadek trywialny. Jeśli nie, to weźmy δ(e

) =

{w, v} w 6= v i rozważmy graf G

z krawędziami E(G) − {e

}, który jest podgrafem

grafu G. Z zamkniętości drogi w grafie G, w grafie G

istnieje droga wiodąca z w do v. Z

twierdzenia 8.3 wynika, że istnieje prosta droga acykliczna wiodąca z w do v. Zawierająca
oczywiście e

. Połączenie wierzchołków końcowych tej drogi krawędzią e

, tworzy cykl

zawierający wierzchołki w i v.

Rozdział 9

Izomorfizmy grafów. ([1])

Twierdzenie 9.1 Jeżeli w 6= v ∈ W (G), gdzie G jest grafem acylkicznym, to istnieje co
najwyżej jedna droga prosta w G wiodąca z w do v.

Dowód. Zaprzeczymy tezie twierdzenia. Niech istnieje para wierzchołków w, v ∈ W (G)

połączona co najmniej dwiema drogami prostymi z w do v. Przy czym można przyjąć,
że jedna z takich dróg jest najkrótsza dla wszystkich par (w, v) spełniających warunek
posiadania co najmniej dwóch różnych dróg prostych. Wtedy albo zbiór wspólnych wierz-
chołków tych dróg składa się jedynie z {w, v} i wówczas mamy sprzeczność z acyklicznością
grafu G, gdyż droga w . . . v . . . w złożona z tych dwóch dróg jest cyklem, lub te dwie drogi
mają poza {w, v} jeszcze co najmniej jeden wspólny wierzchołek. Oznaczmy go ω ∈ W (G),
wówczas możemy skonstruować dwie różne drogi proste wiodące z w do ω lub z ω do v,
co daje sprzeczność z minimum długości drogi z w do v.

Przykład. Droga w

będąca połączeniem (sumą) dróg w

, w

jest cy-

Rysunek 9.1:

klem. Podobną konstrukcję otrzymujemy dla drogi w

, która wiedzie z w

, utworzonej jako suma dróg z w

do w

i z w

do w

. Drogi w

oraz

są proste i wiodą z w

do w

. Łącząc części tych dróg, jednej z w

do w

a drugiej z w

do w

, można utworzyć cykl w

ROZDZIAŁ 9. Izomorfizmy grafów.

Definicja 9.1.1 Izomorfizm grafów bez krawędzi wielokrotnych. Mówimy, że grafy G i Q
są izomorficzne jeżeli istnieje wzajemnie jednoznaczne przekształcenie

H:W (G) → W (Q)

takie, że {w, v} jest krawędzią grafu G, wtedy i tylko wtedy, gdy {

H(w), H(v)} jest kra-

wędzią grafu Q. Przekształcenie

H nazywamy izomorfizmem grafów G i Q, zapisujemy

G ' Q jeżeli G jest izomorficzny z Q. Oczywiście Q jest wtedy izomorficzny z G. Izomor-
fizmem jest

−1

Dla grafów z krawędziami wielokrotnymi zakładamy, że istnieją wzajemnie jednoznaczne
przekształcenia

H:W (G) → W (Q) i Γ:E(G) → E(Q) takie, że dla dowolnej krawędzi

e ∈ E(G), łączy ona wierzchołki w, v ∈ W (G) wtedy i tylko wtedy, gdy odpowiednia
krawędź Γ(e) łączy wierzchołki

H(w) i H(v). Czyli modele ikonograficzne dwóch grafów

izomorficznych pokrywają się z dokładnością do oznaczeń.

Przykład. Izomorfizm G i Q.

H(x

) = y

; i ∈ 1, 11.

Rysunek 9.2: Grafy G i Q.

Uwaga. Identyfikacja grafów wymaga przeliczenia ich wierzchołków i krawędzi. Dwa

grafy izomorficzne posiadają identyczną liczbą wierzchołków i krawędzi.

Niezmienniki izomorfizmu grafów to na przykład:

• liczba wierzchołków

• liczba krawędzi

• liczba pętli

• liczba dróg prostych o przyjętej długości

• liczba punktów wielokrotnych

Definicja 9.1.2 Stopniem wierzchołka w ∈ W (G) nazywamy sumę liczby różnych kra-
wędzi {v, w} v 6= w (dla grafów o skończonej liczbie wierzchołków) oraz podwojonej liczby
pętli o wierzchołku w. Oznaczamy ten stopień deg(W ).

Liczbę wierzchołków stopnia n ∈ N

w grafie G oznaczamy D

(G). Jest to również nie-

zmiennik izomorfizmu

Wniosek. Ciąg liczb wierzchołków (D

(G))

i∈0,n

max

jest niezmiennikiem izomorfizmu

Przykład. Dla grafu G

mamy (D

)) = (0, 0, 3, 4), (D

)) = (0, 3, 0, 4 ,3) przy

i ∈ 0, n

max

Rysunek 9.3: Graf G

Rysunek 9.4: Graf G

ROZDZIAŁ 9. Izomorfizmy grafów.

Rozdział 10

Własności grafów. ([2], [4], [5],
[8])

Graf nazywamy regularnym jeżeli wszystkie jego wierzchołki posiadają identyczny stopień.

Rysunek 10.1: Grafy regularne.

Graf nazywamy pełnym, jeżeli wszystkie jego wierzchołki są połączone ze wszystkimi

innymi oraz nie posiadają pętli i krawędzi wielokrotnych, oznaczamy je

Uwaga. W grafie pełnym posiadającym n wierzchołków każdy wierzchołek ma stopnień

(n − 1). Grafy pełne o tej samej liczbie wierzchołków są ze sobą izomorficzne.

Uwaga. Graf pełny

zawiera

grafów izomorficznych z

, m ¬ n. Grafy te

powstają przez wybór różnych m wierzchołków z n możliwych i wszystkich krawędzi je
łączących.

Uwaga. Dowolny graf bez pętli i krawędzi wielokrotnych posiadający n wierzchołków

jest izomorficzny z podgrafem grafu

Twierdzenie 10.1 Suma stopni wierzchołków grafu jest równa podwojonej liczbie jego

ROZDZIAŁ 10. Własności grafów.

Rysunek 10.2: Grafy pełne.

Rysunek 10.3: Grafy regularne niepełne.

krawędzi. Czyli:

w∈W (G)

deg(w) = 2|E(G)| = 2

e∈E(G)

(10.1)

ponadto,

max

i=0

(G) = 2|E(G)|

(10.2)

Dowód 10.1. Wszystkie krawędzie nie będące pętlami łączą dwa wierzchołki, czyli

uwzględnienie takiej krawędzi zwiększa sumę stopni wierzchołków o 2. Z definicji 9.1.2
stopnia wierzchołka otrzymujemy to również dla pętli.

Dowód 10.2. Sumując stopnie wszystkich wierzchołków łatwo zauważyć, że wszystkie

wierzchołki stopnia i dają wkład iD

(G), gdyż tyle krawędzi lub krawędzi i podwojoną

liczbę pętli dokłada jeden wierzchołek.

10.1

Drogi a krawędzie. Drogi wewnątrz grafu.

Przykład. Problem mostów Królewieckich.

Czy można skonstruować drogę tak by po

każdym moście przejść tylko raz i powrócić do punktu wyjścia? Inaczej, czy istnieje droga
zamknięta w tym grafie, przechodząca przez każdą krawędź dokładnie jeden raz?

Drogę tego typu określa się jako cykl Eulera w grafie G. Drogą Eulera w grafie G,

nazywamy drogę prostą zawierającą wszystkie krawędzie grafu G.

Twierdzenie 10.2 Wszystkie wierzchołki grafu który zawiera cykl Eulera są stopnia pa-
rzystego.

10.1. Drogi a krawędzie. Drogi wewnątrz grafu.

Rysunek 10.4: Mosty w Królewcu.

Rysunek 10.5: Graf odpowiadający połączeniom mostów.

Dowód. Przebiegając drogę wychodzącą z ustalonego wierzchołka, eliminujemy kra-

wędzie dochodzącą i wychodzącą z kolejnych osiąganych po drodze wierzchołków lub też
eliminując pętle. Każda krawędź ma być osiągana tylko raz i zostaje wyeliminowana po-
nieważ droga jest cyklem więc nie pozostanie żadna krawędź i po eliminacji zostają same
wierzchołki. Tak więc, mają one stopień 0. Każde przejście przez wierzchołek odpowia-
da zmniejszeniu jego stopnia o 2 (lub wielokrotność, jeśli eliminujemy pętle), stąd na
początku wszystkie wierzchołki musiały mieć parzystość stopnia deg(w

) = (0 + 2n

∈ W (G).

Wniosek. Graf G posiadający drogę Eulera ma wszystkie wierzchołki stopnia parzy-

stego, albo dokładnie dwa z nich są stopnia nieparzystego.

Dowód. Niech droga Eulera dla grafu G rozpoczyna się w wierzchołku w i kończy w

wierzchołku v, wówczas:

• w = v i z twierdzenia 10.2 droga jest cyklem Eulera, to stopień wszystkich wierz-

chołków jest parzysty.

• w 6= v to konstruujemy krawędź e wiodącą z w do v. Wówczas nadgraf G

= G ∪

{e} posiada cykl Eulera będący sumą drogi Eulera i krawędzi e. Stąd wszystkie
wierzchołki grafu G

są stopnia parzystego, więc jedynie w, v dla grafu G są stopnia

nieparzystego.

Przykład. Graf G

nie posiada cyklu Eulera gdyż 2 - deg(w

), deg(w

), natomiast

ROZDZIAŁ 10. Własności grafów.

Rysunek 10.6: Graf G

droga e

jest drogą Eulera.

Rysunek 10.7: Graf G

Graf G

jest sumą dwóch rozłącznych podgrafów które posiadają cykle Eulera.

Definicja 10.2.1 Graf G nazywamy spójnym, gdy dla dowolnej pary w, v ∈ W (G) w 6= v
istnieje droga wiodąca z w do v w tym grafie.

Definicja 10.2.2 Każdy maksymalny spójny podgraf grafu G nazywamy składową grafu
G.

Uwaga. Składowa z zadanym wierzchołkiem w zawiera wszystkie drogi (w tym wierz-

chołki i krawędzie) zaczynające się w wierzchołku w.

Przykład. Graf G

ma dwie składowe.

Twierdzenie 10.3 (Euler) Dowolny skończony spójny graf, którego wszystkie wierz-
chołki są stopnia parzystego posiada cykl Eulera.

Dowód. Niech G będzie skończonym grafem spójnym który posiada wszystkie wierz-

chołki stopnia parzystego. Jeżeli W (G) = {w

} to przebiegamy wszystkie pętle (jeżeli

są); niech więc |W (G) > 1|, ze spójności G mamy ∀i w

∈ W (G), deg(w

) = 2n

konstruujemy w

. . . w

jako ciąg drogi o maksymalnej długości która nie powtarza

żadnej krawędzi. Z założenia o skończoności ciągu |E(G)| < ∞ to istnieje co najmniej

10.1. Drogi a krawędzie. Drogi wewnątrz grafu.

jedna taka droga. Tworzymy ciąg podgrafów eliminując po kolei krawędzie tej drogi jeżeli
w zbiorze {w

, . . ., w

n−1

} wystąpił wierzchołek w

, to każde jego przekroczenie wiąże

się z eliminacją dwóch krawędzi, czyli zmniejsza stopień wierzchołka w

w odpowiednim

podgrafie o 2. Eliminując ostatnią krawędź wiodącą od w

n−1

do w

zmniejszymy stopień

wierzchołka w

o 1. Gdyby w

6= w

to stopień w

byłby nieparzysty, czyli istniałaby kra-

wędź wychodząca z w

, co jest sprzeczne z maksymalnością długości dróg, stąd w

= w

Gdyby najdłuższa droga nie przechodziła przez wszystkie wierzchołki grafu G, to ze spój-
ności grafu G istnieje krawędź e nie zawarta w drodze wiodącej od w

do w

łączącą jakiś

wierzchołek w

∈ {w

, . . ., w

} z w

6∈ {w

, . . ., w

}. Teraz najdłuższa droga wiodąca

z w

do w

ma długość n (istnieje bo w

= w

), może być przedłużona poprzez do-

łączenie początkowej krawędzi e, co zwiększa długość maksymalnej drogi, co oczywiście
jest sprzeczne z założeniem. Analogicznie, do najdłuższej drogi możemy zawsze dołączyć
krawędź e pominiętą w jej konstrukcji, gdyż musi łączyć wierzchołki zawarte w tej drodze,
(w

, w

) co znów daje sprzeczność z maksymalnością długości drogi.

Wniosek. Jeżeli graf G jest skończony, spójny i posiada dokładnie dwa wierzchołki

stopnia nieparzystego, to posiada drogę Eulera.

Dowód. Jeżeli w 6= v, w, v ∈ W (G), 2 - deg(w), 2 - deg(v) to konstruujemy krawędź

łączącą w z v. Wówczas nadgraf G

= G ∪ {e} cechuje się parzystością wszystkich wierz-

chołków, stąd z twierdzenia 10.3 posiada cykl Eulera. Po eliminacji krawędzi e z cyklu
Eulera, pozostaje droga Eulera zawarta w grafie G.

Definicja 10.3.1 Drzewem nazywamy dowolny acykliczny i spójny graf.

Rysunek 10.8: Drzewa.

Definicja 10.3.2 Podgraf T G nazywamy drzewem spinającym grafu G, jeśli W (T ) =
W (G).

Liśćmi nazywamy wierzchołki stopnia 1 w drzewie. Na rysunku 10.9 są to dla T

: w

, w

, w T

: w

, w

, w T

: w

, w

ROZDZIAŁ 10. Własności grafów.

Rysunek 10.9: Drzewa spinające.

Rozdział 11

Zasada włączania - wyłączania.
([1], [5])

Podane tu twierdzenie będzie szczególnym przypadkiem ogólniejszego twierdzenia mate-
matyki dyskretnej zwanego Zasadą włączania - wyłączania. Zasada ta, jako swoisty ogólny
model matematyczny, zostanie następnie zaaplikowana na gruncie rachunku prawdopo-
dobieństwa do wzoru na obliczanie prawdopodobieństwa sumy zdarzeń, a w dalszej części
do rozwiązania konkretnego problemu z rachunku prawdopodobieństwa.

Twierdzenie 11.1 Dla dowolnych zbiorów A

, A

, . . . , A

zachodzi:

∪ . . . ∪ A

| =

r=1

(−1)

r+1

1¬i

<...<i

¬n

∩ . . . ∩ A

| =

i=1

| −

1¬i

¬n

∪ A

| +

1¬i

¬n

∪ A

. . . + (−1)

n+1

∪ . . . ∪ A

(11.1)

W oparciu o zasadę włączania - wyłączania łatwo udowodnić poniższe twierdzenie ra-
chunku prawdopodobieństwa.

Twierdzenie 11.2 (Wzór Poincare’go) Prawdopodobieństwo zajścia jednego ze zda-
rzeń A

, A

, . . . , A

, A

∈ Ω, wynosi:

P (A

∪ . . . ∪ A

) =

r=1

(−1)

r+1

1¬i

<...<i

¬n

P (A

∩ . . . ∩ A

) =

i=1

P (A

) −

1¬i

¬n

P (A

∩ A

1¬i

¬n

P (A

∩ A

) + . . . + (−1)

n+1

P (A

∪ . . . ∪ A

)

(11.2)

Rozważmy teraz następujące zdanie: Do pociągu złożonego z n wagonów wsiada N

pasażerów (n ¬ N ). Wyznaczyć prawdopodobieństwo zdarzenia że żaden wagon nie będzie
pusty.

ROZDZIAŁ 11. Zasada włączania - wyłączania.

Rozwiązanie. Za przestrzeń zdarzeń elementarnych Ω weźmy zbiór wszystkich N -

wyrazowych wariacji z powtórzeniami zbioru n-elementowego. Zatem |Ω| = n

. Niech

zdarzenie B polega na tym, że żaden wagon nie będzie pusty. Niech A

gdzie 1 ¬ i ¬ n,

będzie zdarzeniem polegającym na tym, że wagon o numerze i będzie pusty. Oznaczmy
ponadto zdarzenie A jako sumę zdarzeń A

, czyli A = A

∪ . . . ∪ A

. Zdarzenie A polega

więc na tym, że po zajęciu miejsc przez pasażerów w pociągu pozostaną puste wago-
ny. Interesujące nas w zadaniu zdarzenie B jest zdarzeniem przeciwnym do zdarzenia A,
zatem |B| = |Ω| − |A|. Z zasady włączania-wyłączania obliczymy moc zbioru zdarzeń
elementarnych sprzyjających zdarzeniu A:

|A| = |A

∪ . . . ∪ A

| =

r=1

(−1)

r+1

1¬i

<...<i

¬n

∩ . . . ∩ A

| =

r=1

(−1)

r+1

(n − r)

Wobec tego:

|B| = n

−

r=1

(−1)

r+1

(n − r)

r=1

(−1)

(n − r)

r=0

(−1)

r+1

(n − r)

Ostatecznie:

P (B) =

|B|

|Ω|

n
r=0

(−1)

r+1 n

(n − r)

r=0

(−1)

r+1

(

n − r

)

(11.3)

Rozdział 12

Zasada Dirichleta. ([12], [15],
[22], [23])

W tym rozdziale przedstawię twierdzenie nazywane zasadą szufladkową Dirichleta. Ma
ono charakter kombinatoryczny i przy bardzo prostym sformułowaniu prowadzi do cieka-
wych i niebanalnych wniosków, ułatwia rozwiązywanie wielu trudnych zadań. Sformuło-
waną przez siebie zasadę szufladkową, Dirichlet z powodzeniem stosował w rozważaniach
dotyczących przybliżeń diofanycznych (tzn. przybliżania liczb niewymiernych liczbami
wymiernymi). Prawdopodobnie po raz pierwszy użył tej zasady w dowodzie twierdzenia
z 1842 roku:

∀a ∈ R ∀n ∈ N

n > 1 ⇒ ∃p ∈ Z∃q ∈ N

q ¬

n ∧ |pa − q| <

(12.1)

12.1

Teoretyczne podstawy metody.

Zasada szufladkowa Dirichleta bywa często istotnym elementem wielu zaawansowanych
rozumowań w różnych dziedzinach matematyki. Formalnie wiąże się ona z pojęciem mocy
zbioru (liczby kardynalnej) i zbioru skończonego w sensie Dedekinda.

Twierdzenie 12.1 (zasada szufladkowa) Jeżeli |X| > n oraz X = X

∪ X

∪ . . . ∪ X

to dla pewnego i ∈ {1 , 2, . . ., n} jest |X

| > 1.

Dowód. Dowód zostanie przeprowadzony metodą indukcji matematycznej. Dla n = 1

twierdzenie jest prawdziwe. Zakładamy jego prawdziwość dla pewnej liczby naturalnej
k > 1:

X = X

∪ X

∪ . . . ∪ X

|X| > k ⇒ ∃i ¬ k

| > 2

Pokażemy teraz, że jest ono prawdziwe dla liczby k + 1, czyli:

X = X

∪ X

∪ . . . ∪ X

k+1

|X| > k + 1 ⇒ ∃i ¬ k + 1

| > 2

Jeżeli X

k+1

= ∅, to twierdzenie jest prawdziwe na mocy przyjętego założenia. Jeżeli

k+1

= 1, to zbiór X

∪ X

∪ . . . ∪ X

ma więcej niż k elementów i na mocy założenia

indukcyjnego jest |X

|  2 dla pewnego i ¬ k. Jeżeli w końcu |X

k+1

|  2, to teza

jest spełniona dla i = k + 1. Zatem na mocy indukcji matematycznej twierdzenie jest
prawdziwe dla wszystkich liczb naturalnych.

Uogólnieniem zasady szufladkowej Dirichleta jest

ROZDZIAŁ 12. Zasada Dirichleta.

Twierdzenie 12.2 (zasada podziałowa) Niech q

, q

, . . . , q

będzie ciągiem liczb na-

turalnych. Jeśli X = X

∪ X

∪ . . . ∪ X

oraz |X|  (

n
i=1

) − n + 1, to |X

| q

dla

pewnego i ∈ {1 , . . ., n}.

Inne sformułowanie zasady szufladkowej używa pojęcia funkcji:

Twierdzenie 12.3 Jeżeli A i B są zbiorami skończonymi, takimi że |A| > |B| (liczba
elementów zbioru A jest większa od liczby elementów zbioru B), zaś f :A → B jest funkcją
przekształcającą zbiór A w zbiór B, wtedy istnieją takie różne elementy a, b ∈ A, że
f (a) = f (b).

W tym ujęciu zasada szufladkowa wyraża więc fakt, że nie istnieje funkcja różnowarto-

ściowa (wariacja bez powtórzeń) ze zbioru o większej liczbie elementów. Szufladami stają
się tutaj tzw. warstwice funkcji f , czyli przeciwobrazy jednoelementowych podzbiorów
zbioru A.

W języku potocznym zasadę szufladkową formułuje się następująco:

Twierdzenie 12.4 Jeżeli rozmieścimy n kul w m szufladach, przy czym n > m to w
pewnej szufladzie znajdą się co najmniej dwie kule.

W postaci ogólniejszej zasada szufladkowa mówi, że:

Twierdzenie 12.5 Jeżeli rozmieścimy n kul w m szufladach, przy czym n > km dla
pewnej liczby naturalnej k, to w pewnej szufladzie znajdzie się co najmniej k + 1 kul.

Czasem łatwiejsza w użyciu jest następująca wersja tejże zasady:

Twierdzenie 12.6 Jeżeli rozmieścimy km+1 kul w m szufladach, to w pewnej szufladzie
znajdzie się co najmniej k + 1 kul.

Stąd na mocy tej zasady stwierdzamy na przykład, że:

• jeżeli z 3 samochodów wysiadło 10 osób, to pewnym samochodem przyjechały co

najmniej 4 osoby;

• wśród 13 liczb naturalnych jest co najmniej 7 jednakowej parzystości oraz co naj-

mniej dwie, których różnica jest podzielna przez 12;

• w klasie 25-osobowej znajdziemy co najmniej troje uczniów urodzonych w tym sa-

mym w tym samym miejscu, itd.

Podane przykłady pokazują, jak prosta jest sama zasada szufladkowa Dirichleta, ale

jak dalej zostanie pokazane może ona mieć nietrywialne zastosowania w matematyce.

W matematyce formułuje się także „nieskończoną” postać zasady szufladkowej:

Twierdzenie 12.7 Jeśli rozmieścimy nieskończenie wiele kul w skończonej ilości szuflad,
to w pewnej szufladzie znajdzie się nieskończenie wiele kul.

Na gruncie arytmetyki liczb naturalnych można zasadzie Dirichleta nadać czysto arytme-
tyczne sformułowanie:

Twierdzenie 12.8 Funkcja o wartościach mniejszych od k, dla k argumentów, musi mieć
co najmniej dwie wartości jednakowe, tzn.

∀n ¬ k

F (n) < k ⇒ ∃ l, m ¬ k

l 6= m ∧ F (m) = F (l)

(12.2)

12.2. Zastosowanie metody modelowania w zadaniach.

Kontrapozycja powyższego arytmetycznego sformułowania zasady Dirichleta ma postać:

∀x, y ¬ k

F (x) = F (y) ⇒ x = y

⇒ ∃x ¬ k F (x)  k

(12.3)

Tak sformułowane twierdzenie o szufladkowaniu przez kontrapozycję opisuje pewną wła-
sność funkcji wzajemnie jednoznacznych.

W arytmetyce teoretycznej udowadnia się nim następujące metatwierdzenie:

Twierdzenie 12.9 Zasada szufladkowa Dirichleta i kontrapozycja zasady Dirichleta są
równoważne zasadzie indukcji.

Oczywiście wszystkie podane wyżej sformułowania zasady szufladkowej są równoważne,
co służy jej wszechstronnym zastosowaniom i aplikacjom.

Na koniec zauważmy jeszcze, że terminologia polska nie jest jednolita: zasadę szu-

fladkową (niem. Dirichletsche Schubfachprinzip) nazywa się także zasadą pudełkową; w
literaturze angielskiej bywa ona nazywana pigeon hole principle (tzn. zasadą gniazd go-
łębich), mówi się tam bowiem o rozmieszczeniu n gołębi w k gniazdach.

12.2

Zastosowanie metody modelowania w zadaniach.

Można powiedzieć, że zasada szufladkowa jest „wytrychem” załatwiającym wiele tech-
nicznych kłopotów przy rozwiązywaniu zadań. Podobny schemat rozmieszczania kul w
szufladach przyjeliśmy w modelowaniu kombonatorycznym. Jednocześnie jednak przy roz-
wiązywaniu zadań, w których moglibyśmy zastosować tę zasadę, najtrudniej jest stwier-
dzić czym w zadaniu są „kule”, a czym „szuflady”. Należy przy tym uzmysłowić sobie, w
jaki sposób będziemy rozmieszczać kule w szufladach. Inaczej mówiąc należy zdefiniować
zbiory A i B oraz funkcję f :A → B w taki sposób, by równość f (a) = f (b) (występująca
w twierdzeniu 12.3) dawała rozwiązanie zadania. W ten sposób dokonujemy transformacji
od modelu logicznego do modelu matematycznego. Transformacje tę nazywamy właśnie
modelowaniem.

W zadaniach o podzielności liczb rolę kul spełniać mogą reszty z dzielenia liczb na-

turalnych przez ustaloną liczbę p. Rolę szuflad spełniają wówczas liczby 1, 2, . . ., p − 1.
Zasada Dirichleta przybiera wtedy następującą postać:

Twierdzenie 12.10 Jeśli zbiór M zawiera p − 1 różnych liczb naturalnych, które nie są
podzielne przez p i różnica dowolnych dwóch spośród tych liczb nie jest podzielna przez p,
to zbiór reszt z dzielenia przez p liczb zbioru M jest równy {1 , 2, . . ., p − 1}.

W niektórych (na ogól trudnych) zadaniach, zasadę Dirichleta stosuje się kilkakrotnie,

wyodrębniając najpierw grupę obiektów, które spełniają tylko część żądanych warunków,
a następnie wybierając z tej grupy obiekt spełniający wszystkie warunki.

Zauważmy jednak, że dowody oparte o zasadę Dirichleta mają w pewnym sensie cha-

rakter egzystencjalny, gdyż nie wskazują obiektów, których istnienia się dowodzi. Jest to
charakterystyczna cecha dla zastosowań tejże zasady.

W niniejszym podrozdziale zaprezentuję atrakcyjność i możliwości, jakie daje metoda

modelowania matematycznego oparta o zasadę szufladkową Dirichleta w zastosowaniach
dydaktycznych. Dokonam tego przedstawiając konkretne problemy zadaniowe i ich roz-
wiązania.

Przykład. Wykazać że w Warszawie mieszkają dwie osoby, mające tę samą liczbę

włosów na głowie.

ROZDZIAŁ 12. Zasada Dirichleta.

Rozwiązanie. Liczba włosów na głowie człowieka nie przekracza 1000000. Ponumeruj-

my szuflady liczbami od 0 do 1000000 (jest ich 1000001) i przyporządkujmy każdemu
mieszkańcowi Warszawy tę szufladę, której numer wskazuje liczbę włosów na jego głowie.
Ponieważ Warszawa liczy ponad 1000000 mieszkańców, więc na mocy zasady Dirichleta
przynajmniej dwie osoby spośród nich mają tę samą liczbę włosów na głowie.

Przykład. W sali znajduje się k osób, k  2. Udowodnić, że co najmniej dwie z tych

osób mają wśród obecnych tę samą liczbę znajomych. Przyjmujemy, że jeżeli osoba A zna
osobę B, to również B zna A.

Rozwiązanie. Niech f (A) będzie liczbą osób na sali, które zna osoba A. Oczywiście

0 ¬ f (A) ¬ k − 1. Nie jest jednak możliwe, by funkcja f przyjmowała zarówno wartość
0, jak i k − 1. Byłaby bowiem osoba X, nie mająca znajomych na sali (f (X) = 0) i osoba
Y , znająca wszystkie pozostałe osoby (f (Y ) = k − 1), a więc i osobę X. Sprzeczność.
Zatem funkcja f przeprowadza k-elementowy zbiór X w zbiór (k − 1)-elementowy {0 , 1,
. . ., k − 2} lub {1 , 2, . . ., k − 1}. Nie jest więc ona różnowartościowa, tzn. istnieją dwie
osoby K i L, dla których f (K) = f (L), czyli mające tę samą liczbę znajomych w sali.

Przykład. Okrągły stół udekorowano proporczykami n różnych krajów w taki sposób,

że przy każdym nakryciu umieszczono jeden proporczyk. Przy stole siedzi n ambasadorów
z tych krajów, przy czym żaden z nich nie siedzi przy proporczyku swego kraju. Wykazać,
że można stół obrócić o taki kąt, że po obrocie co najmniej dwóch ambasadorów będzie
siedziało przy właściwym proporczyku.

Rozwiązanie. Istnieje n − 1 obrotów stołu, po których wzajemne położenie proporczy-

ków i ambasadorów zmieni się. Każdemu ambasadorowi przyporządkowujemy ten obrót,
po którym znajdzie się on przy proporczyku swojego kraju. Ambasadorów utożsamiamy
z kulami, natomiast obroty z szufladami. Zgodnie z zasadą Dirichleta istnieje przynaj-
mniej jeden taki obrót, po którym dwóch (a może nawet więcej) posłów znajdzie się przy
właściwych proporczykach.

Przykład. Dany jest zbiór złożony z dziesięciu liczb naturalnych dwucyfrowych w

rozwinięciu dziesiętnym. Dowieść, że w tym zbiorze istnieją dwa niepuste podzbiory takie,
że sumy liczb obu podzbiorów są równe.

Rozwiązanie. Przyporządkowujemy elementowi a

liczbę naturalną będącą maksymal-

ną długością ciągu rosnącego, jaki można utworzyć bez zmiany kolejności elementów a

. . ., a

. Jeśli jakiemuś elementowi przyporządkowaliśmy liczbę większą od 10, to zadanie

jest rozwiązane. Jeśli nie, to podzielmy ciąg a

, a

, . . ., a

101

na 10 podciągów, zaliczając

do i-tego podciągu te liczby, którym przyporządkowano i. Podciągi traktujemy jako „szu-
flady” (mamy więc 10 szuflad), natomiast elementy i-tego podciągu jako kule wrzucone
do i-tej szuflady. Problem sprowadza się do rozmieszczenia 101 kul w 10 szufladach. Na
mocy uogólnionej zasady szufladkowej pewien podciąg (szuflada) ma więc co najmniej 11
elementów.

Przykład. Danych jest 11 liczb rzeczywistych. Udowodnić, że co najmniej dwie spo-

śród nich mają rozwinięcia dziesiętne pokrywające się w nieskończonej ilości miejsc po
przecinku. (Jeśli liczba ma skończone rozwinięcie dziesiętne, to uzupełniamy je zerami.)

Rozwiązanie. Przypuśćmy dla dowodu nie wprost, że każda para rozważanych liczb

pokrywa się na skończonej ilości miejsc po przecinku. Par tych liczb jest również skończenie
wiele

= 55. Zatem dla dostatecznie dużej liczby naturalnej n, na n-tym miejscu

po przecinku żadna para nie może się pokrywać. To jednak jest niemożliwe, liczb (kul)
mamy 11, cyfr (szuflad) 10, więc, na mocy zasady szufladkowej Dirichleta, pewne dwie
liczby pokrywają się na n-tym miejscu po przecinku. Uzyskana sprzeczność dowodzi tezy
zadania.

12.2. Zastosowanie metody modelowania w zadaniach.

Przykład. Wykazać, że w trójkącie równobocznym o boku 4, nie można umieścić 17

punktów tak, by odległość dwóch z nich była większa niż 1.

Rozwiązanie. Wykorzystujemy następującą własność trójkąta, odległość dowolnych

dwóch punktów leżących w trójkącie, nie przekracza długości jego największego boku.
Każdy bok naszego trójkąta dzielimy na cztery odcinki równej długości. Przez punkty
podziału prowadzimy proste równoległe do boków trójkąta. W ten sposób uzyskujemy
podział wyjściowego trójkąta na 16 trójkątów o boku 1. Gdy rozmieścimy w nich 17
punktów, to zgodnie z zasada szufladkową dwa z nich znajdą się w tym samym trójkącie
o boku 1, a więc ich odległość będzie nie większa niż 1.

Rysunek 12.1: Podział trójkąta.

Przykład. Udowodnić, że w dowolnym 2n-kącie wypukłym istnieje przekątna nierów-

noległa do żadnego z boków tego wielokąta.

Rozwiązanie. Ilość przekątnych dowolnego s-kąta wypukłego wynosi

1
2

s(s − 3). Przy-

puśćmy dla dowodu nie wprost, że każda spośród

1
2

2n(2n − 3) = n(2n − 3) przekątnych

danego 2n-kąta jest równoległa do pewnego z jego boków. Ponieważ:

n(2n − 3)

= n −

> n − 2

więc na mocy zasady szufladkowej Dirichleta istnieje bok, do którego jest równoległych
co najmniej n − 1 przekątnych. Stąd wynika, że dany wielokąt ma co najmniej 2n + 1
wierzchołków. Uzyskana sprzeczność dowodzi tezy zadania.

Przykład. Na płaszczyźnie danych jest 5 punktów kratowych (są to punkty o współ-

rzędnych całkowitych). Wykazać, że środek jednego z odcinków łączących te punkty jest
też punktem kratowym.

Rozwiązanie. Korzystając z liter p (od: parzysty) i n (od: nieparzysty) tworzymy cztery

szufladki: (p, p), (p, n), (n, n) i (n, p) i przydzielamy do nich dane punkty w zależności od
parzystości ich współrzędnych. Zasada Dirichleta gwarantuje, że dwa z tych punktów
znajdą się w jednej szufladce. Oczywiście środek odcinka łączącego te dwa punkty jest
punktem kratowym.

Przykład. Udowodnić, że w zbiorze n + 1 liczb całkowitych istnieją dwie, których

różnica jest podzielna przez n.

Rozwiązanie. Skorzystamy z twierdzenia o dzieleniu z resztą mówiącego, że jeżeli a i

b są liczbami całkowitymi i b 6= 0, to istnieją liczby całkowite q i r (i są one wyznaczone
przez liczby a i b jednoznacznie), spełniające warunki:

a = bq + r

∧

0 ¬ r < |b|

ROZDZIAŁ 12. Zasada Dirichleta.

Liczbę r nazywamy resztą z dzielenia a przez b. Niech liczbami, o których mowa w

zadaniu, będą a

, a

, . . . , a

n+1

. Niech r

będzie resztą z dzielenia liczby a

przez n, zatem

jest liczbą ze zbioru 0, 1, . . . , n − 1. Umieśćmy w jednej szufladzie te spośród liczb a

, . . . , a

n+1

, które dają tę samą resztę przy dzieleniu przez n. Ponieważ liczb jest n + 1,

a możliwych reszt (szuflad) tylko n, zatem dwie liczby znajdą się w tej samej szufladzie.
Oznacza to, że istnieją różne liczby i oraz j, dla których a

= nq

+ r, a

= nq

+ r.

Odejmując stronami te równości otrzymujemy równość a

− a

= n(q

− q

), więc różnica

liczb a

oraz a

jest podzielna przez n, co kończy dowód.

Przykład. Zbiór M składa się z 1874 różnych liczb naturalnych. Pokazać, że można

wybrać a, b, c ∈ M takie, że a(b − c) dzieli się przez 1874.

Rozwiązanie. Jeśli któraś z liczb na przykład a ∈ M dzieli się przez 1874, to b i

c można wybrać dowolnie. Jeśli nie ma takiej liczby, to na podstawie zasady Dirichleta
wnioskujemy, że istnieją co najmniej dwie liczby b, c ∈ M , których reszty z dzielenia przez
1874 są takie same. Wówczas b − c dzieli się przez 1874, natomiast liczbę a można wybrać
dowolnie.

Rozdział 13

Równania rekurencyjne. ([1],
[5], [10], [18], [23])

Podana zostanie obecnie inna niż w rozdziale 4 metoda wyznaczenia wzorów bezpośrednio
określających n-ty wyraz ciągu określonego zależnością rekurencyjną:

= au

n−1

+ bu

n−2

dla

n ∈ N

(13.1)

Ciąg takiej postaci nazywamy uogólnionym ciągiem Fibonacciego. Przyjmujemy, że b 6= 0,
gdyż w przeciwnym razie ciąg (u

) jest ciągiem geometrycznym. Współczynniki a i b

występujące w zależności rekurencyjnej 13.1 wyznaczają wielomian

f (x) = x

− ax − b

który nazywamy wielomianem charakterystycznym równania rekurencyjnego (13.1).

Twierdzenie 13.1 Ciąg (t

) dla t 6= 0 spełnia zależność rekurencyjną 13.1 wtedy i tylko

wtedy, gdy t jest pierwiastkiem wielomianu charakterystycznego.

Ciąg (nt

) dla t 6= 0 spełnia zależność rekurencyjną 13.1 wtedy i tylko wtedy, gdy t

jest dwukrotnym pierwiastkiem wielomianu charakterystycznego.

Jeśli t

, t

są różnymi pierwiastkami wielomianu charakterystycznego, to rozwiązaniem

zależności rekurencyjnej 13.1 jest ciąg (u

) określony

= c

n
1

+ c

(13.2)

gdzie c

, c

są ustalonymi liczbami.

Jeśli t jest dwukrotnym pierwiastkiem wielomianu charakterystycznego, to rozwiąza-

niem zależności rekurencyjnej 13.1 jest ciąg (u

) określony

= c

+ c

(13.3)

gdzie c

są ustalonymi liczbami.

Dowód. Jeśli ciąg (t

) spełnia zależność 13.1, to mamy:

= at

n−1

+ bt

n−2

dla

n = 2, 3, . . .

ROZDZIAŁ 13. Równania rekurencyjne.

skąd oczywiście wynika t

= at + b, więc t jest pierwiastkiem wielomianu x

− ax − b. Jeśli

t jest pierwiastkiem tego wielomianu, to t

= at + b, więc

= at

n−1

+ bt

n−2

dla

n = 2, 3, . . .

Jeśli ciąg (nt

) spełnia zależność 13.1, to mamy:

= a(n − 1)t

n−1

+ b(n − 2)t

n−2

więc

n−2

[n(t

− at − b) + at + 2b] = 0

dla

n = 2, 3, . . .

Wynika stąd, że t

− at − b = 0 oraz at + 2b = 0, a to znaczy, że t = −

spełnia

równanie t

−at−b = 0, to zaś pociąga za sobą, że a

+4b = 0. Liczba t jest więc pierwiast-

kiem dwukrotnym wielomianu charakterystycznego. Przeprowadzone rachunki dowodzą
jednocześnie, że jeśli t jest pierwiastkiem dwukrotnym wielomianu charakterystycznego,
to ciąg (nt

) spełnia zależność 13.1.

Jeśli ciągi (t

) i (t

) albo odpowiednio (t

) i (nt

) spełniają zależność 13.1, to oczy-

wiście przy każdych stałych c

, c

, odpowiednio ciągi

n
1

+ c

n
2

)

+ c

)

spełniają zależność 13.1. Ponieważ ciąg określony rekurencyjnie ma konkretne wyrazy u

, więc stałe c

, c

(dla równania 13.2) są jednoznacznie wyznaczone przez zależności:

= c

+ c

= c

2
1

+ c

2
2

albo (dla 13.3)

= c

+ c

= c

+ c

Dowód twierdzenia został w ten sposób zakończony.

Przykłady w dalszej części pracy zilustrują sposób wykorzystania wielomianu charak-

terystycznego przy znajdowaniu wzoru ogólnego ciągów zadanych rekurencyjnie. Trzeba
jednocześnie w tym miejscu podkreślić, że taka umiejętność niejednokrotnie decyduje o
sukcesie przy rozwiązywaniu zadania techniką modelowania rekurencyjnego.

13.0.1

Renumeracja i przesunięcie o stałą wyrazów ciągu geome-
trycznego.

Przykład. Często występujący przypadek renumeracji który sprawia niekiedy kłopoty w
rozwiązaniu zadania to sytuacja, gdy dana jest zależność:

n+2

= qa

gdzie

q 6= 0

q 6= 1

oraz jest zadana wartość a

6= 0 dla pewnego n

∈ N. Oczywiście w ogólnym przypadku

nie można zapisać:

n+1

= a

√

dla

n ∈ N

13.1. Modelowanie rekurencyjne z wykorzystaniem liczb Fibonacciego.

Mamy natomiast:

+2(p+1)

= qa

+2p

gdzie

p ∈ N

Z powyższego otrzymujemy wzór na (n

+ 2p)-ty wyraz ciągu geometrycznego:

+2p

= a

p ∈ N

Przykład. Kolejny przypadek dotyczy przesunięcia o stałą wyrazów ciągu geometrycz-

nego. Na wejściu dana jest zależność:

n+1

= qa

+ c

q 6= 0

q 6= 1

c 6= 0

6= 0

n ∈ N

Wystarczy wówczas dokonać następującego podstawienia:

= a

q − 1

= a

q − 1

n ∈ N;

by zadanie sprowadziło się do wyznaczenia n-tego wyrazu ciągu geometrycznego b

n+1

przy danym b

i n ∈ N.

13.1

Modelowanie rekurencyjne z wykorzystaniem
liczb Fibonacciego. ([1], [13])

13.1.1

Definicja i własności ciągu liczb Fibonacciego.

Oryginalne zadanie, które Fibonacci rozważał dotyczyło rozmnażania się królików. Cho-
dziło mianowicie o określenie, ile par królików będzie liczyła po 12 miesiącach populacja
zaczęta przez jedną parę, przy założeniu, że po urodzeniu każda para królików dojrzewa
przez pierwszy miesiąc, a począwszy od drugiego wydaje na świat co miesiąc potomstwo
(przyjmuje się przy tym, że każda para jednorazowo płodzi jedną parę królicząt). Przy
tych założeniach rozumowanie Fibonacciego przebiegało następująco. Ponieważ pierwsza
para w pierwszym miesiącu daje jako potomstwo jedną parę, więc w tym miesiącu będą
dwie pary; z nich jedna para, a mianowicie pierwsza, rodzi również w następnym miesią-
cu, więc w drugim miesiącu będą trzy pary. Z nich w następnym miesiącu będą dawały
potomstwo dwie pary, a więc w trzecim rodzą się jeszcze dwie pary królików i w tym
miesiącu bedzie pięć par królików. Dalej analogiczny wywód ciągnie się aż do dwunastego
miesiąca, aby po kilku dodawaniach dojść do liczby 377, będącej końcowym wynikiem.

Idea wywodu daje się streścić następująco. W pierwszym miesiącu mamy dwie pary,

w drugim trzy. Chcąc uzyskać liczbę par królików w miesiącu n + 2 powinniśmy do ich
liczby z miesiąca n + 1 dodać te, które istniały w miesiącu n i wydały właśnie na świat
kolejne (być może pierwsze) młode.

Zakładamy, zgodnie z tradycją oznaczania liczb Fibonacciego a niezgodnie z orygina-

łem, że zarówno pierwsza jak i druga liczba Fibonacciego są jedynkami (tak jak gdyby w
zerowym miesiącu macierzysta para powstawała, a w następnym jeszcze dojrzewała).

Definiujemy ciąg Fibonacciego następująco:

= 1

= F

n−1

+ F

n−2

n  2

Kolejne liczby uzyskane bezpośrednio z definicji, są wypisane w tabeli 13.1.

Jak widzimy definicja rekurencyjna pozwala wyznaczyć kolejne wyrazy ciągu, choć

niestety w celu obliczenia tą metodą któregoś wyrazu ciągu trzeba obliczyć wszystkie

ROZDZIAŁ 13. Równania rekurencyjne.

. . .

Tabela 13.1: Liczby Fibonacciego.

wyrazy poprzednie. Znalezienie jawnego wzoru na wyrazy ciągu Fibonacciego nie jest
najłatwiejsze. Wzór na n-ty wyraz ciągu Fibonacciego został udowodniony dopiero w
XIX wieku (a więc ponad 600 lat po Fibonaccim) przez J.Bineta. Trudno uwierzyć bez
dowodu, że ten skomplikowany wzór daje w wyniku dla każdego n liczby naturalne.

13.1.2

Wzór Bineta.

Twierdzenie 13.2 (wzór Bineta)

√

1 +

√

−

1 −

√

n = 0, 1, 2, . . .

(13.4)

Przedstawię teraz dwie metody wyprowadzenia ogólnego wzoru ciągu Fibonacciego.

Jednocześnie w ten sposób zostaną zaprezentowane dwie podstawowe metody wyzna-
czania wyrazu ogólnego dowolnego ciągu określonego zależnością rekurencyjną. Metoda
pierwsza, akademicka, wykorzystuje pojęcie funkcji tworzącej i własności szeregów po-
tęgowych, z tego też względu nie kandyduje do wykorzystania w liceum. Metoda druga
bazuje na wielomianie charakterystycznym równania rekurencyjnego, który z zosatał już
w podręczniku zdefiniowany i wykorzystany

Metoda I.

Dowód. Określmy funkcję F jako sumę szeregu potęgowego o wspólczynnikach F

, czyli

funkcję tworzącą ciągu liczb Fibonacciego (F

F (t) = F

+ F

t + F

+ . . . =

∞

n=0

Znajdziemy teraz jawny wzór na funkcję F . Zauważmy, że:

F (t) − t − 1 =

∞

n=2

∞

n=0

n+2

∞

n=0

+ F

n+1

n+2

∞

n=0

+ t

∞

n=0

n+1

= t

F (t) + t(F (t) − 1)

Tak więc funkcja F spełnia równanie:

F (t) − t − 1 = t

F (t) + t(F (t) − 1)

Jedyną taką funkcją jest (jak łatwo obliczyć):

F (t) =

1 − t − t

13.1. Modelowanie rekurencyjne z wykorzystaniem liczb Fibonacciego.

Aby znaleźć współczynniki rozwinięcia funkcji F , zapiszemy ją inaczej. Pierwiastkami
trójmianu t

+ t − 1 są liczby:

−1 −

√

−1 +

√

Tak więc

F (t) = −

√

1 −

−

1 −

Teraz korzystając ze wzoru na sumę szeregu geometrycznego, otrzymujemy:

F (t) = −

√

∞

n=0

−

∞

n=0

∞

n=0

√

n+1
1

− t

n+1
2

n+1
1

n+1
2

Wzór ten ma sens dla |t| < min(|t

|, |t

|). Z jednoznaczności rozwinięcia funkcji w szereg

potęgowy mamy:

√

(1 +

√

n+1

− (1 −

√

n+1

√

1 +

√

n+1

−

1 −

√

n+1

n = 0, 1, 2, . . .

Koniec dowodu.

Metoda II.

Dowód. Przypomnijmy definicję rekurencyjną ciągu Fibonacciego:

= F

= 1

(13.5)

n+2

= F

n+1

+ F

n > 1

(13.6)

Zależności 13.6 odpowiada wielomian charakterystyczny:

f (x) = x

− x − 1

Pierwiastki tego wielomianu wynoszą x

1−

√

, x

√

, więc z 13.5 otrzymujemy,

że

= c

n
1

+ c

n
2

= c

1 −

√

+ c

1 +

√

gdzie liczby c

, c

spełniają zależności:

+ c

= 1

1 −

√

+ c

1 +

√

= 1

Rozwiązując ten układ równań otrzymujemy: c

5−

√

, c

√

. Zatem

5 −

√

1 −

√

5 +

√

1 +

√

ROZDZIAŁ 13. Równania rekurencyjne.

Po przekształceniach dostajemy

√

5 − 1)

2 · 5

1 −

√

5 + 1)

2 · 5

1 +

√

1 −

√

n+1

−

1 +

√

n+1

Koniec dowodu.

13.2

Inne własności ciągu liczb Fibonacciego.

Dla dowolnych liczb naturalnych zachodzą związki:

n+2

− 1 = F

+ F

+ . . . + F

= F

+ F

+ . . . + F

2n−1

2n+1

− 1 = F

+ F

+ . . . + F

2m−1

− 1 = F

− F

+ F

− F

+ F

+ . . . + (−1)

+ F

n+1

= F

+ F

+ . . . + F

n+m

= F

n−1

m−1

+ F

m, n  1

= F

n+1

− F

n−1

= F

n−1

n+1

+ (−1)

n+1

= 1 + F

n−2

n−1

n+1

n+2

n  2

= F

+ F

+ . . . + F

2n−1

n+1

= F

n−m

+ F

m+1

n−m+1

n m  0

2n+1

= F

+ F

n+1

n  0

= F

n+1

− F

n−1

n  1

= F

+ F

n+1

− F

n−1

n  1

n−1

n+1

− F

= (−1)

n  1

n+4

− (n + 3) = nF

+ (n − 1)F

+ . . . + 2F

n−1

+ F

n+2

− F

n+3

+ 2 = F

+ 2F

+ . . . + nF

n | m ⇒ F

| F

NWD(F

, F

n+1

) = 1

NWD(F

, F

) = F

NWD(m,n)

n−1

k=0

n−k

= F

k=0

k+2

k+1

k+3

−

n+4

n+2

n+3

13.2. Inne własności ciągu liczb Fibonacciego.

13.2.1

Przykłady zadań rozwiązanych metodą modelowania re-
kurencyjnego z wykorzystaniem liczb Fibonacciego.

Zauważmy, że Fibonacci zamiast podać wynik zadania, podał jedynie sposób, w jaki
można do niego dojść. Czy można uznać to zadanie za rozwiązane?

Jeżeli mamy ochotę odrzucić tego typu „algorytmiczne” rozwiązania, to zdajmy so-

bie sprawę, że w wielu przypadkach trudno jest inaczej rozwiązać problem, niż w taki
rekurencyjny sposób w jaki zrobił to Fibonacci. Przykładowo rozważymy kilka takich
problemów.

Przykład. Ile pra-pra-. . . -pra (n-razy) dziadków i babć ma pszczeli truteń?
Rozwiązanie. Trzeba oczywiście wiedzieć, że u pszczół trutnie mają tylko matkę –

królową, powstają bez udziału ojca, podczas gdy królowe mają już dwoje rodziców – inną
królową i trutnia.

Rysunek 13.1: Drzewo genealogiczne trutnia.

Niech T

oznacza liczbę n-praprzodków. Widzimy już, że na poziomie pierwszych pra-

dziadków truteń ma dwie prababcie i jednego pradziadka, łącznie troje. Piętro wyżej – na
poziomie drugich pradziadków – pięcioro, trzy prababcie i dwóch prapradziadków. Ogól-
nie na poziomie n-tych dziadków ma dokładnie T

n−1

n-prababć oraz T

n−2

n-pradziadków,

łącznie więc ma:

= T

n−1

+ T

n−2

n  2

n-praprzodków. Otrzymaliśmy zatem identyczne równanie rekurencyjne, określające zde-
finiowany wyżej ciąg Fibonacciego. Pozostaje określić warunki początkowe, T

= 2 (przyj-

mujemy dziadków za 0-pradziadków), T

= 3 i jasne jest, że ogólnie zachodzi po prostu:

= F

n+2

n  0

Przykład. Elfy skacząc po schodach czasami przeskakują po dwa schodki. Na ile spo-

sobów może elf wskoczyć na n schodów?

Rozwiązanie. Tym razem od razu poddamy się i zaczniemy rozumowanie rekurencyjne.

Oznaczmy przez E

liczbę sposobów za pomocą których elf może wskoczyć na n schodów.

Przyjmujemy, że E

= 1 i zauważamy ponadto, że E

= 1 oraz E

= 2. Aby wskoczyć na

ROZDZIAŁ 13. Równania rekurencyjne.

n-ty schodek, elf musi to zrobić ze schodka n − 1 lub n − 2. W związku z tym mamy:

= E

n+1

+ E

n−2

n  3

W ten sposób dostajemy oczywistą odpowiedź, że szukana liczba sposobów wynosi:

= F

n  1

Przykład. Ile jest eleganckich sposobów posadzenia łącznie n pań i panów na podłużnej

ławie? Eleganckich, czyli takich, aby żadne dwie panie nie siedziały obok siebie (interesują
nas jedynie różne wzajemne rozmieszczenia pań i panów, czyli interesuje nas tylko, które
miejsca są zajęte przez panie a które przez panów).

Rozwiązanie. Widać, że jeżeli mamy do dyspozycji samych panów, to możemy ich

posadzić na jeden sposób. Jedną panią z n − 1 panami można posadzić na n sposobów.
Z dwiema już będzie trochę kłopotu. Z trzema – tym bardziej. Łatwo zauważyć, że pań
nie może być więcej niż [

]. Rekurencja ze względu na liczbę pań przy ustalonym n

jest trudna do wyprowadzenia. Zastanówmy się jednak, czy nie dałoby się przeprowadzić
rozumowania rekurencyjnego ze względu na n?

Oznaczmy przez S

liczbę takich n-posadzeń, że żadne dwie panie nie siedzą obok

siebie i załóżmy, że znamy S

dla wszystkich k < n. Przeliczając wszystkie n-posadzenia

musimy zdecydować, czy na n-tym miejscu będzie siedziała pani, czy też pan. Jeżeli pani,
to na n − 1 miejscu musi siedzieć pan, a na pierwszych n − 2 miejscach możemy posadzić
dowolny z S

n−2

układów. Jeżeli pan, to ze względu na to, że pan na n-tym miejscu nie

czyni żadnego kłopotu, widzimy, że na pierwszych n − 1 miejscach możemy użyć dowolny
z S

układów. Łącznie, oczywiście, uzyskujemy:

= 2

= 3

= S

n−1

+ S

n−2

n > 2

więc szukana liczba usadzeń pań i panów na ławie wynosi:

= F

n+2

Przykład. Wyznaczyć liczbę takich podzbiorów zbioru {1 , 2, . . ., n}, które nie zawie-

rają dwóch kolejnych liczb.

Rozwiązanie. Dla n = 1 są dwa takie podzbiory: ∅, {1}. Dla n = 2 są trzy takie

podzbiory: ∅, {1}, {2}. Przypuśćmy, że n  2. Każdy podzbiór zbioru {1 , 2, . . ., n + 1}
nie zawierający dwóch kolejnych liczb, do którego nie należy liczba n + 1 jest podzbiorem
żądanej postaci zbioru {1 , 2, . . ., n}. Każdy podzbiór zbioru {1 , 2, . . ., n + 1} nie zawie-
rający dwóch kolejnych liczb do którego należy liczba n + 1 jest podzbiorem postaci {k

, . . ., k

, n + 1}, przy czym liczby k

, k

, . . . , k

są mniejsze od n i nie ma wśród nich

dwóch kolejnych.

Jeśli więc a

jest liczbą omawianych podzbiorów zbioru {1, 2, . . . n}, to dla n  2 jest

n+1

= a

+ a

n−1

. Ciąg (a

) spełnia więc warunki:

= 2

= 3

= a

n−1

+ a

n−2

n > 2

Jest to ciąg Fibonacciego. Wystarczy tylko zauważyć, że:

= F

n+1

n  1

aby otrzymać dający natychmiastowe rozwiązane model rekurencyjny.

Oczywiście nie każde rozumowanie rekurencyjne daje w wyniku liczby Fibonacciego.

Wystarczy zmienić każde z tych zadań (np. dopuścić aby elfy skakały także po trzy schod-
ki, albo rozważyć usadzenia przy okrągłym stole), aby nie tylko warunki początkowe, ale
i same równania otrzymać w innej postaci.

13.3. Metoda modelowania rekurencyjnego w zadaniach.

13.3

Metoda modelowania rekurencyjnego
w zadaniach.

13.3.1

Zadania z kombinatoryki.

W rozdziale 4 zostały już przedstawione pewne zadania z kombinatoryki, przy rozwią-
zywaniu których efektywnie wykorzystywano modele rekurencyjne związane z ciągiem
Fibonacciego. Poniżej przedstawione zostaną inne przykłady zadań kombinatorycznych,
które można łatwo rozwiązać konstruując odpowiednie modele rekurencyjne.

Przykład. W tańcu ludowym tancerze stoją w dwóch rzędach naprzeciw siebie, w

jednym rzędzie n dziewcząt, w drugim n chłopców. Każdy z tancerzy podaje lewą rękę
osobie stojącej naprzeciw siebie lub sąsiadowi z lewej strony lub osobie stojącej naprzeciw
sąsiada z lewej strony. Analogiczna reguła dotyczy prawej ręki. Nikt nie podaje ręki tej
samej osobie. Wyznaczyć liczbę możliwych układów rąk.

Rozwiązanie. Oznaczmy liczbę możliwych układów rąk przez u

. Przypuśćmy, że ob-

serwujemy tancerzy stojąc za rzędem chłopców. Numerujemy chłopców kolejnymi liczbami
naturalnymi zaczynając od lewej strony: c

, c

, . . . , c

; dziewczynce stojącej naprzeciw

chłopca c

przypisujemy symbol d

. Tancerze są ustawieni tak jak na rysunku 13.2.

Z warunku zadania wynika, że chłopiec c

podaje lewą rękę dziewczynce d

, chłopiec

podaje prawą rękę dziewczynce d

. Ponieważ nikt nie podaje obu rąk tej samej osobie,

więc przy n = 1 nie można spełnić warunków zadania, zatem u

= 0. Dla n = 2 możliwe

są dwa układy rąk przedstawione schematycznie na rysunku 13.3, albo c

podaje prawą

rękę c

a d

lewą rękę a

albo c

podaje prawą rękę d

, zaś c

lewą rękę d

. Wobec tego

= 2.

Każdy z tych dwóch układów rąk można na dwa sposoby przedłużyć dołączając trze-

cią parę. Trzeba w tym celu rozłączyć prawą rękę chłopca c

i lewą rękę dziewczynki d

Następnie chłopiec c

może podać swą prawą rękę albo dziewczynce d

albo chłopcu c

Po dokonaniu tego wyboru przez chłopca c

układ pozostałych rąk jest już jednoznacz-

nie wyznaczony. Mamy więc możliwe cztery układy rąk przedstawione schematycznie na
rysunku 13.4. Zatem u

= 4.

Zbudujemy teraz model rekurencyjny danego w zadaniu problemu. Polegać to bę-

dzie na ustaleniu zależności rekurencyjnej określającej wyrazy u

w zależności od dwóch

poprzednich.

Przypuśćmy, że n > 3. Rozważmy dowolny układ rąk tancerzy i zwróćmy szczególną

uwagę na trzy ostatnie pary. Możliwe są przypadki przedstawione na rysunku 13.5.

W przypadkach a) i b) układ rąk tancerzy d

, . . . , d

n−2

, c

, . . . , c

n−2

jest dowolnym

układem dla n − 2 par, zatem liczba układów postaci a) wynosi u

n−2

i liczba układów

postaci b) jest równa u

n−2

. W czterech pozostałych przypadkach rozważane układy po-

Rysunek 13.2: Ustawienie tancerzy.

ROZDZIAŁ 13. Równania rekurencyjne.

Rysunek 13.3: Układy rąk dla dwóch par.

Rysunek 13.4: Układy rąk dla trzech par.

Rysunek 13.5:

wstały z układu dla n − 1 par (d

, c

), . . . , (d

n−1

, c

n−1

) przez rozłączenie prawej ręki

chłopca c

n−1

i lewej ręki dziewczynki d

n−1

. Jeśli przy tym c

n−1

podał prawą rękę chłop-

cu c

, to mamy przypadki c) i e), jeśli zaś c

n−1

podał prawą rękę dziewczynce d

, to

13.3. Metoda modelowania rekurencyjnego w zadaniach.

otrzymujemy przypadki d) i f).

Stwierdziliśmy w ten sposób, że każdy układ rąk dla n par tancerzy można otrzymać

albo z układu rąk dla n − 2 par, albo z układu rąk dla n − 1 par, przy czym z każdego
układu rąk dla n − 2 par albo n − 1 par można otrzymać dwa różne układy rąk dla n par.
Wobec tego:

= 2u

n−1

+ 2u

n−2

n  3

Ciąg (u

) ma (na podstawie twierdzenia 4.1) wielomian charakterystyczny:

f (x) = x

− 2x − 2

którego pierwiastkami są liczby x

= 1 +

√

3 oraz x

= 1 −

√

3. Zatem

= c

n
1

+ c

n
2

= c

(1 +

√

+ c

(1 −

√

gdzie liczby c

, c

obliczymy podstawiając n = 1, 2. Otrzymamy układ:

(1 +

√

3) + c

(1 −

√

3) = 0

(1 +

√

+ c

(1 −

√

= 2

Po jego rozwiązaniu, dostajemy c

3−

√

, c

√

. Ostatecznie więc liczba moż-

liwych układów rąk dna n par wynosi:

3 −

√

(1 +

√

3 +

√

(1 −

√

n  1

13.3.2

Zadania z rachunku prawdopodobieństwa.

Przykład. Gracz rzuca monetą. Jeśli wypadnie reszka, to wygrywa on 1 zł, a jeśli orzeł -
to traci 1 zł. Na początku gry gracz ma n złotych. Gra kończy się, gdy gracz wygra z góry
ustaloną sumę a zł albo też przegra wszystkie pieniądze. Jakie jest prawdopodobieństwo
zrujnowania się gracza? (Problem ruiny gracza.)

Rozwiązanie. Oznaczmy przez p(n) prawdopodobieństwo zrujnowania się gracza, jeśli

na początku gry ma on n złotych. Zauważmy, że wówczas p(n + 1) oznacza prawdopodo-
bieństwo zrujnowania się tego gracza przy założeniu, że wygrał on przy pierwszym rzucie,
ma on wtedy bowiem n + 1 zł. Natomiast p(n − 1) oznacza prawdopodobieństwo zrujno-
wania się tego gracza przy założeniu, że przegrał on przy pierwszym rzucie, ma on wtedy
n − 1 zł.

Dla potrzeb konstrukcji prawdopodobieństwa warunkowego i całkowitego oznaczmy

przez B

, B

prawdopodobieństwa odpowiednio wygranej i przegranej gracza przy pierw-

szym rzucie, a przez A prawdopodobieństwo zrujnowania się gracza. Wtedy:

P (B

) = P (B

) =

P (A | B

) = p(n + 1)

P (A | B

) = p(n − 1)

Uwzględniając wzór na prawdopodobieństwo całkowite,

P (A) = P (A | B

)P (B

) + P (A | B

)P (B

)

ROZDZIAŁ 13. Równania rekurencyjne.

otrzymujemy równanie:

p(n) =

p(n + 1) +

p(n − 1)

0 ¬ n ¬ a

Przekształcając powyższe równanie otrzymujemy następującą postać modelu rekurencyj-
nego:

p(n + 1) = 2p(n) − p(n − 1)

0 ¬ n ¬ a

Powyższej zależności rekurencyjnej odpowiada wielomian charakterystyczny, o postaci:

f (x) = x

− 2x + 1 = (x − 1)

Ponieważ pierwiastkiem dwukrotnym tego wielomianu jest liczba x

, więc, (na mocy twier-

dzenia 4.1):

p(n) = c

n
0

+ c

n
0

= c

+ c

Stałe c

, c

wyznaczamy z warunków zadania:

p(0) = c

= 1

p(a) = c

+ c

a = 0

Skąd otrzymujemy c

= 1, c

= −

1
a

W rezultacie szukane prawdopodobieństwo zrujnowania się gracza wynosi:

p(n) = 1 −

a n  0

Przykład. W pewnej rodzinie mąż i żona zawarli następującą umowę: jeżeli któregoś

dnia zmywa naczynia żona, to następnego dnia zmywa naczynia mąż. Jeżeli natomiast
pewnego dnia zmywa naczynia mąż, to o tym, kto zmywa następnego dnia, decyduje
losowanie za pomocą rzutu monetą. Obliczyć prawdopodobieństwo zdarzenia, że setne-
go dnia trwania umowy będzie zmywał mąż. Przyjmujemy, że pierwszego dnia trwania
umowy rzucono monetą.

Rozwiązanie. Niech p

oznacza prawdopodobieństwo zdarzenia, że n-tego dnia trwania

umowy zmywa naczynia mąż. Wobec tego z warunków zadania mamy p

1
2

. Zauważmy,

że jeżeli n-tego dnia naczynia zmywa mąż, to możliwe są dwa rozłączne przypadki:

1. (n-1)-szego dnia zmywał mąż. Prawdopodobieństwo tego zdarzenia wynosi

1
2

n−1

2. (n-1)-szego dnia zmywała żona. Prawdopodobieństwo tego zdarzenia jest równe 1 −

n−1

Uwzględniając konstrukcję prawdopodobieństwa całkowitego mamy więc:

n−1

+ (1 − p

n−1

)

n  2

Po uproszczeniu otrzymujemy następującą relację uwarunkowania rekurencyjnego:

= −

n−1

+ 1

n  2

13.3. Metoda modelowania rekurencyjnego w zadaniach.

Wykorzystamy teraz metodę przesunięcia o stałą wyrazów ciągu geometrycznego. W tym
celu dokonamy podstawienia:

= p

−

1
2

− 1

= p

−

n  1

Otrzymujemy wtedy:

= p

−

= −

oraz

= −

n−1

n  2

Z powyższych zależności dostajemy:

−

= −

−

n−1

n  2

Przekształcając powyższą zależność i podstawiając n = 100, znajdujemy szukane praw-
dopodobieństwo:

100

= −

−

3 · 2

100

+ 2

Przykład. Jakie jest prawdopodobieństwo otrzymania parzystej liczby sukcesów w

schemacie n prób Bernoulliego, w którym prawdopodobieństwo sukcesu w pojedyńczej
próbie wynosi p.

Rozwiązanie. Oznaczmy przez p

prawdopodobieństwo uzyskania parzystej liczby suk-

cesów po przeprowadzeniu pierwszych k doświadczeń. Zauważamy, że p

= 1 − p. Przed

przeprowadzeniem k-tego doświadczenia możliwe są dwie hipotezy:

1. W pierwszych k − 1 doświadczeniach uzyskano parzystą liczbę sukcesów.

2. W pierwszych k − 1 doświadczeniach uzyskano nieparzystą liczbę sukcesów.

Prawdopodobieństwa tych hipotez są równe odpowiednio p

k−1

i 1 − p

k−1

. Uwzględnia-

jąc konstrukcję prawdopodobieństwa całkowitego, uzyskujemy w ten sposób następującą
postać modelu rekurencyjnego:

= p

k−1

(1 − p) + (1 − p

k−1

k  2

po uproszczeniu zaś:

= p + p

k−1

(1 − 2p)

k  2

Aby dokonać przesunięcia o stałą wyrazów wyżej określonego ciągu rekurencyjnego, do-
konamy podstawienia:

= p

1 − 2p − 1

k  2

Otrzymujemy stąd:

= q

k−1

(1 − 2p)

k  2

− p

Z powyższych zależności można już wyznaczyć postać wzoru na poszukiwane prawdopo-
dobieństwo:

−

= q

− p

(1 − 2p)

k−1

k  2

ROZDZIAŁ 13. Równania rekurencyjne.

Po przekształceniach otrzymujemy:

(1 + (1 − 2p)

)

n  1

Przykład. W urnie znajdują się 3 kule, oznaczone odpowiednio cyframi: 0, 1, 2. Wycią-

gamy w sposób losowy jedną kule, a następnie ją zwracamy. Jakie jest prawdopodobień-
stwo, że w wyniku n (n ∈ N) losowań suma liczb odpowiadających cyfrom oznaczającym
losowanie kule jest liczbą nieparzystą?

Rozwiązanie. Oznaczmy przez a

dla i = 1, 2, 3, . . ., n liczby odpowiadające cyfrom

oznaczającym kule przy i-tym losowaniu. Niech S

oznacza sumę liczb a

po n losowa-

niach. Szukamy więc prawdopodobieństwa tego, że S

jest liczbą nieparzystą. Nie zaj-

mując się historią wcześniejszych wyników niż (n − 1)-sza wartość sumy S

n−1

, wystarczy

zauważyć następującą relację uwarunkowania rekurencyjnego:

1. Jeżeli S

n−1

jest liczbą parzystą, to w n-tym losowaniu należy koniecznie wyciągnąć

kulę oznaczoną cyfrą 1, czyli musi być a

= 1.

2. Jeżeli S

n−1

jest liczbą nieparzystą, to w n-tym losowaniu należy koniecznie wycią-

gnąć kulę oznaczoną cyframi 0 lub 2, czyli musi być a

= 0 lub a

= 2.

Przechodząc od modelu strukturalnego do matematycznego, przy oznaczeniu:

P (S

= 1, 3, . . . , 2k − 1) = p

k  1

oraz uwzględniając konstrukcję prawdopodobieństwa całkowitego, niezależność zdarzeń
losowania kuli oraz wzór na prawdopodobieństwo dopełnienia (p

0
k

= 1 − p

) otrzymamy

następującą postać modelu rekurencyjnego:

2
1

3
1

k−1

1
1

3
1

(1 − p

k−1

) =

k−1

k  2

Z analizy pojedyńczego losowania mamy:

W tym zadaniu model rekurencyjny sprowadza się do konstrukcji przesunięcia o stałą
wyrazów ciągu geometrycznego. Dokonując podstawienia

= p

1
3

− 1

= p

−

k  2

do otrzymanych wcześniej zależności rekurencyjnych otrzymamy:

k−1

k  2

oraz

= −

Ostatecznie:

−

= −

n−1

n  1

Stąd szukane prawdopodobieństwo wynosi:

1 −

n  1

13.3. Metoda modelowania rekurencyjnego w zadaniach.

Przykład. Urna zawiera jedną białą i jedną czarną kulę. Losujemy kolejno po jednej

kuli ze zwracaniem dopóty, dopóki liczba wylosowanych kul jednego koloru nie będzie o
k większa od liczby wylosowanych kul drugiego koloru. Jakie jest prawdopodobieństwo,
że wykonamy:

1. 2n losowań, jeśli k = 2

2. n losowań, jeśli k = 3

Rozwiązanie 1. Zauważamy, że gra może zakończyć się tylko po parzystej liczbie loso-

wań. Niech p

będzie prawdopodobieństwem, że gra nie zakończy się po (2k)-tym losowa-

niu. Przyjmujemy p

= 1. Otrzymujemy wtedy następujący model rekurencyjny:

k+1

k = 0, 1, 2, . . . , n − 1

n−1

· p

n−1

Szukane prawdopodobieństwo wynosi:

n−1

n  1

Rozwiązanie 2. Na początku należy zauważyć, że liczba n może być tylko nieparzysta.

Niech p

będzie prawdopodobieństwem, że gra nie zakończy się po (2k+1)-szym losowaniu.

Dostajemy wtedy następującą relację uwarunkowania rekurencyjnego:

= p

k−1

1 −

k−1

k = 0, 1, . . . ,

(n − 3)

a więc

k = 0, 1, . . . ,

(n − 3)

szukane prawdopodobieństwo wynosi:

(n−3)/2

n  3

Przykład. Rzucamy n-krotnie monetą i wynik zapisujemy w postaci ciągu (a

, a

, . . .,

), gdzie a

= 1 lub a

= 2 w zależności od tego, czy w i-tym rzucie wypadł orzeł,

czy reszka. Przyjmujemy, b

= a

+ a

+ . . . + a

dla j = 1, 2, . . . , n. Niech p(n) będzie

prawdopodobieństwem tego, że w ciągu (b

, b

, . . . , b

) wystąpi liczba n. Wyznaczyć p(n).

Rozwiązanie. Bezpośrednio stwierdzamy, że p(1) =

1
2

, p(2) =

1
4

. Przypuśćmy, że n  3.

Zauważamy, że b

 j dla każdego j. Liczba n może wystąpić w ciągu (b

, b

, . . ., b

) w

następujących dwóch przypadkach:

1. Pewien wyraz tego ciągu równy jest n − 1, np. b

= n − 1

k ¬ n − 1 i ponadto

k+1

= 1.

2. Pewien wyraz tego ciągu równy jest n − 2, np. b

= n − 2

r ¬ n − 2 i ponadto

r+1

= 2.

ROZDZIAŁ 13. Równania rekurencyjne.

Prawdopodobieństwo dla wymienionych tu przypadków wynosi odpowiednio

1
2

p(n − 1)

oraz

1
2

p(n − 2), przy czym przypadki te nie mogą wystąpić jednocześnie. Wobec tego,

uwzględniając konstrukcję prawdopodobieństwa całkowitego, dostajemy następującą po-
stać modelu rekurencyjnego:

p(n) = p(n − 1) ·

+ p(n − 2) ·

Otrzymaliśmy zależność rekurencyjną, której odpowiada (zgodnie z twierdzeniem 4.1)
wielomian charakterystyczny:

f (x) = x

−

x −

Pierwiastkami tego wielomianu są liczby x

= 1, x

= −

1
2

, zatem rozwiązaniem naszej

zależności rekurencyjnej jest ciąg postaci:

p(n) = c

n
1

+ c

n
2

= c

+ c

−

Ponieważ p(1) =

1
2

i p(2) =

1
4

, więc stałe c

, c

otrzymamy rozwiązując układ:











+ c

−

+ c

−

Dostajemy stąd c

1
3

, c

= −

1
3

. Ostatecznie więc:

p(n) =

−

n = 1, 2, 3, . . .

Przykład. Wypisujemy kolejno wyrazy ciągu (n

, n

, . . ., n

), gdzie n

= 1000, zaś n

dla j > 1 jest liczbą całkowitą wybraną losowo z przedziału h0, n

j−1

− 1i (wybór każdej

liczby z tego przedziału jest jednakowo prawdopodobny). Kończymy wypisywanie, gdy
wybrana liczba jest zerem, tzn. n

k−1

6= 0, n

= 0. Długość k, ciągu (n

, n

, . . . , n

) jest

zmienną losową. Udowodnić, że wartość oczekiwana tej zmiennej losowej jest większa od
7.

Rozwiązanie. Dla danej liczby całkowitej nieujemnej n rozważmy zbiór A

wszystkich

ciągów (n

, n

, . . ., n

), w których n

= n, zaś n

dla j > 1 jest liczbą całkowitą

wybraną losowo z przedziału h0, n

j−1

− 1i a n

= 0. Każdej liczbie całkowitej k ∈ h0, ni

przypisujemy prawdopodobieństwo tego, że losowo wybrany ciąg z rozważanego zbioru
ma dokładnie k wyrazów. Otrzymujemy w ten sposób zmienną losową X

Oznaczmy przez E

wartość oczekiwaną tej zmiennej losowej. Oczywiście E

= 1,

gdyż dla n = 0 istnieje tylko jeden ciąg mający długość 1, którego jedynym wyrazem jest
0.

Niech n będzie liczbą naturalną. Przypuśćmy, że wyznaczyliśmy wartości oczekiwane

dla wszystkich m < n. Rozważmy ciągi (n

, n

, . . ., n

), w których n

= n. Możliwe

są dwa następujące zdarzenia:

1. n

= n − 1. Prawdopodobieństwo tego zdarzenia wynosi

. Rozważmy ciąg (n

. . ., n

) należący do zbioru A

n−1

. Wartość oczekiwana długości tego ciągu wynosi

n−1

, więc wartość oczekiwana długości ciągu (n

, n

, . . ., n

) należącego do A

mającego o jeden wyraz więcej wynosi E

n−1

+ 1.

13.3. Metoda modelowania rekurencyjnego w zadaniach.

2. n

< n − 1. Prawdopodobieństwo tego zdarzenia wynosi

n−1

. W tym przypadku

wartość oczekiwana długości ciągu (n

, n

, . . ., n

) należącego do A

jest dokładnie

taka, jak wartość oczekiwana długości ciągu (m

, m

, . . ., m

) należącego do A

n−1

w którym m

= n − 1. Ta wartość oczekiwana wynosi E

n−1

Tak więc, uwzględniając konstrukcję prawdopodobieństwa całkowitego, otrzymujemy mo-
del rekurencyjny postaci:

n−1

+ 1) +

n − 1

n−1

= E

n−1

Ponieważ E

= 1, więc:

= 1 +

= 2 +

+ . . . +

Interesująca nas wartość oczekiwana

1000

= 2 +

+ . . . +

1000

= 2 +

+ . . . +

+ +

+ . . . +

128

129

+ . . . +

256

257

+ . . . +

512

513

+ . . . +

1024

−

1001

+ . . . +

1024

Liczba w ostatnim nawiasie jest mniejsza od

1000

, natomiast każda z liczb w poprzed-

nich nawiasach (których jest osiem) jest większa od

1
2

, gdyż w (k − 1)-szym nawiasie jest

liczba

+ 1

+ 2

+ . . . +

k+1

;

k = 2, 3, . . . , 9

będącą sumą 2

składników, z których wszystkie są większe od (tylko ostatni jest równy)

k+1

. Wobec tego:

1000

> 2 +

+ 8 ·

−

1000

= 6 +

3178

3000

> 7

Przykład. Rzucamy cztery razy sześcienną kostką do gry. Jakie jest prawdopodobień-

stwo, że suma wypadających oczek jest podzielna przez dwa.

Rozwiązanie. Rozwiązując zadanie metodą modelowania rekurencyjnego sprawą naj-

istotniejszą jest przedstawienie relacji kolejnych zdarzeń. W powyższym zadaniu dotyczy
to zdarzeń polegających na rzucie kostką. Rozpatrując k-ty wynik rzutu kostką należy
zwrócić uwagę na istniejącą w zadaniu zależność rekurenvcyjną:

• jeśli S

n−1

jest liczbą nieparzystą, więc aby suma wylosowanych oczek była podzielna

przez dwa należy wylosować kostkę z numerem nieparzystym

ROZDZIAŁ 13. Równania rekurencyjne.

• jeśli S

n−1

jest liczbą parzystą, więc aby suma wylosowanych oczek była podzielna

przez dwa należy wylosować kostkę z numerem parzystym.

Zatem można zapisać zbiór zdarzeń sprzyjających w postaci

A = {ε = (a

, a

, . . . , a

) : (S

n−1

= 1, 3, . . . , 6n − 1

= 1, 3, 5)∨

n−1

= 2, 4, . . . , 6n

= 2, 4, 6)}

Oznaczmy

P (S

= 2, 4, . . . , 6n) = p

k ∈ N

Na podstawie definicji prawdopodobieństwa, uwzględniając niezależność zdarzeń rzutu

kostką oraz wzór na prawdopodobieństwo dopełnienia (prawdopoodbiwństwo całkowite)
możemy skonstruować model rekurencyjny w celu obliczenia szukanego prawdopodobień-
stwa:

= p

k−1

3
1

6
1

+ (1 − p

k−1

)

3
1

6
1

co bezpośrednio daje nam wynik

Przykład. Dla losowo wybranej permutacji f = (f

, . . . , f

) zbioru {1, . . . , n} oznacz-

my przez X(f ) największą liczbę k ¬ n taką, że f

< f

i+1

dla każdego i < k. Udowodnić,

że wartość oczekiwana zmiennej losowej X wynosi

n
k=1

Rozwiązanie. Opiszmy przestrzeń probabilistyczną, czyli przestrzeń zdarzeń elemen-

tarnych, którą stanowią ciągi n-elementowe o wyrazach rosnących:

Ω =

f = (f

, . . . , f

) : f

∈ {1, . . . , n},

i = 1, . . . , n

n ∈ N

Oznaczmy zmienną losową przez Z

. Wartość zmiennej losowej Z

jest to długość n-

elementowego ciągu o wyrazach rosnących. Oczywiście E(Z

) = 1. Przy rozwiązywaniu

zadania bardzo pomocnym okaże się poniższy lemat (13.2.1). Dla zmiennej losowej Z
przyjmującej wartości ze skończonego zbioru udowodnimy własność wynikającą z linio-
wości operacji obliczania zmiennej losowej

Lemat 13.2.1 Jeżeli

Z =

(

z prawdopodobieństwem

(1 − p)

E(Z) = E(X)p + E(Y )(1 − p)

Dowód. Oznaczmy

(

l = 1, . . . , n

l = n + 1, . . . , n + m

(

0
l

l = 1, . . . , n

00
l−n

l = n + 1, . . . , n + m

gdzie P (Z = Z

) = p

, dla l = 1, . . . , n + m. Oczywiście

l=1

0
l

= p

oraz

n+m

l=n+1

00
l

= 1 − p

(13.7)

13.3. Metoda modelowania rekurencyjnego w zadaniach.

Opierając się na poniższych założeniach, obliczymy teraz wartość oczekiwaną zmiennej

losowej Z:

E(Z) =

n+m

l=1

0
l

n+m

l=n+1

l−n

00
l−n

l=1

0
l

k=1

00
k

l=1

0
l

p +

k=1

00
k

1 − p

(1 − p) = E(X)p + E(Y )(1 − p)

gdyż z 13.7 wynika, że

l=1

0
l

k=1

0
k

1 − p

= 1

Co kończy dowód lematu.

Znajdziemy teraz zależność rekurencyjną między wartościami oczekiwanymi E(Z

n−1

)

i E(Z

). Niech n jest dowolną liczbą naturalną taką, że n  2. Weźmy dowolną permutację

f = (f

, . . . , f

) zbioru {1, 2, . . . , n}. Po odrzuceniu ostatniego wyrazu f

, otrzymujemy

permutację f

= (f

, . . . , f

n−1

) zbioru {1, 2, . . . , n − 1}. Dołączając z powrotem wyraz f

rozpatrujemy dwa przypadki

1. Jeśli do permutacji f

dołączamy ostatni wyraz ze zbioru {1, 2, . . . , n}, a więc jeśli

= n, wówczas długość ciągu rosnącego zwiększy się o jeden. Prawdopodobieństwo

takiego zdarzenia wynosi

2. Jeśli do permutacji f

dołączamy dowolny wyraz ze zbioru {1, 2, . . . , n − 1}, a więc

długość ciągu rosnącego pozostaje nie zmieniona. Prawdopodobieństwo takiego zda-
rzenia można wyznaczyć korzystając ze wzoru na prawdopodobieństwo dopełnienia.
Zatem wynosi ono: 1 −

Z warunków 1 i 2 otrzymujemy

(

n−1

+ 1

z prawdopodobieństwem

n−1

z prawdopodobieństwem

1 −

Z powyższego zapisu oraz lematu wynika poszukiwana zależność rekurencyjna:

E(Z

) = (E(Z

n−1

) + 1)

+ E(Z

n−1

)

1 −

= E(Z

n−1

) +

Na podstawie indukcji oraz warunku początkowego: E(Z

) = 1 wynika dany do udowod-

nienia w zadaniu wzór

E(Z

) =

k=1

13.3.3

Zadania algebraiczne.

Przykład. Wyznaczyć największą wartość wyrażenia m

+ n

, gdzie m i n są takimi

liczbami całkowitymi, że 1  m  2000, 1  n  2000 oraz (n

− mn − m

)

= 1.

Rozwiązanie.

Lemat 13.2.2 Liczby naturalne k ¬ r spełniają równanie (x

− xy − y

) = 1 wtedy i

tylko wtedy, gdy liczby k + r, r spełniają to równanie.

ROZDZIAŁ 13. Równania rekurencyjne.

Dowód. Ponieważ

[(k + r)

− (k + r)r − r

]

= (k

+ 2kr + r

− kr − r

− r

)

+ kr − r

)

= (r

− kr − k

)

wobec tego (r

− kr − k

)

= 1 wtedy i tylko wtedy, gdy:

((k + r)

) − (k + r)r − r

)

= 1

Koniec dowodu.

Ponieważ para liczb (1, 1) spełnia równanie (x

− xy − y

)

= 1, więc z powyższego

lematu wynika, że równanie to spełnia każda para kolejnych wyrazów ciągu określonego
w następujący sposób:

= a

= 1

= a

k−2

+ a

k−1

k  3

Jest to ciąg Fibonacciego. Wystarczy udowodnić teraz, że żadna para liczb natural-

nych, które nie są kolejnymi wyrazami ciągu Fibonacciego, nie spełnia danego w zadaniu
równania.

Przypuśćmy, że dla liczb naturalnych m ¬ n jest (n

− mn − m

) = 1, przy czym

m, n nie są kolejnymi wyrazami ciągu Fibonacciego oraz n jest najmniejszą liczbą o tej
własności, tzn. każda para liczb naturalnych r ¬ s spełniających warunki (s

−rs−r

)

1 oraz s < n jest parą kolejnych wyrazów ciągu Fibonacciego. Zauważmy, że liczby m,
n − m spełniają dane równanie:

− m(n − m) − (n − m)

)

= (m

− mn + m

− n

+ 2mn − m

)

− mn − n

)

= (n

− mn − m

)

= 1

Jest przy tym m < n, gdyby bowiem było m = n, to musiałoby być m = n = 1 i

liczby te byłyby kolejnymi wyrazami ciągu Fibonacciego. Udowodniliśmy w ten sposób,
że wszystkimi rozwiązaniami danego równania w liczbach naturalnych są pary kolejnych
wyrazów ciągu liczb Fibonacciego. Aby wyznaczyć największą wartość wyrażenia m

+ n

dla m ¬ n spełniających warunki zadania, należy wyznaczyć największy wyraz ciągu
Fibonacciego nie przekraczający 2000. Wypisując kolejne wyrazy tego ciągu:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, . . .

stwierdzamy, że szukaną wartością jest:

987

+ 1597

= 3514478

Przykład. Znaleźć rozwiązanie równania a

+ b

+ c

= 3abc w liczbach naturalnych

a, b, c nie większych od n.

Rozwiązanie. Zauważmy na początku, że rozwiązaniem danego równania są liczby:

(1, 1, 1), (2, 1, 1), (5, 2, 1), (13, 5, 1), . . . , itd. Pokażemy teraz (co łatwo zauważyć), że jeśli
trójka liczb naturalnych (a, b, c) (gdzie a > b > c) stanowi rozwiązanie danego równania,
to rozwiązaniem tego równania jest trójka liczb postaci:

(3ab − c, a, b)

przy czym 3ab − c > 3a − c > a.

13.3. Metoda modelowania rekurencyjnego w zadaniach.

Przekształcając lewą stronę danego równania i korzystając z założenia:

(3ab − c)

+ a

+ b

= 9a

− 6abc + c

+ a

+ b

− 6abc + 3abc = 9a

− 3abc = 3(3ab − c)ab

otrzymujemy prawą stronę równania, co należało pokazać.

Rozważmy teraz ciąg (b

) określony w następujący sposób:

= b

= 1

k+2

= 3b

k+1

− b

k  1

Udowodnimy indukcyjnie, że każda z trójek

k+1

, b

, 1)

k  1

spełnia dane równanie. (1, 1, 1) jest rozwiązaniem. Załóżmy, że (b

k+1

, b

, 1) jest rozwiąza-

niem, a więc

2
k+1

+ b

2
k

+ 1

= 3b

k+1

Pokażemy, że (b

k+2

, b

k+1

, 1) jest rozwiązaniem, czyli:

2
k+2

+ b

2
k+1

+ 1

= 3b

k+2

k+1

W tym celu przekształćmy lewą stronę równości tezy:

L = b

2
k+2

+ b

2
k+1

+ 1

= (3b

k+1

− b

)

+ b

2
k+1

+ 1 =

2
k+1

− 6b

k+1

+ b

2
k

+ b

2
k+1

+ 1 = 9b

2
k+1

− 6b

k+1

+ 3b

k+1

2
k+1

− 3b

k+1

Przekształćmy teraz prawą stronę równości tezy:

P = 3b

k+2

k+1

= 3(3b

k+1

− b

) = 9b

2
k+1

− 3b

k+1

Zatem L = P .

Na mocy zasady indukcji każda trójka (b

k+1

, b

, 1) dla k  1 spełnia dane równanie.

Na podstawie przeprowadzonego wyżej rozumowania stwierdzamy ponadto, że trójka

(3b

k+1

− 1, b

k+1

)

k  1

jest rozwiązaniem danego równania. Wszystkie trzy liczby występujące w tej trójce są nie
mniejsze niż k, bo (b

) jest rosnącym ciągiem liczb naturalnych.

Znajdziemy teraz wyraz ogólny ciągu (b

). Zależności rekurencyjnej występującej w

definicji tego ciągu odpowiada wielomian charakterystyczny:

f (x) = x

− 3x + 1

którego pierwiastkami są liczby x

3−

√

, x

√

. Otrzymujemy zatem (na podsta-

wie metody podanej w rozdziale 4)

= c

k
1

+ c

k
2

= c

3 −

√

+ c

3 +

√

k  1

ROZDZIAŁ 13. Równania rekurencyjne.

Ponieważ b

= 1, b

= 1, więc stałe c

, c

spełniają zależności:

3 −

√

+ c

3 +

√

= 1

3 −

√

+ c

3 +

√

= 2

Rozwiązując powyższy układ otrzymujemy, że c

√

, c

5−

√

. Ostatecznie dosta-

jemy następujący wzór ogólny ciągu (b

5 +

√

3 −

√

5 −

√

3 +

√

k  1

Rozwiązaniem danego w zadaniu równania w liczbach naturalnych większych od n są
trójki liczb postaci:

(3b

k+1

− 1, b

k+1

, b

)

k > n

Rozdział 14

Modelowanie okrężne. ([14],
[18])

Twierdzenie 14.1

n+1

k=1

2k − 1

n−(2k−1)

− 1)

(14.1)

Dla n = 1 mamy L = P = 1, potraktujmy 14.1 jako założenie indukcyjne i udowodnimy

c+1

k=1

n + 1

2k − 1

n+1−(2k−1)

n+1

− 1)

(14.2)

Dowód.

L =

k=1

2k − 1

n+1−(2k−1)

k=1

2(k − 1)

n−2(k−1)

n + 1

c + 1

n−2[

]

lecz

k=1

2(k − 1)

n−2(k−1)

c−1

k=0

n−2k

k=0

n−2k

−

n−2[

]

+ 1) −

n−2[

]

także

k=1

2k − 1

n+1−(2k−1)

= 2

n+1

k=1

2k − 1

n−(2k−1)

−

[1 + (−1)

n−1

]

2(3

− 1) − [1 + (−1)

n−1

]

ROZDZIAŁ 14. Modelowanie okrężne.

oraz

n + 1

c + 1

n−2[

]

−

n−2[

]

n−2b

n + 1

] + 1

− 1

]

= [1 + (−1)

n−1

]

L = 2

k=1

2k − 1

n−(2k−1)

k=0

n−2k

−

n−2[

]

n + 1

c + 1

n−2b

mamy, że

k=0

n−2k

+ 1)

oraz

−

n−2[

]

n + 1

c + 1

n−2[

]

n−2[

]

n + 1

] + 1

− 1

n−2b

n − 2b

c + 1

Tak więc dla n-parzystego mamy

L = 2 ·

− 1) +

+ 1) − 1 + 1 =

n+1

− 1)

a dla n-nieparzystego

L = 2

n+1

k=1

2k − 1

n−(2k−1)

− 1

+ 1) − 2n + 2(n + 1) =

n+1

− 1)

n+1

k=1

2k − 1

n−2(k−1)

k=1

2k − 1

n−(2k−1)

(1 − 1

n−1

)

Wystarczy pokazać, że

k=1

2k − 1

+ 2

2k − 2

2p−(2k−1)

k=2

2k − 3

2p−(2k−1)

2(2p + 2)

k=0

2(p−k)

+ 2

k=1

2k − 1

2(p−k)

k=1

2k − 2

2(p−k)

Podstawiamy a =

p
k=1

2k−1

, b = P

p
k=0

2p
2k

2(p−k)

, a = b−1 z założenia indukcyjnego.

k=1

2k − 2

2[p−(k−1)]

p−1

k=0

2(p−k)

k=0

2(p−k)

− 1 = b − 1

k=2

2k − 3

2p−(2k−1)

k=2

2k − 3

2p−(2k−3)

k=1

2k − 1

2p−(2k−1)

− 4p

L = a + b − 1 +

(a − 4p) + p + 1 = a + b +

P = b + a +

(b − 1)

k=1

2(k − 1)

2[p−(k−1)]

p−1

k=0

2[p−k]

k=0

2(p−k)

− 1

czyli

L = 2 ·

− 1) − [1 + (−1)

n−1

] +

+ 1) + [1 + (−1)

n−1

] =

n+1

− 1)

Trudniejsze relacje pomocnicze:

n+1

k=1

2k − 1

n−(2k−1)

k=1

2k − 1

n−(2k−1)

[1 + (−1)

n−1

]

(1 + (−1)

n+1

) + 1

Stwierdzenie 14.1.1 Powyższy wynik można uzyskać znacznie prościej stosując metodę
modelowania okrężnego.

W przypadku pierwszym wystarczy rozwiązać następujące zadanie. Losujemy n-krotnie
ze zwracaniem kule z urny, w której znajdują się 3 kule oznaczone cyframi 0, 1, 2. Tworzy-
my sumy wylosowanych liczb odpowiadających cyfrom znaczącym kule. Ile jest różnych
układów różnych układów losowań, przy których uzyskana suma jest liczbą nieparzystą?

ROZDZIAŁ 14. Modelowanie okrężne.

Rysunek 14.1: Modelowanie okrężne. T – transformacja, R – procedura rozwiązania pro-
blemu, T

−1

transformacja odwrotna, P – problem, P

– problem po transformacji, W

–

wynik w postaci transformowanej, W – poszukiwany wynik.

Lewa strona twierdzenia 14.1 przedstawia model kombinatoryczny problemu. Podczas

gdy z prawej strony mamy model ciągu rekurencyjnego. Ustalamy model kombinatoryczny
rozłącznych zdarzeń polegający na wypadnieciu różnej nieparzystej liczby jedynek, w spo-
sób niezależny rozmieszczając je w ciągu n-elementowym, w dowolny sposób zmieniając
pozostałe elementy wybrane ze zbioru {0, 2}. Czyli mnożymy kombinacje k nieparzystych
elementów wybranych spośród n przez wariacje z powtórzeniami (n − k)-elementowe o
dwóch wartościach i sumujemy otrzymane iloczyny po wszystkich nieparzystych k takich,
że k ¬ n. Model rekurencyjny, czyli prawą stronę wzoru, uzyskujemy spostrzegając, że
nieparzystość sumy po n-tym losowaniu otrzymamy przy wyciągnięciu „1” – gdy po n − 1
losowaniach suma była parzysta; oraz przy wyciągnięcu „0” lub „2” gdy odpowiadająca
suma była nieparzysta. Zauważmy tu, że efektywność i wyjściowa elegancja modelu re-
kurencyjnego w stosunku do kombinatorycznego, wynika z ukrytego porządku liniowego
następstw zdarzeń. Ilość układów nie zależy od techniki przeliczania (rodzaju modelu),
to lewa strona twierdzenia 14.1 jest równa prawej stronie.

Rozdział 15

Zadania. ([1], [4], [7], [10], [11],
[19], [21])

15.1

Zadania do rozdziałów.

15.1.1

Rozdziały 1–2.

Zadanie 1. Przeprowadzić dowody indukcyjne następujących twierdzeń i zależności.

1. Dla każdego n ∈ N ilość wszystkich podzbiorów zbioru n-elementowego jest równa

2. p | n

− n gdzie p jest liczbą pierwszą, n ∈ N.

3. (1 + a)

1 + na

a > −1

a ∈ R (nierówność Bernoulliego)

4. 2

> n

5. 13 | 6

n+2

+ 7

2n+1

6. n! > 2

n  4

7. n!

√

n
k

k−1

n+1

n > 1 n k > 1

9. ∀n ∈ N i f orallk ¬ n ilość wszystkich k-elementowych kombinacji zbioru n-

elementowego jest równa

n
k

10. 1

+ 2

+ . . . + n

n(n+1)(2n+1)

11. sin α + sin 2α + . . . + sin nα =

cos

1
2

α−cos(n+

1
2

)α

2 sin

1
2

12. 2

> n

n > 4

13. (a + b)

n
k=0

n
k

n−k

14. Jeżeli suma cyfr w liczbie b jest podzielna przez 9 to 9 | b.

ROZDZIAŁ 15. Zadania.

15. 6 | 10

− 4

16. 9 | n

+ (n + 1)

+ (n + 2)

Zadanie 2. Znaleźć granice ciągów określonych rekurencyjnie.

(

√

n+1

√

∀n

(

= sin 1

◦

n+1

= sin a

(

√

n+1

√

3 + a

Zadanie 3. Określamy ciąg za pomocą wzoru rekurencyjnego:

(

= 6

= 18

n+2

= 2a

n+1

+ 8a

− 18

Dowieść za pomocą indukcji, że a

= 4

+ 2

(

= 1

n+2

= a

+ a

n+1

Ciąg Fibonacciego.

Wykazać, że a

√

−

1−

√

Zadanie 4. Przedział ha, bi dzielmy punktem x

na połowę. Otrzymaną prawą połowę

dzielimy punktem x

na połowy. Z punktami x

; n > 2 postępujemy analogicznie. Wykaż,

że lim

n→∞

= 6.

Zadanie 5. Wypisz pięć pierwszych wartości x dla każdego z następujących fragmentów

algorytmów:

1. x:=0

DOPÓKI 0=<x WYKONUJ
x:=2x+3

2. x:=1

DOPÓKI x>=0 WYKONUJ
x:=2x+3

3. x:=1

DOPÓKI x>=0 WYKONUJ
x:=2x-1

Zadanie 6. Znajdź liczbę całkowitą b taką, że ostatnią wypisaną liczbą będzie 6.

1. n:=0

DOPÓKI n<b WYKONUJ
wypisz n
n:=n+1

15.1. Zadania do rozdziałów.

2. n:=0

DOPÓKI n<0 WYKONUJ
n:=n+1
wypisz n

Zadanie 7. Pokaż, że podane warunki są niezmiennikami pętli:

1. DOPÓKI 1=<n WYKONUJ

m:=m+1
n:=n+1
(

2 | m + n

2 - m + n

2. DOPÓKI 1=<m WYKONUJ

m:=2m
n:=3n
(

 m

< n

Zadanie 8. Rozważmy pętlę:

DOPÓKI j>=n WYKONUJ
i:=i+2
j:=j+1

i, j ∈ Z. Czy poniższe warunki są niezmiennikami pętli?

1. i < j

n = 1

2. i < j

n = 0

3. i =< j

n = 0

4. i >= j

n = 0

Zadanie 9. Rozważmy pętlę:

DOPÓKI k>=1 WYKONUJ
k:=2k

Sprawdź czy poniższe warunki są niezmiennikami pętli:

1. k

≡ 1 mod 3

2. k

≡ 1 mod 4

Zadanie 10. Dla jakich wartości liczby całkowitej b, każdy z następujących algorytmów

zakończy działanie?

1. k:=b

DOPÓKI k<5 WYKONUJ
k:=2k-1

ROZDZIAŁ 15. Zadania.

2. k:=b

DOPÓKI k<>5 WYKONUJ
k:=2k-1

3. k:=b

DOPÓKI k<5 WYKONUJ
k:=2k+1

Zadanie 11. Czy dwa poniższe algorytmy dają ten sam wynik?

1. m:=1

n:=1
DOPÓKI 1=<m=<3 WYKONUJ
m:=2m
n:=n+1
wypisz m

2. m:=1

n:=1
DOPÓKI 1=<m=<3 i 1=<n=<3 WYKONUJ
m:=2m
n:=n+1
wypisz m

Zadanie 12. Dla poniższej pętli sprawdź:

DOPÓKI 1=<I WYKONUJ
S:=S+2I+1
I:=I+1

1. Że, warunek S = I

jest niezmiennikiem pętli.

2. Że, warunek S = I

+ 1 też jest niezmiennikiem tej pętli.

3. Jaka będzie siedemdziesiąta trzecia liczba wypisana przez ten algorytm? Odpowiedź

uzasadnij.

Zadanie 13. Które z nastepujących zbiorów liczb całkowitych mają najmniejszy ele-

ment na podstawie zasady dobrego uporządkowania? Odpowiedź uzasadnij.

1. P = Z

2. Z

3. {n ∈ N n

17}

4. {n ∈ N n

< 0}

5. {n ∈ Z n

> 17}

6. {n ∈ N n! > 80}

Zadanie 14. Czy warunek 5

< k! jest niezmiennikiem następującej pętli?

15.1. Zadania do rozdziałów.

DOPÓKI 4=<k WYKONUJ
k:=k+1

Czy na tej podstawie można wywnioskować, że 5

< k! ∀k  4?

Zadanie 15. Oto algorytm który rozkłada liczbę całkowitą n na iloczyn liczby niepa-

rzystej i potęgi 2.

m:=n
k:=0
DOPÓKI m jest parzyste WYKONUJ
m:=m/2
k:=k+1

Pokazać, że warunek m2

= n jest niezmiennikiem pętli.

Zadanie 16. Udowodnij, że

4 + 10 + 16 + . . . + (6n − 2) = n(3n + 1)

n ∈ N

Zadanie 17. Udowodnij, że:

1. 10 | 37

100

− 37

2. 10 | 37

− 37

3. 10 | 37

500

− 37

4. 10 | 37

− 1

5. 10 | 37

500

− 1

6. 7 | 11

− 4

7. 16 | 5

− 4n − 1

8. 8 | 5

n+1

+ 2 · 3

+ 1

9. 73 | 8

n+2

+ 9

2n+1

Zadanie 18. Udowodnij, że:

1 · 5

5 · 9

9 · 13

+ . . . +

(4n − 3)(4n + 1)

4n + 1

∀n ∈ N

Zadanie 19. Pokaż przez indukcję, że jeśli s

= a oraz s

= 2s

n−1

+ b ∀n ∈ N, to

= 2

a + (2

− 1)b ∀n ∈ N.

Zadanie 20. Pokaż, że warunek

k
i=0

= 2

k+1

− 1 jest niezmiennikiem pętli w algo-

rytmie:

k:=0
DOPÓKI 0=<k WYKONUJ
JESLI suma od i=0 do k po 2^i=2^(k+1) TO
k:=k+1

Zadanie 21. Udowodnij, że:

ROZDZIAŁ 15. Zadania.

n
i=1

√

n
i=1

√

¬ 2

√

n − 1

Zadanie 22. Udowodnij, następujące zależności:

1. | sin nx| ¬ n| sin x|

x ∈ R ∧ n ∈ N

2. 1

+ 2

+ . . . + n

= (1 + 2 + 3 + . . . + n)

15.1.2

Rozdziały 3–4.

Zadanie 23. Udowodnić, że następujące zależności rekurencyjne mają wzór jawny.

= 1

= 2

= 4

= b

n−1

+ b

n−2

+ 2b

n−3

= a

= 2s

n−1

+ b

Zadanie 24. Definiujemy ciąg:

(

= a

= 1

= a

n−1

+ a

n−2

+ a

n−3

n  3

Udowodnij, że wszystkie a

¬ 2

n−1

∀n ∈ N

Zadanie 25. Udowodnić następujące nierówności:

1. (1 + a)

1 + na +

n(n−1)

a  0

n  0

√

n ¬ 1 +

3. 2 ¬ (1 +

)

¬ n + 1

n  1

4. (x

+ x + 1) | ((x + 1)

2n+1

+ x

n+2

)

5. n!

√

6. n! <

n+1

Zadanie 26. Ciąg liczb (a

) jest określony następująco:

(

= a

= 1

2
n−1

n−2

Wykazać, że wszystkie wyrazy tego ciągu są liczbami całkowitymi.

Zadanie 27. Niech ciąg (c

) będzie określony następująco:

(

a
2

n+1

a+c

2
n

a ∈ (0, 1i

Pokazać, że wszystkie wyrazy ciągu (b

), gdzie b

= 1 −

√

1 − a − c

są dodatnie.

100

15.1. Zadania do rozdziałów.

15.1.3

Rozdział 4.

Zadanie 28. Definiujemy rekurencyjnie s

= 1 i s

n+1

. Wypisz pięć pierwszych

wyrazów ciągu i wyznacz jego zbiór wartości.

Zadanie 29. Definiujemy rekurencyjnie SEQ(0) = 0 i SEQ(n + 1) =

1+SEQ

n ∈ N.

Oblicz SEQ(n) dla n = 1, 2, 3, 4 oraz 6.

Zadanie 30. Weźmy ciąg SEQ: (1, 3, 9, 27, 81, . . .). Podaj wzór na n-ty wyraz ciągu

SEQ(n) gdzie SEQ(0) = 1 oraz jego definicję rekurencyjną.

Zadanie 31. Podaj definicję rekurencyjną ciągu 2, 2

, 2

, . . ., czyli ciągu 2, 4, 16, 256,

. . ..

Zadanie 32. Czy następująca definicja jest definicją rekuencyjną ciągu SEQ? Odpo-

wiedź uzasadnij.

(

SEQ(0) = 1

SEQ(n + 1) =

SEQ(n)

(100−n)

Zadanie 33. Oblicz:

1. SEQ = 9 gdzie

(

SEQ(0) = 1

SEQ(n + 1) =

n+1

SEQ(n)

n ∈ N

2. F IB(11) gdzie

(

FIB(0) = FIB(1) = 1

FIB(n) = FIB(n − 1) + FIB(n − 2)

n  2

Zadanie 34. Niech Σ = {a, b, c} – alfabet i niech s

oznacza liczbę słów długości n które

nie mają kolejnych liter a. Oblicz s

, s

, znajdź wzór rekurencyjny na s

i następnie

oblicz s

i s

Zadanie 35. Niech Σ = {a, b} – alfabet dwuliterowy i niech s

oznacza liczbę słów

długości n, w których jest parzysta liczba liter a. Oblicz s

, s

i znajdź wzór

rekurencyjny na s

Zadanie 36. Niech Σ = {a, b} i niech s

oznacza liczbę słów długości nnie zawierających

ciągu ab. Oblicz s

, s

oraz znajdź wzór na s

Zadanie 37. Weźmy ciąg SEQ(0) = 1, SEQ(1) = 0 SEQ(n) = SEQ(n − 2) n  2.

Wypisz pieć wyrazów tego ciągu, określ zbiór jego wartości.

Zadanie 38. a

= a

= 1

= a

n+1

+ 2a

n−2

n  2. Obliczyć a

i udowodnić, że

∀n ∈ N są nieparzyste.

Zadanie 39. Udowodnij, że ciąg macierzy M

, M

określony wzorami

1 1

2 1

FIB(n)

FIB(n − 1)

FIB(n − 2)

n  2

spełnia zależność M

n+1

= M

· M

Zadanie 40. Definiujemy rekurencyjnie ciąg za pomocą wzoru b

= b

= 1 b

n−1

+ b

n−2

n  2. Oblicz b

metodą iteracyjną oraz udowodnij, że wszystkie wyrazy

tego ciągu są nieparzyste.

Zadanie 41. SEQ(0) = 1 i niech SEQ(n) =

n−1
i=0

SEQ(i)

n  1. Okazuje się, że jest

to znany prosty ciąg. Jaki?

101

ROZDZIAŁ 15. Zadania.

Zadanie 42. Definiujemy rekurencyjnie ciąg wzorem a

= 0, a

= 1, a

= 2 a

n−1

− a

n−2

+ a

n−3

n  3. Wypisz pięć pierwszych wyrazów tego ciągu. Jaki jest zbiór

wartości tego ciągu?

Zadanie 43. Proces przydzielania n dzieci do n miejsc w klasie może być podzielony

na dwie fazy:

1. Wybór dziecka na pierwsze miejsce.

2. Przydzielenie pozostałych n − 1 dzieci do n − 1 miejsc.

Niech A(n) będzie liczbą różnych usadzeń n dzieci na n miejscach. Napisz definicję reku-
rencyjną ciągu A. Oblicz rekurencyjnie A(6). Czy ciąg A wydaje ci się znajomy.

Zadanie 44. Weźmy pod uwagę proces przydzielania 2n dzieci do n wagoników kolejki,

tak by w każdym wagoniku była dwójka dzieci. Najpierw wybieramy dwoje dzieci do
pierwszego wagonika na C

2n(2n−1)

sposobów. Następnie przydzielamy pozostałe

dzieci do n−1 wagoników. Niech B(n) będzie liczbą sposobów, na które można przydzielić
2n dzieci do n wagoników. Napisz definicję rekurencyjną B(n). Oblicz rekurencyjnie B(3)
oraz metodą iteracyjną B(5). Podaj wzor ogólny na B(n).

Zadanie 45. Weźmy ciągi określone wzorami

FOO(0) = 1

FOO(1) = 1

FOO(n) =

10FOO(n − 1) + 100

FOO(n − 2)

n  2

GOO(0) = 1

GOO(1) = 2

GOO(n) =

10GOO(n − 1) + 100

GOO(n − 2)

n  2

Zadanie 46. Niech (a

, a

, . . .) będzie ciągiem liczb rzeczywistych. Podaj definicję re-

kurencyjną ciągu suma(n) =

n
j=1

, n  1. Zmień twoją definicję rekurencyjną ciągu

suma(n), zaczynając od n = 0. Co to jest „suma pusta”?

Zadanie 47. Niech (A

, A

, . . .) będzie ciągiem podzbiorów pewnego zbioru S.

1. Podaj definicję rekurencyjną dla

n
j=1

. Jak zdefiniować sumę pustą?

2. Podaj definicję rekurencyjną dla

n
j=1

. Jak zdefiniować puste przecięcie?

Zadanie 48. Udowodnij, że jeśli s

= as

n−1

dla n  1 i a 6= 0, to s

= a

dla n ∈ N.

Zadanie 49. Sprawdź, że ciąg s

dany wzorem

1. s

= 2

n+1

+ (−1)

spełnia warunki s

= s

= 3 s

= s

n−1

+ 2s

n−2

2. s

= 3

− 2n3

spełnia warunki s

= 1, s

= −3 s

= 6s

n−1

Zadanie 50. Podaj wzór jawny na s

, gdzie

1. s

= 3

= −2s

n−1

n  1

2. s

= 4s

n−2

= s

= 1

3. s

= s

n−1

+ 2s

n−2

= 3

= 6

4. s

= s

n−1

+ 2s

n−2

= 3

= −3

5. s

= s

n−1

+ s

n−2

= 1

= 2

102

15.1. Zadania do rozdziałów.

6. s

= s

n−1

+ s

n−2

= 2

= 1

n  2. Oblicz s

dla n = 2, 3, 4, 5, 6.

7. s

= −s

n−1

+ 6s

n−2

= 2

= 1

n  2

8. s

= 5s

n−1

= 2

n  1

9. s

= 4s

n−1

− 4s

n−2

= 1

= 8

n  2

Zadanie 51. W każdym z następujących przypadków podaj wzór jawny na s

1. s

= 3s

+ 3

= 1

2. s

= 2s

= 3

3. s

= 2s

+ 5n

= 0

4. s

= 2s

+ 3 + 5n

= 2

5. s

= 2s

− 7

= 1

Zadanie 52. Przypuścmy, że ciąg (s

) spełnia zależność rekurencyjną s

= 2s

+ n

Podaj wzór na s

oraz uzasadnij, że jest on poprawny.

Zadanie 53. Jeśli s

będzie ciągiem rekurencyjnym spełniającym zależność rekuren-

cyjną postaci

= 2s

+ f (n)

n ∈ N

to wtedy

= 2

m−1

j=0

f (2

)

. Sprawdź tą zależność dla f (n) = A + Bn.

Zadanie 54. Definiujemy rekurencyjnie ciąg (a

) wzorami











= 1

= 2

n−1

n−2

n  2

oraz (b

)











= 1

= 2

n−1

−1

n−2

n  2

Oblicz kilka pierwszych wyrazów tych ciągow oraz zgadnij ich wzory ogólne na tej pod-
stawie. Udowodnij je.

Zadanie 55. Definiujemy rekurencyjnie ciąg (a

)











= 1

= 2

= 3

= a

n−2

+ 2a

n−3

n  3

Oblicz a

dla n = 3, 4, 5, 6, 7. Udowodnij, że a

3
2

n  1.

103

ROZDZIAŁ 15. Zadania.

Zadanie 56. Definiujemy rekurencyjnie ciąg a











= 1

= 3

= 5

= 3a

n−2

+ 2a

n−3

n  3

Oblicz a

dla n = 3, 4, 5, 6, 7. Udowodnij, że a

> 2

dla n  1, a

< 2

n+1

dla n  1

oraz, że a

= 2a

n−1

+ (−1)

n−1

n  1.

Zadanie 57. Definiujemy rekurencyjnie ciąg a

(

= a

= 1

= a

n−1

+ a

n−3

n  3

Oblicz a

dla n = 3, 4, 5, 6. Udowodnij, że a

> (

√

n−2

dla n  2 oraz, że a

< (

3
2

)

n−1

dla n  1.

Zadanie 58. Definiujemy rekurencyjnie ciąg SEQ(n) za pomocą wzorów

(

SEQ(0) = 0

SEQ(1) = 1

SEQ(n) =

SEQ(n − 1) +

n−1

SEQ(n − 2)

n  2

Udowodnij, że 0 SEQ(n) 1 dla n ∈ N.

Zadanie 59. Rozważmy ciąg Fibonacciego

FIB(0) = FIB(1) = 1FIB(n) = FIB(n − 1) + FIB(n − 2)

n  2

Udowodnij, że FIB(n) = 1 +

n−2
k=0

FIB(k) dla n  2.

15.1.4

Rozdziały 5–6.

Zadanie 60. Ile różnych wyników można otrzymać przy rzucaniu dwoma kostkami do gry,
jeśli

1. kostki są rozróżnialne

2. kostki są nierozróżnialne

3. rozróżniamy wyniki w zależności od sumy wyrzuconych oczek

Zadanie 61. Ile liczb 4-cyfrowych można utworzyć z cyfr 1, 2, 3, 4 tak aby żadna cyfra

w liczbie nie powtarzała się a ile takich w których dopuszczalne są powtórzenia

Zadanie 62. Ile liczb czterocyfrowych można utworzyć z cyfr 0, 1, 2, 3, tak aby żadna

cyfra w liczbie nie powtarzała się?

Zadanie 63. W urnie znajduje się n kul ponumerowanych i m kul bez numerów. Ku-

le wyjmujemy z urny jedną po drugiej i układamy w rząd. Ile jest różnych rezultatów
ciągnienia przy założeniu, że kule nienumerowane są nierozróżnialne?

Zadanie 64. Na 4 różne posady zgłosiło się 20 kandydatów. Na ile sposobów można

obsadzić te posady?

Zadanie 65. Ile różnych słów pięcioliterowych można utworzyć z 24 liter przy założeniu,

że każda litera może występować w słowie dokładnie jeden raz? Ile ich jest jeśli mogą
występować powtórzenia?

104

15.1. Zadania do rozdziałów.

Zadanie 66. Ile można utworzyć liczb trzycyfrowych z cyfr 1, 2, 3, 4, 5?
Zadanie 67. Ile istnieje liczb trzycyfrowych?
Zadanie 68. Ile słów można utworzyć z 18 spółgłosek i 6 samogłosek, jeżeli każde słowo

składa się z 2 samogłosek i 3 spółgłosek oraz samogłoski zajmują 2 i 4 miejsce?

Zadanie 69. Iloma sposobami można z 18 osób utworzyć 3 drużyny sześcioosobowe?
Zadanie 70. Ile prostych można utworzyć z n punktów przestrzeni jeśli wiadomo, że m

punktów leży w jednej płaszczyźnie, a poza tym żadne 4 nie leżą w jednej płaszczyźnie.

Zadanie 71. W kwiaciarni są trzy gatunki kwiatów. Ile różnych bukietów można utwo-

rzyć z 10 kwiatów.

Zadanie 72. W skład 5-osobowej komisji wchodzą przedstawiciele 10 narodów. Iloma

sposobami można taką komisję utworzyć przy założeniu, że komisja nie może składać się
wyłącznie z przedstawicieli jednego narodu.

Zadanie 73. Każdą krawędź sześcianu podzielono na n równych części i przez każdy

punkt podziału poprowadzono płaszczyznę prostopadłą do tej krawędzi. Ile prostopadlo-
ścianów powstaje w wyniku tego podziału?

Zadanie 74. Na sali mamy n osób. Na ile sposobów można wymienić uscisk dłoni?
Zadanie 75. Pewna grupa studencka składa się z 212 mężczyzn i 16 kobiet. Ile da się

z nich utworzyć komisji składających się z

1. 7 osób

2. 3 mężczyzn i 4 kobiet

3. 7 kobiet lub 7 mężczyzn

Zadanie 76. Ile można utworzyć komisji składających się z 4 osób wybranych z 9

osobowej grupy? A ile przy założeniu, że są dwie osoby, które nie chcą być w tej samej
komisji?

Zadanie 77. Niech S = {a, b, c, d} T = {1, 2, 3, 4, 5, 7}.

1. Ile jest funkcji różnowartościowych z T w S?

2. Ile jest funkcji różnowartościowych z S w T ?

3. Ile jest funkcji z S w T ?

Zadanie 78. Niech P = {1, 2, 3, . . . , 9}, Q = {A, B, C, D, E}

1. Ile jest czteroelementowych podzbiorów zbioru P ?

2. Ile jest permutacji zbioru Q.

3. Ile jest numerów rejestracyjnych składających się z trzech liter ze zbioru Q i nastę-

pujących po nich dwóch cyfr ze zbioru P ? Powtórzenia są dozwolone.

Zadanie 79. Niech Ω będzie zbiorem uporządkowanych n-tek z powtórzeniami złożo-

nych z cyfr 1, 2, 3. Wyznaczyć liczbę elementów Ω, które:

1. rozpoczynają się od 1

2. zawierają dokładnie k+2 jedynek, przy czym rozpoczynają się i kończą 1, a n k+2.

3. zawierają dokładnie k dwójek n k

105

ROZDZIAŁ 15. Zadania.

4. są złożone z k

jedynek, k

dwójek, k

trójek, gdzie k

+ k

= n.

Zadanie 80. W n różnych komórkach rozmieszczono k rozróżnialnych cząstek b

, . . . , b

przy czym k n i komórka może zawierać nie więcej niż 1 cząstkę. Obliczyć liczbę
wszystkich sposobów rozmieszczenia przy których

1. w komórce a

znajduje się cząstka b

2. w komórkach a

, a

znajdują się cząstki b

, b

Zadanie 81. Numer telefoniczny, może się rozpoczynać od każdej z cyfr 0, 1, 2, . . ., 9.

Obliczyć liczbę sześciocyfrowych numerów telefonów, w których wszystkie cyfry są:

1. różne

2. nieparzyste

Zadanie 82. Spośród n osób należy wybrać r osób. Następnie z r osób należy wybrać k

członków zarządu. Pozostali utworzą komisję rewizyjną. Na ile sposobów można wybrać
zarząd i komisję rewizyjną. Czy liczba wyborów będzie taka sama gdy najpierw wybierze
się k członków zarządu a z pozostałych n − k osób wybierze się r − k członków komisju
rewizyjnej?

Zadanie 83. Ile dzielników ma liczba 2 · 3 · 5 · 7 · 11.
Zadanie 84.

1. Wyjaśnij, dlaczego wsród dowolnych czterech liczb całkowitych dwie muszą przy-

stawać

mod 3.

2. Udowodnij, że jeśli a

, . . . , a

p+1

są całkowite, to dwie muszą przystawać

mod p.

Zadanie 85. Przypuścmy, że 73 kulki zostały umieszczone w ośmiu pudełkach. Wykaż,

że

1. jedno z pudełek zawiera co najmniej 10 kulek

2. jeśli dwa pudełka są puste, to jakieś pudełko zawiera co najmniej 13 kule

Zadanie 86. Niech B będzie dwunastoelementowym podzbiorem zbioru {1, 2, . . . , 6} ×

{1, 2, . . . , 6}.

1. Wykaż, że B zawiera dwie różne pary uporządkowane, mające różne sumy elemen-

tów, poprzednika i następnika.

2. Ile razy można rzucić parą kostek bez dwukrotnego otrzymania tej samej liczby

oczek?

Zadanie 87. Worek zawiera 50 szklanych kulek w 4 różnych kolorach.

1. Wyjaśnij dlaczego jest co najmniej 13 kulek tego samego koloru.

2. Jeśli czerwonych kulek jest dokładnie 8, to wyjaśnij dlaczego jest co najmniej 14

kulek tego samego koloru

106

15.1. Zadania do rozdziałów.

Zadanie 88. Niech A będzie dziesięcioelementowym podzbiorem zbioru {1, 2, 3, . . . , 50}.

Wykazać, że A ma dwa różne czteroelementowe podzbiory, których sumy elementów są
równe.

Zadanie 89. Niech A będzie podzbiorem zbioru {1, 2, 3, . . . , 149, 150} złożonym z 25

liczb. Wykaż, że istnieją dwie rozłączne pary elementów zbioru A, mające te równe sumy.

Zadanie 90. Weźmy 9 nieujemnych liczb rzeczywistych a

, a

, . . . , a

, których suma

jest równa 90.

1. Pokazać, że wśród tych liczb muszą istnieć trzy takie, których suma równa się co

najmniej 30.

2. Pokażemy, że wśród tych liczb muszą istnieć cztery takie, których suma równa się

co najmniej 40

Zadanie 91. Urna zawiera M czarnych i N − M białych kul (M < N ). Dokonujemy

wyboru losowej próbki bez zwracania o liczności n (n < N , n < N − M ). Obliczyć
prawdopodobieństwo tego, że próbka zwiera dokładnie k czarnych kul (k ¬ n, k ¬ M )

Zadanie 92. Cyfry 1, 2, 3, 4, 5 zapisane są na 5 kartkach. Wybierzmy losowo jedną po

drugiej trzy kartki i zapisujemy umieszczone na nich cyfry w kolejności losowania. Obliczyć
prawdopodobieństwo, że otrzymana w ten sposób liczba będzie parzysta.

Zadanie 93. Zamek cyfrowy zawiera 5 dysków osadzonych na wspólnej osi. Każdy

z nich jest podzielony na 6 sektorów oznaczonych różnymi literami. Zamek otwiera się
tylko wtedy, gdy każdy dysk zajmie pewną określoną pozycję względem korpusu zamka.
Obliczyć prawdopodobieństwo otwarcia zamka po ustawieniu losowo wybranej kombinacji
liter na dyskach.

Zadanie 94. Obliczyć prawdopodobieństwo, że numer losowo wybranej obligacji nie

zawiera jednakowych cyfr, jeśli numer ten może być dowolną liczbą pięciocyfrową, poczy-
nając od 00001.

Zadanie 95. Grupa składająca się z 2n siada w sposób losowy wokół okrągłego stołu.

Obliczyć prawdopodobieństwo, że dwie z góry ustalone osoby

1. usiądą obok siebie

2. nie będą sąsiadować ze sobą

Zadanie 96. W pudełku znajduje się pięć jednakowych klocków, przy czym trzy z nich

są pomalowane. Losowo wyciągnięto dwa klocki. Znaleźć prawdopodobieństwo tego, że
wśród wyciągnietych dwóch klocków jest

1. jeden pomalowany

2. dwa pomalowane

3. co najmniej jeden pomalowany

Zadanie 97. W magazynie znajduje się 15 kineskopów, w tym 10 jest wyprodukowanych

przez zakłady X. Znaleźć prawdopodobieństwo tego, że wśród losowo wybranych pięciu
kineskopów będą trzy kineskopy produkcji X.

Zadanie 98. Wykręcając numer telefonu abonent zapomniał ostatnie trzy cyfry. Pamię-

tając tylko, że te cyfry są różne wykręcił je na chybił trafił. Znaleźć prawdopodobieństwo
tego, że znalazł właściwy numer.

Zadanie 99. Pomyślano dwucyfrową liczbę, której cyfry są różne. Znaleźć prawdopo-

dobieństwo tego, że okaże się równa pomyślanej liczbie

107

ROZDZIAŁ 15. Zadania.

1. przypadkowa liczba dwucyfrowa

2. przypadkowa liczba dwucyfrowa, której cyfry są różne

Zadanie 100. Przy przewożeniu skrzyni zawierającej 21 detali standardowych i 10

niestandardowych, zgubiono jeden z nich, nie wiadomo który. Ze skrzyni po przewiezieniu
wyciągnięto losowo jeden detal standardowy. Znaleźć prawdopobieństwo tego, że zgubiono
detal standardowy, oraz tego że zgubiono detal niestandardowy.

Zadanie 101. W kolejce po bilety w cenie 10 zł ustawiło się n + m osób z których n

ma tylko dziesięciozłotówki, a m tylko dwudziestozłotówki (m ¬ n + 1). Wszyscy kupują
po jednym bilecie. Przed rozpoczęciem sprzedaży w kasie nie było pieniędzy. Jakie jest
prawdopodobieństwo, że nikt z kolejki nie będzie musiał czekać na resztę?

Zadanie 102. Obliczyć ile jest liczb całkowitych w zbiorze S = {1, 2, 3, . . . , 2000}, które

są podzielne przez 9, 11, 13 lub 15.

Zadanie 103. Wybieramy losowo liczbę ze zbioru T = {1000, 1001, . . . , 9999}. Znaleźć

prawdopobieństwo tego, że wśród cyfr wylosowanej liczby co najmniej raz występuje 0,
co najmniej raz 1 oraz co najmniej raz 2 (na przykład 1072 lub 2101).

Zadanie 104. Wśród 200 osób 150 uprawia pływanie lub jogging lub jedno i drugie.

Jeśli 85 osób uprawia pływanie a 60 pływanie i jogging to ile uprawia jogging?

Zadanie 105. Niech S = {100, 101, 102, . . . , 999}, a więc |S| = 900.

1. Ile jest liczb ze zbioru S ma co najmnie jedną cyfrę równą 3 lub 7?

2. Ile liczb ze zbioru S ma co najmniej jedną z cyfr równą 3 i co najmnie jedną z cyfr

równą 7?

Zadanie 106. Wybieramy losowo liczbę całkowitą ze zbioru {1, 2, 3, . . . , 1000}. Ile wy-

nosi prawdopodobieństwo, że jest ona podzielna przez 4, 5 lub 6?

Zadanie 107. Wybieramy losowo liczbe całkowitą ze zbioru {1, 2, 3, . . . , 1000}. Ile wy-

nosi prawdopodobieństwo, że liczba ta jest

1. podzielna przez 7

2. podzielna przez 11

3. niepodzielna przez 7 lub 11

4. podzielna przez 7 lub 11, a także przez obie te liczby

Zadanie 108. Ile jest sposobów rozmieszczenia pięciu kul w czterech pudełkach?
Zadanie 109. Na ile sposobów dziesięć identycznych czerwonych kulek można umieścić

w pięciu rozróżnialnych torbach?

Zadanie 110. Ile jest liczb ze zbioru {1, 2, 3, . . . , 1000} ma tę własność, że suma cyfr

wynosi 7?

Zadanie 111. Na ile sposobów można wybrać 10 monet mając nieograniczony zapas

jednogroszówek, pięciogroszówek, dziesięciogroszówek i pięćdziesięciogroszówek?

Zadanie 112. Pewien inwestor ma 7 przekazów gotówkowych po 1200 zł każdy, które

chce przesłać pocztą trzem fundacjom emerytalnym (powierniczym).

1. na ile sposobów może zainwestować swoje pieniądze?

2. na ile sposobów może zainwestować swoje pieniądze zakładając, że każdy fundusz

wymaga wpłaty co najmniej 1000 zł.

108

15.1. Zadania do rozdziałów.

Zadanie 113. Dwanaście identycznych listów ma zostać wrzuconych do czterech róż-

nych skrzynek pocztowych. Policz

1. na ile różnych sposobów można to zrobić?

2. na ile różnych sposobów można to zrobić, jeśli do każdej ze skrzynek muszą trafić

co najmniej dwa listy?

Zadanie 114. Ile można otrzymać różnych mieszanek po 10 cukierków, jeśli mamy do

dyspozycji cztery rodzaje cukierków w nieograniczonych ilościach?

Zadanie 115. Na ile sposobów można rozmieścić 14 przedmiotów w 3 pudełkach

1. tak by w jednym z pudełek znalazło się co najmniej 8 przedmiotów?

2. tak ,by w żadnym z pudełek nie znalazło się więcej niż 7 przedmiotów?

Zadanie 116. W związku z wzajemną jednoznacznością między ciągami złożonymi z

pięciu zer i trzech jedynek, a rozmieszczniem pięciu przedmiotów w czterech pudełkach

1. Znajdź rozmieszcznienia, które odpowiadają następującym ciągom:

10101000

01001001

10000011

11100000

2. Znajdź ciągi, które odpowiadają następującym rozmieszczeniom:

|0|0|0|00|

|00| |0|00|

|00000| | | | |

Zadanie 117. Podać model kombinatoryczny prowadzący do dowódu równości

n + 1

r − 1

1 ¬ r ¬ n

Zadanie 118. Dla dowolnych a, b ∈ R oraz n ∈ N mamy

(a + b)

r=0

n−r

Znajdź rozwinięcią następujących wyrażeń:

1. (x + 2y)

2. (x − y)

3. (3x + 1)

4. (x + 2)

109

ROZDZIAŁ 15. Zadania.

Rysunek 15.1: Grafy.

γ(e)

(x, w)

(w, x)

(x, x)

(w, z)

(w, y)

(w, z)

(z, y)

Tabela 15.1: Wartości funkcji γ.

Rysunek 15.2: Graf skierowany.

110

15.1. Zadania do rozdziałów.

15.1.5

Rozdziały 7–9.

Zadanie 119. Podaj tabelę funkcji p dla każdego z grafów z rysunku 15.1.

Zadanie 120. Zrób rysunek grafu skierowanego G, w którym zbiorem wierzchołków

jest V (G) = {w, x, y, z}, a zbiorem krawędzi E(G) = {a, b, c, d, e, f , g}, a funkcją γ
podaną w tabeli 15.1.

Zadanie 121. Które z podanych ciągów wierzchołków opisują drogi w grafie skierowa-

nym przedstawionym na rysunku 15.2.

1. zywvwt

2. vstx

3. xzyvs

Zadanie 122. Weźmy graf skierowany przedstawiony na rysunku 15.3. Opisz drogę

acykliczną

1. od x do y

2. od v do w

3. od z do v

Rysunek 15.3: Graf.

Zadanie 123. Podaj przykład grafu skierowanego o wierchołkach x, y, z w którym są

cykle jeden z wierzchołkami x i y a drugi z y i z, ale nie ma cyklu mającego wierzchołki
x i z.

Zadanie 124. Które z następujących ciągów wierzchołków odpowiadają drogom w gra-

fie z rysunku 15.4.

1. zxw

2. wwxz

3. zxwyywz

4. yyww

111

ROZDZIAŁ 15. Zadania.

Rysunek 15.4: Graf.

Podaj długość każdej drogi. Które z nich są drogami zamkniętymi? Wypisz krawędzie
wielokrotne, ile jest pętli w tym grafie?

Zadanie 125. Podaj relację sąsiedztwa A dla grafu z rysunku 15.4?
Zadanie 126. Dla grafu przedstawionego na rysunku 15.5 podaj przykład każdej z

następujących dróg. Sprawdź czy podałeś ciąg krawędzi i ciąg wierzchołków.

Rysunek 15.5: Graf.

1. droga długości 3 od y do w

2. droga długości 4 od v do y

Zadanie 127. Mamy daną macierz sąsiedztwa grafu skierowanego

























Jakie informacje o grafie zawarte są w tych macierzach sąsiedztwa?

Zadanie 128. Dla grafu przedstawionego na rysunku 15.6 podaj ciąg wierzchołków

najkrótszej drogi łączącej następujące pary wierzchołków i podaj jej długość.

112

15.1. Zadania do rozdziałów.

Rysunek 15.6: Graf.

1. s i v

2. u i y

Zadanie 129.

1. Zrób rysunek pięciu grafów regularnych o 4 wierzchołkach, z którch każdy ma stopień

równy dwa.

2. Zrób rysunek wszystkich grafów regularnych o pięciu wierzchołkach, z których każdy

ma stopień równy trzy.

Zadanie 130. Które pary grafów z rysunku 15.7 są izomorficzne? Uzasadnij odpowiedź

opisując izomorfizm lub wyjaśniając dlaczego nie istnieje.

Rysunek 15.7: Grafy.

Zadanie 131. Które z następujących ciągów są ciągami liczb wierzchołków kolejnych

stopni grafów? W każdym przypadku narysuj graf o danym ciągu liczb wierzchołków
kolejnych stopni tego grafu, albo wyjaśnij dlaczego taki graf nie istnieje.

113

ROZDZIAŁ 15. Zadania.

1. (1, 1, 0, 3, 1, 0, 0, . . .)

2. (0, 0, 1, 2, 1, 0, 0, . . .)

Zadanie 132. Zbadać spójność oraz podać liczbę składowych grafów z rysunku 15.8.

Rysunek 15.8: Grafy.

Zadanie 133. Który z grafów przedstawionych na rysunku 15.9 ma cykle Eulera?

Rysunek 15.9: Grafy.

Zadanie 134. Czy grafy przedstawione na rysunku 15.10 mają drogę Eulera?

Rysunek 15.10: Grafy.

Zadanie 135. Znaleźć wzór na s

= 1

= 2s

+ 3

R(n) = 3

= 2s

114

15.1. Zadania do rozdziałów.

= 0

= 2s

+ 5n

= 2

= 2s

+ 3 + 5n

= 2s

− 7

= 3

= 2s

− n

= 0

= 2s

+ 5 − 7n

Zadanie 136. Wyprowadzić wzór na s

dla R(n) = n

15.1.6

Rozdział 14.

Zadanie 137. Zmienna losowa X ma funkcję zadaną wzorem

1. g(s) =

1
4

(1 + s)

2. g(s) =

s(1−s

)

6(1−s)

3. g(s) =

2−s

Wyznaczyć rozkład zmiennej losowej oraz E(X) i D

(X).

Zadanie 138. Weźmy X

, X

niezależne zmienne losowe o rozkładzie Poissona z λ

,λ

0. Korzystając z funkcji tworzących znaleźć rozkład Y = X

+ X

Zadanie 139. Dana jest funkcja tworząca f (s) rozkładu zmiennej losowej X. Policzyć

funkcje tworzące rozkładów

1. Y = X + 1

2. Y = 2X

Zadanie 140. Dana jest funkcja tworząca f (s) rozkładu zmiennej losowej X. Policzyć

funkcje tworzące dla

1. P ({ε : X(ε) ¬ n})

2. P ({ε : X(ε)  n})

3. P ({ε : X(ε) < n})

4. P ({ε : X(ε) > n + 1})

5. P ({ε : X(ε) = 2n})

115

ROZDZIAŁ 15. Zadania.

15.2

Zestawy kolokwialne.

15.2.1

Zestaw 1.

Wersja I.

1. Udowodnić, że (x

+ x + 1) | ((x + 1)

2n+1

+ x

n+2

) dla n ∈ N.

2. Sprawdzić czy podane niżej warunki są niezmiennikami pętli

DOPÓKI 1=<m WYKONUJ
m:=2m
n:=3n

(a) n

 m

(b) 2m

< n

3. Niech Σ = {a, b, c} i niech A(n) będzie zbiorem słów w Σ

, w których występuje

parzysta liczba elementów a oraz niech s

oznacza liczbę słów w A(n)

(a) podaj wartość s

, s

(b) znajdź wzór rekurencyjny na s

, s

4. Znaleźć zbiór ogólny ciągu s

i s

mając dane

(a) s

= 5s

n−1

+ 7s

n−2

= 1

= 2

(b) s

= 2s

+ n

= 5

Wersja II.

1. Udowodnić, że n! <

n+1

dla n  2.

2. Sprawdzić czy podane niżej warunki są niezmiennikami pętli

DOPÓKI 1=<k WYKONUJ
k:=2k

(a) k

≡ 1( mod 3)

(b) k

≡

mod 4

3. Niech Σ = {0, 1} i niech A(n) będzie zbiorem ciągów w Σ

, w których dwie jedynki

nie stoją obok siebie oraz niech s

oznacza liczbę ciągów w A(n)

(a) podaj wartość s

, s

(b) znajdź wzór rekurencyjny na s

, s

4. Znaleźć wzór ogólny ciągu s

i s

mając dane

(a) s

= 4s

n−1

+ 2s

n−2

= 0

= 5

(b) s

= 2s

+ n

= 8

116

15.2. Zestawy kolokwialne.

Wersja III

1. Udowodnić, że (

)

¬ n! ¬ (

)

dla n  6.

2. Sprawdzić czy warunek

k
i=0

= 2

k+1

− 1 jest niezmiennikiem pętli

DOPÓKI k>=0 WYKONUJ
JEŚLI suma od 0 do k po 2^i = 2^(k+1)-1 TO k:=k+1

3. Wyznaczyć ciąg s

określony rekurencyjnie, oznaczający liczbę takich podziałów

podzbiorów zbioru {1, 2, . . . , n}, które nie zawierają dwóch kolejnych liczb

(a) podaj wartość s

, s

(b) oblicz s

, s

4. Znaleźć wzór ogólny ciągu s

i s

mając dane

(a) s

= 5s

n−1

+ 6s

n−2

= 5

= 8

(b) s

= 2s

+ An

+ Bn + Cs

= 2

A, B, C ∈ R

15.2.2

Zestaw 2.

Wersja I.

1. Spośród n osób należy wybrać r osób. Następnie z r osób należy wybrać k członków

zarządu. Pozostali utworzą komisję rewizyjną. Na ile sposobów można wybrać zarząd
i komisję rewizyjną? Czy liczba wyborów będzie taka sama, gdy najpierw wybierze
się k członków zarządu, a z pozostałych n − k osób wybierze się r − k członków
komisji rewizyjnej?

2. W urnie znajduje sie n białych i m czarnych kul m < n. Wyjmujemy kolejno bez

zwracania kule z urny. Niech M (k) i N (k) oznaczają odpowiednio liczbę kul czarnych
i białych wyjętych w pierwszych k losowaniach. Obliczyć prawdopodobieństwo, że
dla wszystkich k = 1, 2, . . . , n + m będzie

(a) M (k) < N (k)

(b) M (k) ¬ N (k)

3. Ile jest liczb całkowitych od 1 do 5000, które są podzielne przez 9, 11, 13 i 15.

4. Dany jest zbiór złożony z 10 liczb naturalnych dwucyfrowych w rozwinięciu dzie-

siętnym. Dowieść, że w tym zbiorze istnieją dwa niepuste podzbiory takie, że sumy
liczb obu podzbiorów są równe.

5. Dwanaście identycznych listów ma zostać wrzuconych do czterech różnych skrzynek

pocztowych.

(a) Na ile sposobów można to zrobić?

(b) Na ile sposobów można to zrobić, jeśli do każdej ze skrzynek muszą trafić

przynajmniej dwa listy?

117

ROZDZIAŁ 15. Zadania.

Wersja II.

1. Liczby 1, 2, . . . , n ustawiono przypadkowo, oblicz prawdopodobieństwo, że

(a) liczby 1 i 2

(b) liczby 1, 2 i 3

występują w sąsiedztwie i w wyżej wymienionej kolejności.

2. W urnie znajduje się n białych i m czarnych kul m < n. Wyjmujemy kolejno bez

(a) M (k) < N (k)

(b) M (k) ¬ N (k)

3. Ile jest liczb całkowitych od 1 do 3000, które są podzielne przez 9, 11, 13 i 15?

4. Dany jest zbiór złożony z 10 liczb naturalnych dwucyfrowych w rozwinięciu dzie-

siętnym. Dowieść, że w tym zbiorze istnieją dwa niepuste podzbiory takie, że sumy
liczb obu podzbiorów są równe.

5. Siedemnaście identycznych kul ma być włożonych do pięciu różnych szuflad

(a) Na ile sposobów można to zrobić?

(b) Na ile sposobów można to zrobić, jeśli do każdej szuflady muszą trafić co naj-

mniej dwie kule?

Wersja III.

1. Z n par obuwia wybrano losowo 2r butów (2r < n). Obliczyć prawdopodobieństwo,

że wśród wybranych butów

(a) nie ma ani jednej pary.

(b) są dokładnie dwie pary.

2. Na każdym przystanku k = 1, 2, . . . , n + m stoi jedna osoba. Na wszystkich przy-

stankach jest n + m osób w tym n chłopców i m dziewcząt gdzie m < n. W trakcie
trwania kursu nikt nie wychodzi z autobusu. Oblicz prawdopodobieństwo, że

(a) w autobusie po przejechaniu k-tego przystanku k = 1, 2, . . . , n + m będzie

mniej dziewcząt niż chłopców dla każdego k?

(b) w autobusie będzie nie więcej dziewcząt niż chłopców dla każdego k.

3. Ile jest liczb całkowitych od 1 do 7000, które są podzielne przez 9, 11, 13 i 15?

4. Na płaszczyźnie danych jest pięć punktów kratowych (są to punkty o wspołrzędnych

całkowitych). Wykazać, że środek jednego z odcinków łączących te punkty jest też
punktem kratowym.

5. Na ile sposobów można rozmieścić 14 przedmiotów w 3 pudełkach, tak aby

(a) w jednym z pudełek znalazłoby się co najmniej 8 przedmiotów?

(b) w żadnym z pudełek nie znalazłoby się więcej niż 7 przedmiotów?

118

15.2. Zestawy kolokwialne.

Wersja IV.

1. Z n par obuwia wybrano losowo 2r butów (2r < n). Obliczyć prawdopodobieństwo,

że wśród wybranych butów

(a) jest dokładnie jedna para?

(b) są dokładnie trzy pary?

2. Na każdym przystanku k = 1, 2, . . . , n + m stoi jedna osoba. Na wszystkich przy-

stankach jest n + m osób w tym n chłopców i m dziewcząt gdzie m < n. W trakcie
trwania kursu nikt nie wychodzi z autobusu. Oblicz prawdopodobieństwo, że

(a) w autobusie po przejechaniu k-tego przystanku k = 1, 2, . . . , n + m będzie

mniej dziewcząt niż chłopców dla każdego k?

(b) w autobusie będzie nie więcej dziewcząt niż chłopców dla każdego k.

3. Ile jest liczb całkowitych od 1 do 4000, które są podzielne przez 9, 11, 13 i 15?

4. Wykazać, że w trójkącie równobocznym o boku 4 nie można umieścić 17 punktów,

tak by odległość dwóch z nich była większa od jedynki.

5. Dwanaście identycznych listów ma zostać wrzuconych do czterech różnych skrzynek

pocztowych.

(a) na ile sposobów można to zrobić?

(b) na ile sposobów można to zrobić, jeśli do każdej ze skrzynek muszą trafić co

najmniej dwa listy?

15.2.3

Zestaw 3.

Wersja I.

1. Niech Σ = {0, 1} i niech A(n) będzie zbiorem ciągów w Σ

, w których dwie jedynki

nie stoją obok siebie oraz niech s

oznacza liczbę ciągów w A(n)

(a) podaj wartość s

, s

(b) znajdź wzór rekurencyjny na s

, s

2. Sprawdzić czy podane warunki są niezmiennikami pętli

DOPÓKI j>=n WYKONUJ
i:=i+2
j:=j+2

(a) i < j

dla n = 1

(b) i ¬ j

dla n = 0

3. Dwanaście identycznych książek – nowości wydawniczych ma trafić do 4 różnych

bibliotek w pewnym mieście. Na ile sposobów można to zrobić? Jak zmieni się licz-
ba tych sposobów przydzialania, gdy każda biblioteka wymaga co najmniej dwóch
książek?

119

ROZDZIAŁ 15. Zadania.

4. Niech A będzie pewnym ustalonym dziesięcioelementowym podzbiorem zbioru {1,

2, . . ., 50}. Pokazać, że zbiór A ma dwa różne pięcioelementowe podzbiory takie, że
sumy wszystkich elementów każdego z nich są równe.

5. Jeśli dwaj kandydaci P i Q otrzymali w wyborach p i q głosów, p > q. Jaka jest

szansa na to, że przy zliczaniu głosów kandydat P będzie cały czas wyprzedzał bądź
dorównywał pod względem liczby głosów kandydatowi Q?

Wersja II.

1. Niech Σ = {a, b, c} i niech A(n) będzie zbiorem słów w Σ

, w których występuje

parzysta liczba elementów a oraz niech s

oznacza liczbę słów w A(n)

(a) podaj wartość s

, s

(b) znajdź wzór rekurencyjny na s

, s

2. Sprawdzić czy podane warunki są niezmiennikami pętli

DOPÓKI j>=n WYKONUJ
i:=i+2
j:=j+2

(a) i < j

dla n = 1

(b) i ¬ j

dla n = 0

3. Piętnaście identycznych kul ma trafić do trzech różnych szuflad. Na ile sposobów

można to zrobić? Jak zmieni się liczba tych sposobów przydzielania, gdy do każdej
szuflady muszą trafić co najmniej trzy kule?

4. Nich A będzie pewnym ustalonym 25-elementowym podzbiorem zbioru {1 , 2 , . . .,

150}. Pokazać, że zbiór A ma dwa różne dwuelementowe podzbiory takie, że sumy
wszystkich elementów każdego z nich są równe.

5. Jeśli dwaj kandydaci P i Q otrzymali w wyborach p + 1 i q głosów, p > q. Jaka

jest szansa na to, że przy zliczaniu głosów kandydat P będzie cały czas wyprzedzał
bądź dorównywał pod względem liczby głosów kandydatowi Q?

120

Spis literatury

[1] Ross K. A., Wright R.B., Matematyka dyskretna, PWN, Warszawa 2000.

[2] Graham R. L., Knuth D., Patashnik O., Matematyka konkretna, PWN, Warszawa

2001.

[3] Weron A., Weron R., Inżynieria finansowa, WNT, Warszawa 2001.

[4] Jeśmianowicz L., Łoś J., Zbiór zadań z algebry, PWN, Warszawa 1976.

[5] Lipski W., Marek W., Analiza kombinatoryczna, PWN, Warszawa 1986.

[6] Feller W., Wstęp do rachunku prawdopodobieństwa, PWN, Warszawa 1981.

[7] Stojanow J., Zbiór zadań z rachunku prawdopodobieństwa, PWN, Warszawa 1982.

[8] Deo N., Teoria grafów i jej zastosowania w technice i informatyce, PWN, Warszawa

1980.

[9] Plucińska A., Pluciński E., Zadania z rachunku prawdopodobieństwa i statystyki ma-

tematycznej : dla studentów politechnik, PWN, Warszawa 1976.

[10] Browkin J., Zadania z olimpiad matematycznych V-VI, WSiP, Warszawa 1983.

[11] Bryński M., Olimipiady matematyczne VII, WSiP, Warszawa 1995

[12] Chełmiński K., Pompe W., Zasada szufladkowa Dirichleta, Delta, nr 12, 1994.

[13] Chrząstowski P., Liczby Fibonacciego, Delta, nr 2, 1992.

[14] Łukasiewicz G., Szafrański N., O metodzie okrężnej, Delta, nr 5, 1989.

[15] Mąkowski A., Iwaniec T., Zasada szufladkowa Dirichleta. Geometria okręgów i sfer,

WSiP, Warszawa 1980.

[16] Rutkowski J., O pewnym hokus-pokus w kombinatoryce, Delta, nr 2, 1988.

[17] Ryll J., Ciągi rekurencyjne a szeregi potęgowe, Delta, nr 5, 1985.

[18] Starczyk-Podhalicz D., Marczak M., Modelowanie matematyczne w nauczaniu ma-

tematyki na poziomie szkoły średniej, Politechnika Radomska, Prace naukowo-
pedagogiczne, nr 4, 1998.

[19] Strasiewicz S., Zadania z olimpiad matematycznych tom I-IV, PZWS, Warszawa

1956, 1961, 1967, 1972.

121

SPIS LITERATURY

[20] Traczyk T., Modele matematyczne i jak z nich korzystać, Delta, nr 7, 1978.

[21] Pawłowski H., Zadania z olimpiad matemayczynych z całego świata, Oficyna Wy-

dawnicza TUTOR, Toruń 1997.

[22] Żołądek M., Zasada szufladkowa Dirichleta w mechanice, Delta, nr 3, 1998.

[23] Makarec A., Wybrane metody modelowania matematycznego w problemach zadanio-

wych matematyki szkoły średniej, praca magisterska, promotor Marczak M., Uniwer-
sytet w Białymstoku, Białystok 2000.

[24] Ryba A., Marczak M., Wpływ wykorzystania technologii informacyjnej i metod mo-

delowania w rozwiązywaniu problemów na aktywność i motywację do nauki uczniów,
Rocznik Edukacji Alternatywnej, Łódź 2001.

122

Wyszukiwarka

Podobne podstrony:
J Jaworski Z Palka J Szymański Matematyka dyskretna dla informatyków
Matematyka Dyskretna dla informatyków Wojciech Kordecki
Elementy matematyki finansowej 2014
Hordi wzór zaliczenia, Matematyka dla ambitnych, matematyka dyskretna
4 ELEMENTY MATEMATYKI FINANSOWEJ
Hordi Ćw1, Matematyka dla ambitnych, matematyka dyskretna
Elementy matematyki finansowej, Różne Dokumenty, MARKETING EKONOMIA ZARZĄDZANIE
rozwiązania zadań, studia AGH, ZiIP, Magister, Elementy Matematyki Finansowej
Hordi Ćw2, Matematyka dla ambitnych, matematyka dyskretna
Elementy matematyki finansowej dodatkowe zadania
Program zajęć terapii pedagogicznej z elementami?ukacji matematycznej dla uczniów w młodszym wieku s
Elementy matematyki finansowej 2014
matematyka dyskretna w 2 id 283 Nieznany
Denisjuk A Matematyka Dyskretna
ANOVA hierarch odp folia Word2003, Elementy matematyki wyższej

więcej podobnych podstron