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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

n
0
1 0 0 0 0 0
1
0 1 0 0 0 0
2
0 -1 1 0 0 0
3
0 2 -3 1 0 0
4
0 -6 11 -6 1 0
5
0 24 50 35 -10 1
Таблица 3.3. Числа Стирлинга первого рода.
Лекция 4. Формулы включений и исключений.
Формулы включений и исключений
Лемма 4.1. Пусть дано N элементов и n свойств p
1
,…,p
n
. Пусть
- число элементов, обладающих, по крайней мере, свойст-
вами
r1
ii
N
...
n1rpp
r1
ii
,,,... =
. Тогда число элементов N
0
, не обладающих
ни одним из указанных свойств определяется формулой
n12
n
iii
ii
ii
s
ii
n
1i
i0
N1
N1NNNN
s21
s1
21
21
...
...
...
)(
...)(...
−+
+−+++−=
∑∑∑
<<<<=
(4.1)
Доказательство
. Рассмотрим правую часть (4.1). Элемент, не
обладающий свойствами p
1
,…,p
n
, учитывается только в слагаемом
N. Любой элемент A, обладающий ровно r свойствами j
1
,…,j
r
учи-
тывается в выражении
∑
<<<
≤
s
s
iii
ii
rsN
...
...
21
1
,,
s
r
C
раз.
Следовательно, вклад A в правую часть (4.1) равен:
12
1 ... ( 1) ... ( 1) (1 1) 0 0
ss rr r r
rr r r
CC C C−+++− ++− =−==
.
Пример 4.1. (пояснение к предыдущей формуле)
Рассмотрим множество шаров, которые могут быть окрашены в
4 цвета:
желтый – свойство 1;
красный – свойство 2;
синий – свойство 3;
зеленый – свойство 4.
Пусть некоторый шар окрашен одновременно в желтый, крас-
ный и зеленый цвета. Тогда для него N
0
= 0. Теперь рассмотрим,
14

Страницы