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

Числа Стирлинга первого рода (без знака) — количествоперестановок порядка n с k циклами.

Определение


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

(x)n=k=0ns(n,k)xk,
 где (x)n — символ Похгаммера (убывающий факториал):

(x)n=x(x1)(x2)(xn+1).
 Как видно из определения, числа имеют чередующийся знак. Их абсолютныезначения, называемые числами Стирлинга первого рода без знака,задают количество перестановок множества, состоящего из nэлементов с k циклами, и обозначаются c(n,k) или[nk]:

c(n,k)=|s(n,k)|=(1)nks(n,k).
 Их производящей функцией является возрастающий факториал:
k=0nc(n,k)xk=x(x+1)(x+2)(x+n1)=xn¯=(x+n1)n.

Рекуррентноесоотношение


 Числа Стирлинга первого рода задаются рекуррентным соотношением:
s(0,0)=c(0,0)=1
,
s(n,0)=c(n,0)=0
, для n \textgreater 0,
s(0,k)=c(0,k)=0
, для k \textgreater 0,

 для чисел со знаком: s(n,k)=s(n1,k1)(n1)s(n1,k) для0<k<n.
 для чисел без знака: c(n,k)=c(n1,k1)+(n1)c(n1,k) для0<k<n.

Пример


 Первые ряды:
n\{k0123456
01
101
2011
30231
4061161
50245035101
6012027422585151