флеров

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

Выражение [x]_n является полиномом степени n от переменной x, следовательно его можно представить в виде следующего разложения по степеням x:

[x]_n= s(n,0) + s(n,1)x +...+ s(n,n)xⁿ .

По определению, коэффициенты s(n,k) такого разложения называются числами Стирлинга первого рода.

Утверждение 1.3. Числа Стирлинга первого рода удовлетворяют следующим рекуррентным соотношениям:

s(n, 0)= 0;

s(n, n)= 1.

Доказательство. По определению

[x]_n+1 = [x]_n(x-n).

Представляя полиномы в левой и правой частях равенства в виде разложения по степеням x, получим

s(n+1,n+1)xⁿ⁺¹ +  + s(n+1, k)x^k+ +s(n+1,0)=

(s(n,n)+  +s(n, k-1)x^k-1 + s(n,k)x^k +  +s(n,0))(x-n).

Вычисляя и приравнивая коэффициенты при x^k слева и справа, получаем первую формулу утверждения. Другие две формулы очевидны. 

Утверждение 1 .3 дает эффективный способ рекуррентного вычисления чисел Стирлинга первого рода.

Приведем часть значений таблицы s(n,k) для начальных значений n и k :

Отметим связь чисел Стирлинга первого рода, в частности рекуррентного соотношения для них, с изучением циклической структуры перестановок.