Теорема 1.

.

Доказательство. Рассмотрим как ящики сомножители произведения

.

Произведение состоит из слагаемых вида . Каждое такое слагаемое встречается столько раз, сколько существует упорядоченных разбиений множества ящиков. Разбиение будет состоять из следующих подмножеств: первое подмножество состоит из ящиков, откуда выбран x₁, второе состоит из подмножеств, откуда выбран x₂ и т.д. Отсюда коэффициент при будет равен P(k₁, k₂, ××× , k_m). Что и требовалось доказать.

Разбиения и перечисление сюръекций. Пусть {B₁, ××× , B_k } – разбиение множества X, состоящего из n элементов. Обозначим через P_k(X) множество разбиений X на k блоков, а через P(X) – множество всех разбиений. Число S(n,k) = |P_k(X)| называется числом Стирлинга второго рода, B_n=|P(X)| – числом Белла. Ясно, что . Каждому разбиению мы сопоставили отношение эквивалентности и заметили, что разбиения составляют решетку относительно включения соответствующих отношений эквивалентности. Отсюда множество разбиений будет решеткой относительно неравенства p£s Û каждый блок BÎs является объединением некоторых блоков из p. Например, {{1},{2},{3}}£{{1},{2,3}}.

Пусть s_n,k – число сюръекций f:{1,2, ××× ,n}® {1,2, ××× , k}. Каждой сюръекции соответствует разбиение {f ^–1(y): 1 £ y £ k}. Отсюда легко видеть, что s_n,k =k!S(n,k). Положим S(0,0)=1.

Пример 2. Число S(4,2) равно 7, ибо все разбиения множества {1,2,3,4, 5, 6, 7} на два блока исчерпываются следующими:

{{1},{2,3,4}}, {{2},{1,3,4}}, {{3},{1,2,4}}, {{4},{1,2,3}},

{{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}} .

Теорема 2. Имеют место следующие свойства чисел Стирлинга второго рода:

· S(n,k)=0, при k > n.

· S(n,0)=0 и S(n,n)=1, при n>0.

· S(n,k)=S(n-1,k-1)+kS(n-1,k), при 0 < k < n .

Доказательство. Докажем последнее соотношение. Множество разбиений множества {1,2, ××× ,n} состоит из двух классов:

(1) разбиения, содержащие блок {n} ;

(2) разбиения, для которых n принадлежит блокам, имеющим более одного элемента.

В первом классе S(n-1,k-1) разбиений.

Во втором классе получаем kS(n-1,k) разбиений, ибо каждому разбиению множества {1, 2, ×××, n-1} на k блоков B₁, B₂, ××× , B_k соответствует k разбиений

B₁ È {n}, B₂, ××× , B_{k ,}

B₁, B₂È {n}, ××× , B_{k ,}

×××××××××××××××××××××××××××××××

B₁, B₂ , ××× , B_k È {n}_,

Следовательно, S(n,k)=S(n-1,k-1)+kS(n-1,k), при 0 < k < n .

Составим таблицу для нахождения чисел Стирлинга:

n k

Пример 3. Найдем число сюръекций {1,2,3,4,5,6}®{1,2,3,4}. Оно равно 4!S(6,4). Число S(6,4) находим из таблицы. Отсюда искомое число = 4!∙65 = 1∙2∙3∙4∙65 = 1560.

Положим B₀=1. Число Белла B_n можно вычислить по формуле .

Рассмотрим более простые формулы для нахождения чисел Белла.

Теорема 3. , "n ³ 0 .

Доказательство. Множество разбиений X={1,2, ×××, n+1} состоит из классов, зависящих от блока A содержащего n+1. Для таких A будет справедливо включение X\A Í{1, 2, ×××, n}. Отсюда каждое разбиение можно получить, выбрав блок A ' n+1 и разбиение pÎP(X\A). Выбор блока A с |A|=k+1, будет осуществляться выбором подмножества из {1,2, ××× ,n}, состоящего из k элементов. Следовательно, .