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

Обозначение. (t)_n=t(t-1)…(t-n+1).

Числа Стирлинга определяются следующим образом. Положим

(t)₀=t⁰=s(0,0)=S(0,0)=1

(t)_n=t(t-1)…(t-n+1)=, n>0 (1)

tⁿ=, n>0. (2)

Тогда s(n,k) и S(n,k) называются числами Стирлинга соответственно первого и второго рода. Заметим, что числа обоих рядов отличаются от нуля только для k=1,2,…,n, n>0 и что (t)_n является обычной производящей функцией для s(n,k), тогда как tⁿ является новым типом производящей функции для входящей в уравнение (*) функции f_k(t), равной (t)_k.

Упражнение. Докажите, что совокупность функций {(t)₀,(t)₁,…,(t)_n} линейно независима.

Для заданного n или k числа Стирлинга первого рода s(n,k) могут иметь тот или иной знак, действительно

(-t)_n=(-1)ⁿt(t+1)…(t+n-1),

тогда из (1) немедленно следует, что (-1)^n+ks(n,k) всегда положительно. Кроме того, учитывая вид производящей функции С_n(t), получаем С(n,k)=(-1)^n+ks(n,k). Т. е модули чисел Стирлинга первого рода s(n,k) определяют число перестановок n-го порядка с k циклами.

Рекуррентные соотношения для чисел Стирлинга первого рода s(n k) вытекают из соотношения для факториалов (t)_n=(t-n+1) (t)_n-1, т.е.

s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).

Для чисел Стирлинга второго рода, используя (2), находим

tⁿ==t=

и

S(n+1,k)= S(n,k-1)+k S(n,k). (3)

С числами Стирлинга второго рода можно связать разбиения конечных множеств, а именно:

Пусть Х={1,2,…,n}, рассмотрим всевозможные разбиения Х на k блоков. Множество таких разбиений будем обозначать П_k(X), пусть u(n,k)=|П_k(X)|, тогда

u(0,0)=1 u(n,k)=u(n-1,k-1)+k×u(n-1,k). (4)

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

Разобьем П_k(X) на два различных класса:

– тех разбиений, которые содержат одноэлементный блок {n}, и

– тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока.

Мощность первого класса равна u(n-1,k-1). Т. е. такова, каково число разбиений множества {1,2,…,n-1} на k-1 блоков.

Мощность другого класса составляет k×u(n-1,k), так как каждому разбиению множества {1,2,…,n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочередно к каждому блоку.

Следствие. Сравнивая (3) и (4), получаем S(n,k)=u(n,k), т. е.

Числа Стирлинга 2-го рода S(n,k) определяют число разбиений n-элементного множества на k дизъюнктных блоков.

Исходя, из соотношения 3 легко построить таблицу для чисел Стирлинга 2-рода при небольших значений n и k:

Теорема. Числа Стирлинга 2-го рода удовлетворяют тождеству

S(n,k) = , k≥2

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

Обозначим ) всех множество разбиений Х={1,2…,n} на k дизъюнктных подмножеств. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что каждого b-элементного множества BХ, содержащего элемент n, существует в точности S(n-b,k-1) разбиений множества X на k блоков, содержащих B в качестве блока. Действительно, каждое такое разбиение однозначно соответствует разбиению X\B на k-1 блоков. b-элементное множество BХ, содержащее элемент n, можно выбратьспособами; таким образом,

S(n,k) = ==

Число Белла β_n определяется как число разбиений n-элементного множества, т. е. β_n=||=, другими словами

β_n=

Теорема. Справедливо следующее тождество: β_n=.

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

Принимаем β₀=1. проведем комбинаторное доказательство тождества, аналогичное предыдущему.

Множество всех разбиений множества Х={1,2,…,n+1} можно разбить на различные классы в зависимости от блока В, содержащего элемент n+1, или – что равнозначно – в зависимости мощности Х\В. Для каждого множества Х\В {1,2,…,n} существует в точности || = β_|х\в| разбиений множества Х, содержащих В в качестве блока. Группируя наши классы в зависимости от мощности множества Х\В, получаем требуемое тождество.

Теорема. Пусть |X|=n, |Y|=k, то число всех функций f:X®Y и f(X)=Y, равно S_n,k=k!S(n,k).

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

Зафиксируем конкретное разбиение Х на k дизъюнктных подмножеств, тогда существует k! вариантов отображений, при которых каждому элементу разбиения сопоставляется биективно элемент Y. Каждое конкретное разбиение можно выбрать S(n,k) способами.