WikiSort.ru - Не сортированное

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

Определение

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

${\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k},}$

где ${\displaystyle (x)_{n}}$ — символ Похгаммера (убывающий факториал):

${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}$

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения, называемые числами Стирлинга первого рода без знака, задают количество перестановок множества, состоящего из n элементов с k циклами, и обозначаются ${\displaystyle c(n,k)}$ или ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}}$ :

${\displaystyle c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k).}$

Их производящей функцией является возрастающий факториал:

${\displaystyle \sum _{k=0}^{n}c(n,k)x^{k}=x(x+1)(x+2)\cdots (x+n-1)=x^{\bar {n}}=(x+n-1)_{n}.}$

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

Числа Стирлинга первого рода задаются рекуррентным соотношением:

${\displaystyle s(0,0)=c(0,0)=1}$ ,

${\displaystyle s(n,0)=c(n,0)=0}$ , для n > 0,

${\displaystyle s(0,k)=c(0,k)=0}$ , для k > 0,

для чисел со знаком: ${\displaystyle s(n,k)=s(n-1,k-1)-(n-1)\cdot s(n-1,k)}$ для ${\displaystyle 0<k<n.}$

для чисел без знака: ${\displaystyle c(n,k)=c(n-1,k-1)+(n-1)\cdot c(n-1,k)}$ для ${\displaystyle 0<k<n.}$

Пример

Первые числа Стирлинга со знаком:

См. также

• Число Стирлинга второго рода
• Факториал
• Субфакториал

Ссылки

• Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.