Четыре лекции по комбинаторике. Семенов А.С. - 15 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

17
∑∑∑
=
+
=
+
=
=⋅
n
i
mn
k
kk
mn
m
j
jj
m
ii
n
xCxCxC
000
или
∑∑∑
=
+
=
+
=
+
=
n
i
mn
k
kk
mn
m
j
lij
m
i
n
xCxCC
000
.
Так как необходимыми и достаточными условиями тождественного равенства двух
многочленов являются равенства коэффициентов при одинаковых степенях
,x то,
приравнивая коэффициенты при
k
x в правой и в левой части последнего тождест-
ва, получаем .
0
k
mn
k
i
ik
m
i
n
CCC
+
=
−
=⋅
∑
Свойство 6 доказано.
§ 11. Полиномиальная теорема
Теорема 13
Для любых заданных чисел
),...,2,1( kia
i
=
и для любого натурального n
имеет место равенство
,...
!...!
!
)...(
1
1
1
1
...
0,...,0
1
21
k
k
k
r
k
r
nrr
rr
k
n
k
aa
rr
n
aaa ⋅⋅⋅
⋅⋅
=+++
∑
=
+
+
≥≥
(23)
где сумма в правой части распространена на всевозможные разбиения числа
n на
k
целых неотрицательных чисел.
Доказательство. Перемножим последовательно (
k
aa
+
+
...
1
) ( 1−n ) раз. Тогда
получим сумму
n
k
слагаемых вида ,...
21 n
ddd
⋅
⋅
⋅
где ),...,2,1( nid
i
=
равно ли-
бо ,...
1
a , либо .
k
a Обозначим через ),...,(
1 k
rrB множество всех тех слагаемых,
где
1
a встречается множителем
1
r раз,
22
ra
−
раз,…,
kk
ra
−
раз, причем должно
выполнятся равенство ....
21
nrrr
k
=
+
++ Ясно, что каждый элемент множества
−),...,(
1 k
rrB это перестановка с повторением. Следовательно,
.
!...!!
!
),...,()(
21
1
k
kn
rrr
n
rrCBN
⋅⋅⋅
==
Каждое слагаемое из B равно
k
r
k
rr
aaa ⋅⋅⋅ ...
21
21
, поэтому
=++
n
k
aa )...(
1
∑
=
+
+
≥≥
⋅⋅⋅
nrr
rr
r
k
r
k
k
k
k
aarrBN
...
0,...0
11
1
1
1
..)),...,((
,
или
....
!...!
!
)...(
1
1
1
1
...
0,...,0
1
21
k
k
k
r
k
r
nrr
rr
k
n
k
aa
rr
n
aaa ⋅⋅⋅
⋅⋅
=+++
∑
=
+
+
≥≥
Теорема 13 доказана.
Замечание 1. Теорему 13 называют полиномиальной теоремой, а числа
−),...,(
1 kn
rrC
полиномиальными коэффициентами. Формула (23) обобщает фор-
мулу бинома Ньютона (19).
Замечание 2. Если числа
k
ss ,...,
1
получаются из чисел
k
rr ,...,
1
перестановкой, то
).,...,(),...,(
11 knkn
rrCssC = Поэтому, например, в разложении
4
)( zyx ++ ко-
эффициенты при yzx
2
и
2
xyz одинаковы. Это облегчает выписывание членов

Страницы