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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

множества , содержащего элемент n, существует в точности
S(n-b,k-1) разбиений множества А на k блоков, содержащих B в ка-
честве блока. Действительно, каждое такое разбиение однозначно
соответствует разбиению множества А\В на k-1 блоков. b-
элементное множество , содержащее элемент n, можно вы-
брать С(n-1,b-1) способами. Следовательно
AB ⊆
AB ⊆
12
).−
(1)
1
1
1
(1)
1
11
11
(,) ( , 1)
(,1) (,1
nk
b
n
b
nk
n
nb i
nn
bik
Snk C Sn bk
CSnbk CSik
−−
−
−
=
−−
−
−
−−
==−
=−−=
=−−=
∑
∑∑
Число Белла
Определение. Число Белла есть число всех разбиений n-
элементного множества
n
B
)(AB
n
Π
=
, где
.nA =
Другими словами
∑
=
=
n
0k
n
knSB ).,(
1
0
n
i
nni
i
CB
+
=
=
∑
.
Теорема 3.3.
B
Доказательство.
Множество всех разбиений множества A={1,…,n+1} можно
разбить на различные классы в зависимости от блока В, содержа-
щего элемент n+1 (или в зависимости от множества А\В). Для каж-
дого множества существует в точности
},...,{\ n1BA ⊆
BA
BBA
−
=)\(
Π
разбиений множества А, содержащих В в каче-
стве блока. Группируя классы в зависимости от мощности множе-
ства А\В, получаем требуемую формулу.
B(0)=1
B(1)=1
B(2)=2
B(3)=5
B(4)=15
B(5)=52
B(6)=203
Таблица 3.2. Числа Белла.

Страницы