Русская Википедия:Числа Стирлинга первого рода

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

<math>(x)_{n} = \sum_{k=0}^n s(n,k) x^k,</math>

где <math>(x)_n</math> — символ Похгаммера (убывающий факториал):

<math>(x)_{n}=x(x-1)(x-2)\cdots(x-n+1).</math>

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

<math>c(n,k) = |s(n,k)| = (-1)^{n-k} s(n,k).</math>

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

<math>\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.</math>

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

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

<math> s(0, 0) = c(0,0) = 1 </math>,

<math> s(n, 0) = c(n,0) = 0 </math>, для n > 0,

<math> s(0, k) = c(0,k) = 0 </math>, для k > 0,

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

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

Доказательство

Для n=1 это равенство проверяется непосредственно. Пусть перестановка (n-1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки различны и содержат k циклов, их количество (n-1)·s(n-1, k). Из любой перестановки (n-1)-го порядка, содержащей k-1 цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n-го порядка, содержащие k циклов. Тем самым равенство доказано.

Пример

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

n\k	0	1	2	3	4	5	6
0	1
1	0	1
2	0	−1	1
3	0	2	−3	1
4	0	−6	11	−6	1
5	0	24	−50	35	−10	1
6	0	−120	274	−225	85	−15	1

См. также

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

Ссылки

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