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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

Пример 5.2.
Найти
1
1
2
()()
n
nk
n
k
nknkC
−
−
−
+
−−
∑
.
Решение
: Запишем исходную сумму в виде
2
2
1
1
.
n
k
n
k
kC
−
−
=
∑
Обозначим
2
11
,,
kk
knknkn
xkCykCzC
1
.
k
−
−−
===
Соответствующие ПФ имеют вид:
1
22
11
00 1
11
1
11
11
() ,
() , () (1 ) .
n
kkkkk
kn n
kk k
nn
kk kk n
nn
kk
Xs xs kC s kC s
Ys kC s Zs C s s
∞∞ −
−−
== =
−−
−
−−
==
== =
===
∑∑ ∑
∑∑
+
Т.к. y
k
=kz
k
, то Y(s)=sZ'(s). Т.к. x
k
=ky
k
, то
X(s)=sY'(s)=sZ'(s)+s
2
z
4
(s)=s(n-1)(1+s)
n+2
+s
2
(n-1)(n-2)(1+s)
n-3
.
Далее, поскольку
1
2
1
1
(1) ,
n
k
n
k
XkC
−
−
=
=
∑
то искомая сумма равна X(1)-(n-1)
2
=n(n-1)2
n-3
-(n-1)
2
.
Лекция 6. Генерирование комбинаторных объектов. Пере-
становки. Сочетания. Разбиение чисел. Подмно-
жества множеств.
Перестановки
Определение. Если
δ
={
δ
1
,…,
δ
n
} и
τ
={
τ
1
,…,
τ
n
} - перестановки,
то
δ
лексикографически меньше
τ
, если и только если для некото-
рого k
≥
1 мы имеем
δ
j
=
τ
j
, для всех j<k и
δ
k
<
τ
k
.
Иными словами последовательность перестановок на множест-
ве {1,…,n} представлена в лексикографическом порядке, если она
записана в порядке возрастания получающихся чисел.
Например: лексикографическая последовательность перестано-
вок трех элементов имеет вид: 123, 132, 213, 231, 312, 321.
Алгоритм лексикографического порождения перестановок мо-
21

Страницы