Числа Стирлинга 1-го рода

Число сюръективных функций, то есть число размещений m предметов по n ящикам, таких, что все ящики заняты, называется числом Стирлинга первого рода и обозначаются s(m,n).

Число Белла (Эрик Темпл Белл (1883-1960))

Число всех разбиений m -элементного множества называется числом Белла и обозначается B(m):

Числа Белла:

B(0) = 1

B(1) = 1

B(2) = 2

B(3) = 5

B(4) = 15

B(5) = 52

B(6) = 203

Также существуют число Белла B(n), которое означает число всевозможных вариантов разбиения множества M на непустые подмножества.

)

Утверждение 1. Для определения S (n,k) существует рекуррентная формула S(n,k) = S(n-1,k-1)+ k S(n-1,k).

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

M: card (M) = n

M = {a₁,a₂,…,a_n}\

M {a_n}

Существует два способа присоединения {a_n} к M:

1) Пусть M было разбито на k-1 непустых подмножества, тогда {a_n} можно было бы присоединить отдельным k -м подмножеством.

2) Множество M {a_n} было разбито на k непустых подмножества, тогда элемент {a_n} можно было бы присоединить к любому из уже существующих подмножеств. Всего k вариантов.