Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 18 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

Основные операции
Пусть x
k
, y
k
, z
k
, k=0,1,2… - последовательности, а X(s), Y(s) и Z(s)
- соответствующие им ПФ.
Линейные операции
Если a и b - константы, то последовательность z
n
=ax
n
+by
n
имеет
ПФ z(s)=aX(s)+bY(s).
18
Доказательство.
)()(
)()(
sbYsaX
sybsxasbyaxszsZ
0k
k
n
0k
k
n
0k
k
kk
0k
k
k
+=
=+=+==
∑∑∑∑
∞
=
∞
=
∞
=
∞
=
Сдвиг начала
Последовательность y
k
=0, для k=0,…,i-1; y
k
=x
k-i
, k=i,i+1,… име-
ет производящую функцию Y(s)=X(s)s
i
.
Доказательство.
)(
)(
sXssxs
sxssxsysysY
i
0k
k
k
i
ik
ik
ik
ik
ik
ik
ik
k
k
0k
k
k
∑
∑∑∑∑
∞
=
∞
=
−
−
∞
=
−
∞
=
∞
=
==
=====
Последовательность y
k
= x
k+i
, k=0,1,2,… имеет ПФ
1
0
1
() ()
i
k
k
i
k
Ys Xs xs
s
−
=
⎡⎤
=−
⎢⎥
⎣⎦
∑
Доказательство.
11
00 0 00
11
00 0
1
()
11
()
ii
kk kikk
kki ki k k
i
kk k kk
ii
kk k
kk k
ii
kk k
Ys ys x s x s xs xs
s
xs xs X s xs
ss
∞∞ ∞ − −
+
++
== = ==
∞− −
== =
⎡
⎤
=
== +−=
⎢
⎥
⎣
⎦
⎡⎤⎡⎤
=−=−
⎢⎥⎢⎥
⎣⎦⎣⎦
∑∑ ∑ ∑∑
∑∑ ∑
Частичные суммы
Если то
∑
=
==
k
0i
ik
210kxy ,...,,,,
s
1
sX
sY
−
=
)(
)(
.
Доказательство.

Страницы