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

Числа Стирлинга первого рода (без знака) — количество перестановок порядка 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