ВУЗ:
Составители:
Рубрика:
Лекция 3.Разбиения множества. Числа Стирлинга второго
рода. Число Белла. Числа Стирлинга первого рода.
Разбиения множества
Под разбиением n-элементного множества А на k блоков будем
понимать произвольное семейство
},...,{
k1
BB
=
π
, такое что
, для
ABB
k1
=∪∪ ...
OBB
ji
/∩ kji1
≤
<
≤
и OB
i
/
≠
для
. Подмножества будем называть блоками се-
мейства
ki1 ≤≤
k1
BB ,...,
π
. Множество всех разбиений множества А на k блоков
будем обозначать , а множество всех разбиений через
.
)(A
k
Π
)(A
Π
Числа Стирлинга второго рода
Определение. Число Стирлинга второго рода S(n,k) есть число
разбиений n-элементного множества на k блоков:
)(),( AknS
k
Π
=
, где
.nA =
Пример 3.1.
S(4,2)=7, так как множество {1,2,3,4} можно раз-
бить на 2 блока семью различными способами:
{{1,2,3},{4}}
{{1,2,4},{3}}
{{1,3,4},{2}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}
{{1},{2,3,4}}
Очевидно, что S(n,k)=0 для k>n. Положим также S(0,0)=1, т.к.
по определению пустое семейство блоков является разбиением
пустого множества.
Докажем теперь тождество, аналогичное тождеству, связанно-
му с треугольником Паскаля.
Теорема 3.1.
),(),(),( k1nkS1k1nSknS
для
,nk0
≤
<
(3.1)
−=
−
+
−
1nnS =),(
для (3.2)
,0n ≥
00nS =),(
для (3.3)
,0n >
Доказательство.
Формулы (3.2) и (3.3) очевидны. Докажем (3.1). Рассмотрим
множество всех разбиений множества {1,…,n} на k блоков. Оно
10
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
