Rozwiązywanie rekurencji za pomocą funkcji tworzących
MATEMATYKA DYSKRETNA ——- MATERIAŁY DO WYKLADU
Funkcje tworzące
ALEKSANDRA ORPEL
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
MATEMATYKA DYSKRETNA ——- MATERIAŁY DO WYKLADU
Funkcje tworzące
ALEKSANDRA ORPEL
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
DEFINICJA
Niech dany będzie ciąg liczbowy a
0
, a
1
, ..., a
n,...
. Funkcję
A(z) =
∞
X
k=0
a
k
z
k
nazywamy funkcją tworzącą ciągu {a
n
}
n∈N
.
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
Ciąg {a
n
}
n∈N
Funkcja tworząca
∞
P
n=0
a
n
z
n
1, 1, ..., 1, ...
1
1−z
=
P
n0
z
n
0, 1, 2, 3, 4, ..., n, ...
z
(1−z)
2
=
P
n1
nz
n
0, ..., 0, 1, M + 1, ...,
n
M
, ...
z
M
(1−z)
M+1
=
P
nM
n
M
z
n
1, M,
M
2
, ...,
M
N
!
, ..., M, 1
(1 + z)
M
=
P
n0
M
n
z
n
1, M + 1,
M+2
2
,
M+3
3
, ...
1
(1−z)
M+1
=
P
n0
n+M
n
z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
1, c, c
2
, ..., c
n
, ...
1
1−cz
=
P
n0
c
n
z
n
1, 1,
1
2!
, ...,
1
n!
, ...
e
z
=
P
N0
z
N
N!
0, 1,
1
2
, ...,
1
n
, ...
ln
1
1−z
=
P
n1
z
N
n
0, 1, 1 +
1
2
, 1 +
1
2
+
1
3
, ..., H
n
, ...
1
1−z
ln
1
1−z
=
P
n1
H
n
z
n
0, 0, 1, 3
1
2
+
1
3
, 4
1
2
+
1
3
+
1
4
, ...
z
(1−z)
2
ln
1
1−z
=
P
n0
n(H
n
− 1)z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
1, c, c
2
, ..., c
n
, ...
1
1−cz
=
P
n0
c
n
z
n
1, 1,
1
2!
, ...,
1
n!
, ...
e
z
=
P
N0
z
N
N!
0, 1,
1
2
, ...,
1
n
, ...
ln
1
1−z
=
P
n1
z
N
n
0, 1, 1 +
1
2
, 1 +
1
2
+
1
3
, ..., H
n
, ...
1
1−z
ln
1
1−z
=
P
n1
H
n
z
n
0, 0, 1, 3
1
2
+
1
3
, 4
1
2
+
1
3
+
1
4
, ...
z
(1−z)
2
ln
1
1−z
=
P
n0
n(H
n
− 1)z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
1, c, c
2
, ..., c
n
, ...
1
1−cz
=
P
n0
c
n
z
n
1, 1,
1
2!
, ...,
1
n!
, ...
e
z
=
P
N0
z
N
N!
0, 1,
1
2
, ...,
1
n
, ...
ln
1
1−z
=
P
n1
z
N
n
0, 1, 1 +
1
2
, 1 +
1
2
+
1
3
, ..., H
n
, ...
1
1−z
ln
1
1−z
=
P
n1
H
n
z
n
0, 0, 1, 3
1
2
+
1
3
, 4
1
2
+
1
3
+
1
4
, ...
z
(1−z)
2
ln
1
1−z
=
P
n0
n(H
n
− 1)z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
1, c, c
2
, ..., c
n
, ...
1
1−cz
=
P
n0
c
n
z
n
1, 1,
1
2!
, ...,
1
n!
, ...
e
z
=
P
N0
z
N
N!
0, 1,
1
2
, ...,
1
n
, ...
ln
1
1−z
=
P
n1
z
N
n
0, 1, 1 +
1
2
, 1 +
1
2
+
1
3
, ..., H
n
, ...
1
1−z
ln
1
1−z
=
P
n1
H
n
z
n
0, 0, 1, 3
1
2
+
1
3
, 4
1
2
+
1
3
+
1
4
, ...
z
(1−z)
2
ln
1
1−z
=
P
n0
n(H
n
− 1)z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Przykłady
1, c, c
2
, ..., c
n
, ...
1
1−cz
=
P
n0
c
n
z
n
1, 1,
1
2!
, ...,
1
n!
, ...
e
z
=
P
N0
z
N
N!
0, 1,
1
2
, ...,
1
n
, ...
ln
1
1−z
=
P
n1
z
N
n
0, 1, 1 +
1
2
, 1 +
1
2
+
1
3
, ..., H
n
, ...
1
1−z
ln
1
1−z
=
P
n1
H
n
z
n
0, 0, 1, 3
1
2
+
1
3
, 4
1
2
+
1
3
+
1
4
, ...
z
(1−z)
2
ln
1
1−z
=
P
n0
n(H
n
− 1)z
n
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
Niech dane będą dwa ciągi {a
n
}
n∈N
oraz {b
n
}
n∈N
reprezentowane
przez, odpowiednio, A(z) =
P
n0
a
n
z
n
oraz B(z) =
P
n0
b
n
z
n
.
Następujące operacje generują funkcje tworzorzące reprezentujące
poniższe ciągi
W1
sumowanie:
A(z) + B(z) =
X
n0
(a
n
+ b
n
) z
n
jest funkcją tworzącą dla ciągu
a
0
+ b
0
, a
1
+ b
1
, ..., a
n
+ b
n
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
Niech dane będą dwa ciągi {a
n
}
n∈N
oraz {b
n
}
n∈N
reprezentowane
przez, odpowiednio, A(z) =
P
n0
a
n
z
n
oraz B(z) =
P
n0
b
n
z
n
.
Następujące operacje generują funkcje tworzorzące reprezentujące
poniższe ciągi
W1
sumowanie:
A(z) + B(z) =
X
n0
(a
n
+ b
n
) z
n
jest funkcją tworzącą dla ciągu
a
0
+ b
0
, a
1
+ b
1
, ..., a
n
+ b
n
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W2
przesunięcie w prawo:
zA(z) =
X
n1
a
n−1
z
n
jest funkcją tworzącą dla ciągu
0, a
0
, a
1
, ..., a
n−1
, ...
W3
przesunięcie w lewo:
A(z) − a
0
z
=
X
n0
a
n+1
z
n
jest funkcją tworzącą dla ciągu
a
1
, a
2
, ..., a
n+1
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W2
przesunięcie w prawo:
zA(z) =
X
n1
a
n−1
z
n
jest funkcją tworzącą dla ciągu
0, a
0
, a
1
, ..., a
n−1
, ...
W3
przesunięcie w lewo:
A(z) − a
0
z
=
X
n0
a
n+1
z
n
jest funkcją tworzącą dla ciągu
a
1
, a
2
, ..., a
n+1
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W4
mnożenie przez indeks (różniczkowanie):
A
0
(z) =
X
n0
(n + 1)a
n+1
z
n
jest funkcją tworzącą dla ciągu
a
1
, 2a
2
, ..., (n + 1)a
n+1
, ...
W5
dzielenie przez indeks (całkowanie):
z
Z
0
A(t)dt =
X
n1
a
n−1
n
z
n
jest funkcją tworzącą dla ciągu
0, a
0
,
a
1
2
, ...,
a
n−1
n
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W4
mnożenie przez indeks (różniczkowanie):
A
0
(z) =
X
n0
(n + 1)a
n+1
z
n
jest funkcją tworzącą dla ciągu
a
1
, 2a
2
, ..., (n + 1)a
n+1
, ...
W5
dzielenie przez indeks (całkowanie):
z
Z
0
A(t)dt =
X
n1
a
n−1
n
z
n
jest funkcją tworzącą dla ciągu
0, a
0
,
a
1
2
, ...,
a
n−1
n
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W6
skalowanie:
A(λz) =
X
n0
λ
n
a
n
z
n
jest funkcją tworzącą dla ciągu
a
0
, λa
1
, λ
2
a
2
, ..., λ
n
a
n
, ...
W7
różnica:
(1 − z) A(z) = a
0
+
X
n1
(a
n
− a
n−1
) z
n
jest funkcją tworzącą dla ciągu
a
0
, a
1
− a
0
, ..., a
n
− a
n−1
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W6
skalowanie:
A(λz) =
X
n0
λ
n
a
n
z
n
jest funkcją tworzącą dla ciągu
a
0
, λa
1
, λ
2
a
2
, ..., λ
n
a
n
, ...
W7
różnica:
(1 − z) A(z) = a
0
+
X
n1
(a
n
− a
n−1
) z
n
jest funkcją tworzącą dla ciągu
a
0
, a
1
− a
0
, ..., a
n
− a
n−1
, ...
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W8
mnożenie (splot)
A(z)B(z) =
X
n0
X
0¬k¬n
a
k
b
n−k
z
n
jest funkcją tworzącą dla ciągu
a
0
b
0
, a
1
b
0
+ a
0
b
1
, ...,
X
0¬k¬n
a
k
b
n−k
, ...
W9
sumy częściowe:
A(z)
(1 − z)
=
X
n0
X
0¬k¬n
a
k
z
n
jest funkcją tworzącą dla ciągu
a
0
, a
0
+ a
1
, a
0
+ a
1
+ a
2
, ...,
X
0¬k¬n
a
k
, ....
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
Własności funkcji tworzących
W8
mnożenie (splot)
A(z)B(z) =
X
n0
X
0¬k¬n
a
k
b
n−k
z
n
jest funkcją tworzącą dla ciągu
a
0
b
0
, a
1
b
0
+ a
0
b
1
, ...,
X
0¬k¬n
a
k
b
n−k
, ...
W9
sumy częściowe:
A(z)
(1 − z)
=
X
n0
X
0¬k¬n
a
k
z
n
jest funkcją tworzącą dla ciągu
a
0
, a
0
+ a
1
, a
0
+ a
1
+ a
2
, ...,
X
a
k
, ....
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
TWIERDZENIE
Jeżeli {a
n
}
n∈N
spełnia rekurencję
a
n
= x
1
a
n−1
+ x
2
a
n−2
+ ... + x
t
a
n−t
dla
n t
wówczas funkcja tworząca a(z) =
P
n0
a
n
z
n
jest postaci
a(z) =
f (z)
g (z)
,
gdzie
g (z) = 1 − x
1
z − x
2
z
2
− ... − x
t
z
t
,
natomiast f jest wielomianem zdeterminowanym przez wartości
początkowe ciągu a
0
, ..., a
t−1
.
ALEKSANDRA ORPEL
Rozwiązywanie rekurencji za pomocą funkcji tworzących
TWIERDZENIE
Jeżeli {a
n
}
n∈N
spełnia rekurencję
a
n
= x
1
a
n−1
+ x
2
a
n−2
+ ... + x
t
a
n−t
dla
n t
wówczas funkcja tworząca a(z) =
P
n0
a
n
z
n
jest postaci
a(z) =
f (z)
g (z)
,
gdzie
g (z) = 1 − x
1
z − x
2
z
2
− ... − x
t
z
t
,
natomiast f jest wielomianem zdeterminowanym przez wartości
początkowe ciągu a
0
, ..., a
t−1
.
ALEKSANDRA ORPEL