Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Обозначение. (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) способами.