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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

Числа Стирлинга первого рода
Введем следующее обозначение многочлена
0
1
2
3
[ ] ( 1)...( 1)
Для частных случаев:
[] 1,
[] 1,
[] ( 1),
[] ( 1)( 2).
k
xxx xk
x
x
xxx
xxx x
=− −+
=
=
=−
=−−
.
Определение.
Числа Стирлинга первого рода s(n,k) есть коэф-
фициенты при последовательных степенях переменной x в много-
члене :
k
x][
∑
=
=
n
0k
k
n
xknsx ),(][
.
Очевидно, что s(n,k)=0 для k>n.
Теорема 3.4.
),()(),(),( k1ns1n1k1nskns
, для
,nk0
<
<
(3.4)
−−=
−
−
−
1nns =),(
, для (3.5)
,0n ≥
00ns =),(
, для (3.6)
.0n >
Доказательство.
Формулы (3.5) и (3.6) очевидны. Формулу (3.4) получим, срав-
нивая коэффициенты при в обеих частях равенства
k
x
).(][][ 1nxxx
1nn
+−
=
−
Имеем
).,()(),(
)),()(),((
),()(),(
),()(),(
01ns1nx1n1ns
xk1ns1n1k1ns
xkns1nxk1ns
xk1ns1nxxkns
n
1n
1k
k
1n
0k
1n
0k
k1k
1n
0k
k
n
0k
k
−−−−−+
+−−−−−
=−−−=
=−=−=
∑
∑∑
∑∑
−
=
−
=
−
=
+
−
==
13
k 0 1 2 3 4 5

Страницы