Теорема 1. Для всех n, kÎN

. (1)

Доказательство. Пусть U ={ } есть n +1 элементное множество. Рассмотрим все разбиения множества U на k блоков.

Число всех тех разбиений множества U на k блоков у которых есть блок

{ } равно .

Подсчитаем число всех тех разбиений множества U на k блоков в которых элемент лежит в некотором блоке мощности >1. Каждое такое разбиение можно получить из разбиения множества { } на k блоков добавляя элемент в один из k блоков. Поэтому число всех разбиений множества U на k блоков в которых элемент лежит в некотором блоке мощности >1 равно .

Из выше доказанного следует (1). n

Равенство (1) даёт удобный рекуррентный способ вычисления чисел Стирлинга второго рода, аналогичный треугольнику Паскаля.

Таблица чисел Стирлинга второго рода.

n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 7	r = 1	r = 2	r = 3	r = 4	r = 6	r = 7	r = 8

Определение. Если - разбиение множества U, то кортеж ( называется упорядоченным разбиением множества U на k блоков.

Число упорядоченных разбиений n элементного множества на k блоков равно .

Теорема 2. Пусть A, B - конечные множества, | A | = n, | B | = k. Тогда число всех сюръекций f: A ® B равно .

Доказательство. Обозначим элементы множества B = { }. Сюръекцию f: A ® B зададим табличным способом

,

где кортеж является упорядоченным разбиением множества A на k блоков, отсюда следует нужное утверждение. n

Свойства чисел Стирлинга второго рода.

1. Для всех k Î N , n Î N справедливо равенство

. (2)

Доказательство. Пусть k, n Î N. Вычислим двумя способами P - число всех функций f: {1,..., n }®{1,..., k }.

По следствию 2 п.3, P = .

Каждая функция f:{1,..., n }®{1,..., k } разбивает множество {1,..., n } на r блоков на которых функция f постоянна, 1£ r £ k. Поэтому функция f определяет инъекцию ` f:{ }®{1,..., k }, где ` f () = f (b) для любого b Î . Верно и обратная, каждая инъекция ` f:{ }®{1,..., k } определяет функцию f:{1,..., n }®{1,..., k }, где f (b) =` f () для b Î . Поэтому

.

Из выше доказанного следует равенство (1). n

2. Для всех n Î N справедливо равенство многочленов

. n

3. Для всех n, k Î N

. (3)

Доказательство. Пусть n фиксировано. Из свойства 1 следует, что

, k Î N .

Перепишем это равенство в виде

, k Î N .

Применяя к последнему равенству биномиальное обращение из п. 8 получим равенства (3). n

Число разбиений данного типа.

Определение. Пусть p - разбиение n элементного множества U. Если p содержит блок мощности 1, блоков мощности 2,..., блоков мощности n, то кортеж (, ,..., )Î N называется типом разбиения p.

Если (, ,..., ) - тип некоторого разбиения n элементного множества, то .

Пример 1. Тип разбиения p=3|1,2 равен (1,2,0). n

Обозначение. Обозначим число всех разбиений n элементного множества имеющих тип (, ,..., ).

Теорема 3. Для всех n Î N, (, ,..., )Î N таких, что

, справедливо равенство

. (4)

Доказательство. Докажем равенство (4) индукцией по числу n.

Если n = 1, то равенство (4) очевидно выполнено.

Предположим, что равенство (4) доказано для числа n - 1 и докажем его для числа n.

Пусть U = { } - n - элементное множество, (, ,..., )Î N , . Имеем или .

Докажем равенство (4) для . В этом случае равно числу разбиений множества U не имеющих блока мощности n. Каждое такое разбиение можно получить из разбиений множества следующими способами.

1-й способ. К каждому разбиению множества V типа добавим блок { }. Легко видеть, учитывая индукционное предположение, что число таких разбиений равно

.

2-й способ. В каждом разбиении множества V типа добавим элемент в один из блоков мощности 1. Легко видеть, учитывая индукционное предположение, что число таких разбиений равно

.

И т.д.

(n -1)-й способ. В каждом разбиении множества V типа добавим элемент в один из блоков мощности n - 2. Легко видеть, учитывая индукционное предположение, что число таких разбиений равно

.

Из выше доказанного следует

= =

= =

= =

= ,

что совпадает с равенством (4) при = 0.

Если = 1, то и равенство (4) очевидно выполнено. n