ВУЗ:
Составители:
Рубрика:
распадается на два различных класса: множество тех разбиений,
которые содержат одноэлементный блок {n}, и тех разбиений, для
которых n является элементом большего (по крайней мере, двух-
элементного) блока. Мощность первого класса равна S(n-1,k-1), т.е.
равна числу разбиений множества {1,…,n-1} на k-1 блоков. Мощ-
ность второго класса составляет kS(n-1,k), т.к. каждому разбиению
множества {1,…,n-1} на k блоков соответствует в этом классе в
точности k разбиений, образованных добавлением элемента n по-
очередно к каждому блоку.
Теорема (3.1) позволяет легко вычислять S(n,k) даже для боль-
ших значений n и k. В следующей таблице представлены числа
S(n,k) для .
8kn0 ≤≤ ,
12826610501701966127108
012114035030163107
00115659031106
0001102515105
0000167104
0000013103
0000001102
0000000101
0000000010
876543210
n
k
Таблица 3.1. Числа Стирлинга второго рода.
Данную таблицу можно трактовать как «треугольник Стирлин-
га», в котором каждое значение кроме крайних, равных единице,
можно получить как сумму числа, расположенного над ним и ум-
ноженного на k, и числа над ним с левой стороны.
1
1
(,) (, 1), 2.
n
k
n
ik
Snk CSik k
−
=−
−≥
∑
Теорема 3.2.
=
Доказательство.
Рассмотрим множество всех разбиений множества А={1,…,n}.
Это множество распадается на различные классы, соответствую-
щие разным подмножествам множества А, которые являются бло-
ками, содержащими элемент n. Для каждого b-элементного под-
11
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
