aaaaCzęsto usiłujemy ukryć nasze uczucia przed tymi, którzy powinni je poznać.aaaa [ Pobierz całość w formacie PDF ]
Matematyka dyskretna
dla informatyk
ó
w
Czƒ–¢ I: Elementy kombinatoryki
Jerzy Jaworski
Zbigniew Palka
Jerzy Szyma«ski
Uniwersytet im. Adama Mickiewicza
Pozna« 2007
Zale»no±ci rekurencyjne
4
Wiele zale»no–ci kombinatorycznych mo»na wyrazi¢ prosto w postaci r
ó
wna« rekurencyjnych.
Typowym przypadkiem jest, gdy rozwi¡zanie danego problemu mo»emy sprowadzi¢ do rozwi¡za«
mniejszych
problem
ó
w tego samego typu.
4.1. Proste zale»no–ci rekurencyjne
Przyk“ad 4.1. Wyznaczy¢ przy pomocy zale»no–ci rekurencyjnej liczbƒ wszystkich permutacji
zbioru
f
1
;
2
;:::;ng
.
Przyk“ad 4.2. Na ile sp
ó
jnych obszar
ó
w dzieli p“aszczyznƒ
n
prostych, z kt
ó
rych »adne dwie nie
s¡ r
ó
wnoleg“e i »adne trzy nie przecinaj¡ siƒ w jednym punkcie?
4.2. Jednorodne zale»no–ci rekurencyjne
Zajmiemy siƒ teraz rozwi¡zywaniem tak zwanych jednorodnych (liniowych) r
ó
wna« rekurencyj-
nych. S¡ one postaci
a
n
=
c
1
a
n¡
1
+
c
2
a
n¡
2
+
:::
+
c
r
a
n¡r
;
(4.1)
gdzie
c
i
,
i
=1
;
2
;:::;r
, s¡ zadanymi sta“ymi (niezale»nymi od
n
) i
c
r
6
=0. Powy»sza zale»no–¢ ma
g“ƒboko–¢
r
wiƒc, jak za chwilƒ poka»emy, aby j¡ rozwi¡za¢ musimy mie¢ zadanych
r
warunk
ó
w
pocz¡tkowych. Zauwa»my, »e to r
ó
wnanie ma zawsze rozwi¡zanie trywialne
a
n
=0, dla ka»dego
n2
N. Ci¡g
a
n
spe“niaj¡cy (4.1), taki »e
a
k
6
=0dla pewnego
k2
N, nazywamy rozwi¡zaniem
nietrywialnym.
Przyk“ad 4.3. Udowodni¢, »e je»eli ci¡gi
a
0
n
i
a
00
n
spe“niaj¡ r
ó
wnanie rekurencyjne (4.1), a
c
jest
dowoln¡ sta“¡, to ci¡gi
a
0
n
+
a
00
n
oraz
ca
0
n
spe“niaj¡ tak»e to r
ó
wnanie.
Bezpo–redni¡ konsekwencj¡ powy»szego przyk“adu jest fakt, i» kombinacja liniowa dw
ó
ch (sko«-
czonej liczby) rozwi¡za« jednorodnego liniowego r
ó
wnania rekurencyjnego jest r
ó
wnie» rozwi¡-
zaniem tego r
ó
wnania.
Z ka»dym jednorodnym r
ó
wnaniem rekurencyjnym (4.1) zwi¡zane jest r
ó
wnanie algebraiczne
x
r
¡c
1
x
r¡
1
¡c
2
x
r¡
2
¡:::¡c
r
=0
;
(4.2)
zwane jego r
ó
wnaniem charakterystycznym. R
ó
wnanie (4.2) mo»emy otrzyma¢ z (4.1) poprzez
zamianƒ
a
k
na
x
k
, a nastƒpnie podzielenie przez najmniejsz¡ potƒgƒ
x
. Jak zobaczymy w dalszej
czƒ–ci, rozwi¡zanie og
ó
lne zale»no–ci (4.1) zale»y od pierwiastk
ó
w r
ó
wnania charakterystycz-
nego (4.2) w zbiorze liczb zespolonych C.
Przyk“ad 4.4. Udowodni¢, »e ci¡g
a
n
=
®
n
jest nietrywialnym rozwi¡zaniem r
ó
wnania rekuren-
cyjnego (4.1) wtedy i tylko wtedy, gdy
®
jest pierwiastkiem r
ó
wnania charakterystycznego (4.2).
20
4. Zale»no–ci rekurencyjne
Przyk“ad 4.5. Udowodni¢, »e je»eli
®
jest
k
-krotnym pierwiastkiem r
ó
wnania charakterystycz-
nego (4.2), to ci¡g
a
n
=
n
i
®
n
jest nietrywialnym rozwi¡zaniem r
ó
wnania rekurencyjnego (4.1),
dla
i
=0
;
1
;:::k¡
1.
W szczeg
ó
lnym przypadku, gdy zale»no–¢ rekurencyjna (4.1) ma
g“ƒboko–¢
dwa, to r
ó
wnanie
charakterystyczne jest r
ó
wnaniem kwadratowym, zatem mo»emy sformu“owa¢ nastƒpuj¡cy fakt.
Lemat 4.1. Je»eli
®
i
¯
s¡ r
ó
»nymi (nie koniecznie rzeczywistymi) pierwiastkami r
ó
wnania
charakterystycznego
x
2
=
Ax
+
B;
to r
ó
wnanie rekurencyjne
a
n
=
Aa
n¡
1
+
Ba
n¡
2
ma rozwi¡zanie og
ó
lne postaci
a
n
=
C
1
®
n
+
C
2
¯
n
:
(4.3)
W przypadku, gdy
®
=
¯
, to rozwi¡zanie og
ó
lne ma posta¢
a
n
=(
C
1
+
C
2
n
)
®
n
:
(4.4)
Sta“e
C
1
oraz
C
2
wystƒpuj¡ce powy»ej zale»¡ od warunk
ó
w pocz¡tkowych na“o»onych na r
ó
wnanie
rekurencyjne.
Zauwa»my, »e w powy»szym przypadku potrzebne s¡ nam dwa warunki pocz¡tkowe, kt
ó
re
dadz¡ uk“ad dw
ó
ch r
ó
wna« z dwiema niewiadomymi
C
1
i
C
2
.
Przyk“ad 4.6. Bƒdziemy m
ó
wili, »e rozwi¡zuj¡cy pewien problem student jest na
n
-tym etapie
je»eli do rozwi¡zania problemu pozosta“o mu
n
(
n
>1) krok
ó
w. Na ka»dym etapie ma on piƒ¢
mo»liwo–ci. Dwie z nich prowadz¡ go z
n
-tego etapu do(
n¡
1)-go etapu, a pozosta“e trzy prowadz¡
go bezpo–rednio do(
n¡
2)-go etapu. Niech
a
n
oznacza liczbƒ sposob
ó
w rozwi¡zania problemu
zaczynaj¡c od
n
-tego etapu. Przyjmuj¡c, »e
a
1
=5oraz
a
2
=13wyznaczy¢ wz
ó
r na
a
n
.
Przyk“ad 4.7. Rozwi¡za¢ r
ó
wnanie rekurencyjne
a
n
=
¡
6
a
n¡
1
¡
9
a
n¡
2
;
z warunkami pocz¡tkowymi
a
0
=1,
a
1
=
¡
9.
Przyk“ad 4.8. Ile jest r
ó
»nych sposob
ó
w wej–cia po schodach zbudowanych z
n
stopni, je–li w
ka»dym kroku mo»na pokona¢ jeden lub dwa stopnie?
a
n
=
a
n¡
1
+
a
n¡
2
;n
>2
; a
0
=1i
a
1
=1
:
(4.5)
Zale»no–¢ rekurencyjna (4.5) nazywa siƒ r
ó
wnaniem Fibonacciego a ci¡g liczb 1, 1, 2,3, 5, 8, 13,21,...
nosi nazwƒ ci¡gu Fibonacciego .
Przyk“ad 4.10. Wyznaczy¢ liczby Lucasa
L
n
okre–lone wzorem
L
n
=
F
n
+1
+
F
n¡
1
;
gdzie
F
k
oznacza liczbƒ Fibonacciego z dodatkowym za“o»eniem
F
0
=0.
Przyk“ad 4.11. Niech
b
n
oznacza liczbƒ
n
-elementowych ci¡g
ó
w o elementach ze zbioru
f
0
;
1
;
2
g
takich, »e »adne dwie po sobie nastƒpuj¡ce jedynki ani »adne dwie po sobie nastƒpuj¡ce dw
ó
jki
nie s¡ dozwolone. Wyznaczy¢ wz
ó
r na
b
n
.
Lemat 4.1 jest szczeg
ó
lnym przypadkiem nastƒpuj¡cego twierdzenia.
4.3. Niejednorodne liniowe zale»no–ci rekurencyjne
21
Twierdzenie 4.2. Je»eli
®
1
;®
2
;:::;®
r
s¡ r
ó
»nymi (nie koniecznie rzeczywistymi) pierwiastkami
r
ó
wnania charakterystycznego
x
r
¡c
1
x
r¡
1
¡c
2
x
r¡
2
¡:::¡c
r
=0
;
to r
ó
wnanie rekurencyjne
a
n
=
c
1
a
n¡
1
+
c
2
a
n¡
2
+
:::
+
c
r
a
n¡r
;
ma rozwi¡zanie postaci
a
n
=
C
1
®
n
1
+
C
2
®
n
2
+
:::
+
C
r
®
n
r
:
Og
ó
lnie, je»eli
x
r
¡c
1
x
r¡
1
¡c
2
x
r¡
2
¡:::¡c
r
=(
x¡®
1
)
m
1
(
x¡®
2
)
m
2
¢:::¢
(
x¡®
k
)
m
k
;
gdzie
m
i
>1,
i
=1
;
2
;:::;k
oraz
m
1
+
m
2
+
:::
+
m
k
=
r
(tzn.
®
i
jest
m
i
-krotnym pierwiastkiem
r
ó
wnania charakterystycznego), to
a
n
=
¡
C
1
+
C
2
n
+
:::
+
C
m
1
n
m
1
¡
1
¢
®
n
1
+
¡
D
1
+
D
2
n
+
:::
+
D
m
2
n
m
2
¡
1
¢
®
n
2
.
+
¡
Z
1
+
Z
2
n
+
:::
+
Z
m
k
n
m
k
¡
1
¢
®
n
k
:
Sta“e wystƒpuj¡ce powy»ej zale»¡ od warunk
ó
w pocz¡tkowych na“o»onych na r
ó
wnanie rekuren-
cyjne.
Przyk“ad 4.12. Przypu–¢my, »e pewien prymitywny organizm osi¡ga dojrza“o–¢ po dw
ó
ch go-
dzinach i ma wtedy pierwszych czterech potomk
ó
w a nastƒpnie ju» co godzinƒ ma sze–ciu kolej-
nych potomk
ó
w. Zak“adaj¡c, »e wszystkie urodzone organizmy zachowuj¡ siƒ tak samo oraz, »e
rozpoczynali–my z jednym nowourodzonym organizmem, znale„¢ zale»no–¢ rekurencyjn¡ dla
a
n
liczby organizm
ó
w po
n
godzinach.
Przyk“ad 4.13. Rozwi¡» r
ó
wnanie rekurencyjne
a
n
=2
a
n¡
1
+15
a
n¡
2
+4
a
n¡
3
¡
20
a
n¡
4
;
z warunkami pocz¡tkowymi
a
0
=6
; a
1
=3
; a
2
=71
; a
3
=203
:
4.3. Niejednorodne liniowe zale»no–ci rekurencyjne
Niejednorodnym liniowym r
ó
wnaniem rekurencyjnym nazywamy r
ó
wnanie postaci
a
n
=
c
1
a
n¡
1
+
c
2
a
n¡
2
+
¢¢¢
+
c
r
a
n¡r
+
f
(
n
)
:
(4.6)
Funkcjƒ
f
(
n
)wystƒpuj¡c¡ w tym r
ó
wnaniu nazywamy wyrazem wolnym. Rozwi¡zanie og
ó
lne tej
zale»no–ci jest postaci
a
n
=
a
(1)
n
+
a
(2)
n
;
n
jest rozwi¡zaniem og
ó
lnym r
ó
wnania jednorodnego
n
=
c
1
a
(1)
n¡
1
+
c
2
a
(1)
n¡
2
+
¢¢¢
+
c
r
a
(1)
n¡r
;
(4.7)
kt
ó
re wyznaczamy zgodnie z zasadami poznanymi w poprzednim paragra
e.
gdzie
a
(1)
a
(1)
22
4. Zale»no–ci rekurencyjne
n
jest dowolnym szczeg
ó
lnym rozwi¡zaniem r
ó
wnania niejednorodnego (4.6).
Niestety, nie ma og
ó
lnej metody znajdowania tego rozwi¡zania szczeg
ó
lnego. W dalszej czƒ–ci
tego paragrafu, bƒdziemy wykorzystywa¢ metodƒ przewidywania rozwi¡zania. Polega ona na tym,
»e w zale»no–ci od postaci wyrazu wolnego, mo»emy odgadn¡¢ posta¢ rozwi¡zania. Najwa»niejsze
przypadki, to
Natomiast
a
(2)
1
±
Je»eli wyraz wolny
f
(
n
)jest wielomianem (zmiennej
n
) stopnia
d
oraz rozwi¡zanie og
ó
lne
r
ó
wnania jednorodnego
a
(2)
a
(2)
n
=
C
d
n
d
+
C
d¡
1
n
d¡
1
+
¢¢¢
+
C
0
:
2
±
Je»eli
f
(
n
)jest wielomianem (zmiennej
n
) stopnia
d
oraz
a
(2)
n
jest wielomianem stopnia
k
,
to przewidujemy rozwi¡zanie szczeg
ó
lne postaci
n
=
n
k
+1
(
C
d
n
d
+
C
d¡
1
n
d¡
1
+
¢¢¢
+
C
0
)
:
3
±
Je»eli
f
(
n
)jest funkcj¡ wyk“adnicz¡ postaci
f
(
n
)=
C¯
n
i
¯
nie jest pierwiastkiem r
ó
w-
nania charakterystycznego, to przewidywane rozwi¡zanie szczeg
ó
lne jest r
ó
wnie» funkcj¡
wyk“adnicz¡ postaci
a
(2)
n
=
A¯
n
.
4
±
Je»eli
f
(
n
)jest funkcj¡ wyk“adnicz¡ postaci
f
(
n
)=
C¯
n
i
¯
jest pierwiastkiem r
ó
wnania
charakterystycznego o krotno–ci
k
, to przewidywane rozwi¡zanie szczeg
ó
lne jest r
ó
wnie»
funkcj¡ wyk“adnicz¡ postaci
a
(2)
n
=
An
k
¯
n
.
5
±
Je»eli natomiast wyraz wolny
f
(
n
)jest sum¡ pewnych funkcji (zmiennej
n
), to przewi-
dywane rozwi¡zanie szczeg
ó
lne jest sum¡ przewidywanych rozwi¡za« dla poszczeg
ó
lnych
sk“adnik
ó
w.
Zwr
ó
¢my uwagƒ, »e sta“¡ mo»emy interpretowa¢ jako wielomian stopnia zero lub jako funkcjƒ
wyk“adnicz¡ o podstawie1.
Przyk“ad 4.16. Rozwi¡za¢ r
ó
wnanie rekurencyjne
a
n
=7
a
n¡
1
¡
10
a
n¡
2
+3
n
z warunkami pocz¡tkowymi
a
0
=0i
a
1
=1.
Przyk“ad 4.17. Znale„¢ rozwi¡zanie og
ó
lne r
ó
wnania rekurencyjnego
a
n
=3
a
n¡
1
¡
2
a
n¡
2
+2
n
:
Przyk“ad 4.18. Znale„¢ rozwi¡zanie og
ó
lne r
ó
wnania rekurencyjnego
a
n
=2
a
n¡
1
+7
n
2
:
Przyk“ad 4.19. Korzystaj¡c z faktu, »e liczba podzia“
ó
w zbioru
f
1
;
2
;:::;ng
na dwa niepuste
zbiory r
ó
wna jest2
n¡
1
¡
1(patrz Przyk“ad ??) pokaza¢, »e
a
n
okre–laj¡ce liczbƒ podzia“
ó
w zbioru
f
1
;
2
;:::;ng
na trzy niepuste zbiory, spe“nia dla
n
>1zale»no–¢
a
n
=
1
6
3
n
¡
1
2
2
n
+
1
2
:
Na zako«czenie tego paragrafu zwr
ó
¢my uwagƒ, »e r
ó
wnania tu prezentowane mo»na r
ó
w-
nie» rozwi¡za¢ innymi metodami, np. wykorzystuj¡c aparat funkcji tworz¡cych (patrz nastƒpny
rozdzia“).
n
nie jest wielomianem, to istnieje rozwi¡zanie szczeg
ó
lne, kt
ó
re
jest r
ó
wnie» wielomianem stopnia
d
, czyli zak“adamy, »e
a
(2)
 [ Pobierz całość w formacie PDF ]