Элементы дискретной математики - 33 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

33
Запишем (x
1
+x
2
+…x
k
)
n
в виде произведения n сомножителей
(x
1
+x
2
+…x
k
)·(x
1
+x
2
+…x
k
)·…·(x
1
+x
2
+…x
k
).
Раскроем скобки в правой части этого равенства и запишем все слагаемые в виде
произведения n сомножителей x
1
, x
2
,…,x
k
в том порядке, в котором они появляются.
Получим всевозможные размещения с повторениями букв x
1
, x
2
,…,x
k
, состоящие из n
элементов. Используем коммутативность и приведем подобные члены. Подобными будут
члены, содержащие одинаковое количество множителей x
1
, x
2
,…,x
k
. Членов, в которые
входит k
1
множителей х
1
, k
2
множителей х
2
и так далее k
m
множителей х
m
, ровно
Р(k
1
,k
2
,…k
m
). Отсюда вытекает, что после приведения подобных членов выражение
m
k
m
kk
xxx ...
21
21
⋅⋅ войдет с коэффициентом ),...,,(
21 m
kkkP . Поэтому формула примет вид:
∑∑
=+++=
=
⎟
⎠
⎞
⎜
⎝
⎛
nkkk
k
m
kk
m
n
m
i
i
m
m
xxxkkkPx
...
2121
1
21
21
...),...,,(.
Свойства чисел Р(k1k2…k3)
1.
∑
=+++
=
nkkk
n
m
m
mkkkP
...
21
21
),...,,(
.
Доказательство.
Если в полиномиальной формуле положить х
1
=х
2
=…=х
m
=1, то получим требуемое
равенство.
2. )1,...,,(...),...,1,(),...,,1(),...,,(
21212121
−
+
+
−
+
−
=
mmmm
kkkPkkkPkkkPkkkP .
Доказательство.
Умножим обе части равенства
∑∑
−=+++
−
=
=
⎟
⎠
⎞
⎜
⎝
⎛
1...
2121
1
1
21
21
...),...,,(
nkkk
k
m
kk
m
n
m
i
i
m
m
xxxkkkPx на (х
1
+х
2
+…+х
m
). Получим
)...)(...),...,,((
21
1...
2121
1
21
21
m
nkkk
k
m
kk
m
n
m
i
i
xxxxxxkkkPx
m
m
+++=
⎟
⎠
⎞
⎜
⎝
⎛
∑∑
−=+++=
.
Применим к левой части полиномиальную формулу, а в правой части раскроем скобки и
рассмотрим коэффициент при
m
k
m
kk
xxx ...
21
21
⋅⋅ . Слева он будет равен ),...,,(
21 m
kkkP . В правой
части член, содержащий
m
k
m
kk
xxx ...
21
21
⋅⋅ , появится m раз: при умножении
),...,,1(
21 m
kkkP −
m
k
m
kk
xxx ...
21
2
1
1
⋅⋅
−
на х
1
, при умножении ),...,1,(
21 m
kkkP
−
m
k
m
kk
xxx ...
1
21
21
⋅⋅
−
на
х
2
и так далее коэффициент при
m
k
m
kk
xxx ...
21
21
⋅⋅ будет равен
)1,...,,(...),...,1,(),...,,1(
212121
−
+
+−+−
mmm
kkkPkkkPkkkP . Слева и справа стоит один и тот

Страницы