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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

8
=
1
11
1
0
11
11
11
00
11
11
11
00
01 1 1 2 2 2 11
11 1 1
()()()()
{распишем суммы}
...
k
kkrrkr
k
r
kk
rrkr rrkr
kk
rr
kk
r r kr r r kr
kk
rr
kkkkk
kk k k
xy xyxy xy Cxy
xC x y yC x y
Cxy Cxy
Cxy Cxy C xy C
−
−−−
−
=
−−
−− −−
−−
==
−−
+−− −
−−
==
−−−−
−− − −
+=+ + =+ =
=+=
=+=
=+ ++ +
∑
∑∑
∑∑
10
00 11 1 2 22 1 11
11 1 1
110 1 2 21 2
11 11
22 3 2 11 2 1
11 11
10 00
11
...
{приведем подобные}=
= ( ) ( ) ...
()()
k
kkkkkk
kk k k
kk
kk kk
kkkkkk
kk kk
kk k
kk
xy
Cxy Cxy C x y Cxy
xyCC xyCC
xyC C xyC C
Cxy Cxy
−
−−−−−
−− − −
−−
−− −−
−−−−−−
−− −−
−
−−
+
++ ++ + =
=
++ +++
+++++
++=
1
11
111 112 22 2 11 1 0
00
0
{по свойству }
...
(,) . Теорема доказана.
rrr
kkk
kk kkkknk
kk k kn
k
krrkr
nk
r
CCС
x
yC xyC x yC xyC Cxy
Cxy C nrxy
−
−−
−− −−−−
−
=
+==
=+++ + +
+=
∑
+
Следствие 1.
0
2
n
rn
n
r
C
=
=
∑
.
Доказательство.
Пусть 1, 1
x
y
=
= .
00
2(11) 11
nn
nnrrnrr
nn
rr
CC
−
==
=+ = ⋅⋅ =
∑∑
.
Следствие 2.
0
(1) 0
n
rr
n
r
C
=
−=
∑
.
Доказательство.
Пусть 1, 1
x
y
=
−=.
00
0(11) (1)1 (1)
nn
nrrnr rr
nn
rr
CC
−
==
=−+ = − = −
∑∑
.
Биномиальные коэффициенты обладают рядом интересных

Страницы