![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Коэффициенты многочлена называются числами Стирлинга первого рода и обозначаются
они определяются равенствами
.
Из определения чисел Стирлинга первого рода следует, что:
для всех n Î N
;
для всех n Î N;
для всех n Î N;
для всех n Î N
.
Теорема 1. Справедливы утверждения:
1. Для всех n Î N числа отличны от 0 и имеют чередующиеся знаки.
2. Для всех n, k Î N
. (1)
Доказательство. 1. Имеем
Из последнего равенства следует, что у многочлена коэффициенты при
положительны. Из предыдущих равенств следует, что
.
2. Имеем
Приравнивая коэффициенты при в правых частях последних равенств получаем нужное утверждение. n
Равенство (1) даёт удобный рекуррентный способ вычисления чисел Стирлинга первого рода, аналогичный треугольнику Паскаля.
Таблица чисел Стирлинга первого рода.
Sn,r n =1 n =2 n =3 n =4 n =5 n =6 n =7 | r =1 -1 -6 -120 | r =2 -3 -50 -1764 | r =3 -6 -225 | r =4 -10 -735 | r =5 -15 | r =6 -21 | r =7 |
Заметим, что удобных простых формул для вычисления чисел Стирлинга первого рода не найдено.
Теорема 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
Дата публикования: 2015-01-23; Прочитано: 387 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!