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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

Дифференцируя (4.3) r раз по x, получим
( 1)...( 1)(1 ) ( 1)...( 1)
n
nr k kr
n
kr
nn n r x Ckk k r x
−
−
=
−−++= −−+
∑
.
Последнее равенство преобразуется к виду
!!
(1 )
()! ()!
n
nr k kr
n
kr
nk
x
Cx
nr kr
−−
=
+=
−−
∑
.
Разделив обе части на r! приходим к соотношению
(1 )
n
rnr krk
nn
kr
Cx CCx
−−
=
+=
∑
r
k
,
которое при дает
1x =−
(1) 0
n
kr k r
nk
kr
CC
−
=
−=
∑
.
Лемма 4.3. Пусть дано N элементов и n свойств s
1
,…,s
n
. Пусть
- число элементов, обладающих по крайней мере свойствами
i
r1
ii
N
...
1
,…,i
r
,
n1r ,=
. Тогда число элементов N(r), обладающих ровно r
свойствами определяются формулой
11
11
1
1
... ...
1... 1...
12... ...
1...
() (1)
(1) (1) .
rs
s
s
s
sr r
ii s ii
iin iin
n
nr r ns r
nn s ii
sr i i n
Nr N C N
CN C N
−
≤<<≤ ≤<<≤
−−
=≤<<≤
s
=
++− +
+− = −
∑∑
∑∑

(4.4)
Доказательство.
В левой части (4.4) элемент с ровно r свойст-
вами учитываются один раз. В правой части (4.4) элемент с ровно r
свойствами учитываются один раз в первом слагаемом и не учи-
тываются далее. Элемент с ровно t свойствами, t>r, учитывается
(1)
s
rrs
s
t
CC
−
−
раз в слагаемом
1
1
...
1...
(1)
s
s
sr r
s
ii
iin
CN
−
≤<<≤
−
∑
.
Поэтому вклад от элементов с ровно t свойствами, t>r, состав-
ляет
(1)
t
rrs
s
t
sr
CC
−
=
−
∑
. В силу леммы 4.2 эта сумма равна нулю.
16
Пример 4.3
(задача о встречах). Определить количество пере-
становок a
1
,…,a
n
чисел 1,…,n , для которых a
i
=i ровно в r местах.

Страницы