Министерство развития информационных технологий и коммуникации республики узбекистан

Числа Стирлинга, Белла

Числа Стирлинга первого и второго рода

S – второго рода; s (малая) – первого рода
Числа Стирлинга второго рода – S(n,k) – число разбиенийn элементного пространства наk не пересекающихся подмножеств.
S(4,2) = 7 {1,2,3,4} | {1,2,3} {4}
{1,2,4} {3}
{1,3,4} {2}
{2,3,4} {1}
{1,2} {3,4}
{1,3} {2,4}
{1,4} {2,3}
Свойства чисел Стирлинга

1. 
   S(0,0)=1
   
2. 
   S(n,k)=0 приk>n
   
3. 
   S(n,0)=0
   

S(n,n)=1

4. 
   S(n,k)=S(n-1,k-1)+kS(n-1,k) 0

Доказательство:
Рассмотрим разбиение n множества наk не пересекающихся подмножеств.
Разбиение: Разобьем на 2 группы:
{n} {n…}
Разбиение содержит только n в комбинации с другими элементами элемент
Остается n-1, разбиваем наk-1 n выбран, n фиксировано, ноk подмножеств.
S(n-1,k-1) + k S(n-1,k)
В каждом подмножестве S(n-1,k) можно добавитьn и увеличим вk
Треугольник Стирлинга.

n\k	1	2	3	4	5	6
1	1	0	0	0	0	0
2	1	1	0	0	0	0
3	1	3	1	0	0	0
4	1	25	6	1	0	0
5	1	15	25	10	1	0
6	1	31	90	65	15	1

S(2,1) = S(1,0)+ 1 S(1,1)=1
S(n,1)=1
S(3,2)=S(2,1) + 2 S(2,2)

Числа Белла

S(n,k) – Это способы разбиенияn элементного множества наkподмножеств

B_n – это число разбиенийnэлементного множества на все вариантные не пересекающиеся подмножества.
В_n=ⁿ_k=0 S(n,k)
B₀=1
Теорема:28
В_n+1=ⁿ_k=0 C_kⁿB_k
Доказательство:
{1,2,….,n,n+1} - множество,n+1 - фиксировано
из 1..n будем выбирать поk элементов
k=0,1,…,n
Если k=0, все множество
K=n, то останется толькоn+1
Выбирая k остаетсяn+1-i
Оставшееся рассмотрим как одно подмножество.
Всевозможных k разбиенийB_k способами выбрать можно столько элементов – С_kⁿ отсюда В_n+1=ⁿ_k=0 C_kⁿB_k

1. 
   1
   
2. 
   0
   

_ _ _ … _
x₁ x₂ x₃ x_n
x_iX Еслиx₁X, то ставим 1
Если x₁X, то ставим 0
Получается 2ⁿ комбинаций
_A2^A – множество всех подмножеств данного подмножества
i=0,1,2,…,2ⁿ-1
i=0 (0,0,…,0) \
i=1 (0,0,…,1) | Все подмножества данного множества
… |
i=2ⁿ-1(1,1,…,1) /
(0,0,0,1,1,1) Очень сильно отличаются друг от друга
(0,0,1,0,0,0)

Связь с числами Стирлинга второго рода

Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:
Bn=∑nk=0{nk}Bn=∑k=0n{nk},
где число Стирлинга {nk}{nk} является количеством способов разбиения набора элементов nn в ровно kk непустых подмножеств.

Доказательство

Посчитаем количество подмножеств nn-элементного множества. Нам нужно разбить nn-элементное множество на kk непустых подмножеств, где kk от 11 до nn. Пусть C — C — все подмножества nn-элементного множества. Пусть Ak — Ak — разбиение nn-элементного множества на kk непустых подмножеств, тогда C=⋃k=1nAkC=⋃k=1nAk. |Ak|={nk} — |Ak|={nk} — по определению, тогда Bn=|C|=∑nk=1 |Ak|=∑nk=1{nk}=∑nk=0{nk}Bn=|C|=∑k=1n |Ak|=∑k=1n{nk}=∑k=0n{nk}, т.к. {n0}=0{n0}=0.

Объединяющая формула

Майкл Спайви^[3] получил формулу, которая объединяет оба эти суммирования:
Bn+m=∑nk=0∑mj=0{mj}(nk)jn−kBk.Bn+m=∑k=0n∑j=0m{mj}(nk)jn−kBk.

Лемма

Bn+m — Bn+m — количество способов разбить (n+m)(n+m)-элементное множество на подмножества. Количество способов разбить mm-элементное множество на jj непустых подмножеств это {mj}{mj}, где jj меняется от 11 до mm. Из оставшихся nn объектов выберем kk, для разделения их на новые подмножества, а оставшиеся n−kn−k объектов распределим между jj подмножествами, сформированных из mm-элементного множества. Bk — Bk — количество разбиений kk-элементного множества на подмножества и jn−kjn−k способов разбить n−kn−k элементов между jj подмножествами. Значит jn−k{nk}(nk)Bkjn−k{nk}(nk)Bk способов разбить mm элементов на jj подмножеств и выбрать kk элементов из nn-элементного множества и выбрать kk элементов из nn-элементного множества и сформировать из них новые подмножества, а из оставшихся n−kn−k объектов разделить между jj множествами, сформированных из mm-элементного множества.