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

. (1)

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

Из последнего равенства следует, что у многочлена коэффициенты при положительны. Из предыдущих равенств следует, что

.

2. Имеем

Приравнивая коэффициенты при в правых частях последних равенств получаем нужное утверждение. n

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

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

Заметим, что удобных простых формул для вычисления чисел Стирлинга первого рода не найдено.

Теорема 2. Число всех подстановок степени n, раскладывающихся в произведение k циклов, равно .

Доказательство. Из равенства (1) следует, что двойная последовательность , где удовлетворяет рекуррентному уравнению

, 1£ k £ n +1, (2)

с начальными и граничными условиями:

для всех n Î N. (3)

Заметим, что рекуррентное уравнение, начальные и граничные условия полностью определяют двойную последовательность .

Обозначим, для n, k Î N, - число всех подстановок степени n, раскладывающихся в произведение k циклов. Положим , имеем , .

Рассмотрим те подстановки степени n +1, раскладывающиеся в произведение k циклов, у которых число n +1 расположено в цикле длины 1. Таких подстановок существует .

Рассмотрим те подстановки степени n +1, раскладывающиеся в произведение k циклов, у которых число n +1 расположено в цикле длины >1. Такие подстановки можно получить из подстановок степени n, раскладывающихся в произведение k циклов, размещая число n +1 на n местах в циклах. Число таких подстановок равно .

Из выше доказанного следует, что , т.е. последовательность удовлетворяет рекуррентному уравнению (2) с начальными и граничными условиями (3). Поэтому для всех 1£ k £ n. n