Четверг, 10.07.2025, 11:33
Приветствую Вас Гость | RSS

Специальные числа

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

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

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

 
Определение

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

(x)_{n} = \sum_{k=0}^n s(n,k) x^k,

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

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

Как видно из определения, числа имеют чередующийся знак. Их абсолютные значения задают количество перестановок множества, состоящего из n элементов с циклами.

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

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

 s(n, n) = 1 , для n ≥ 0,
 s(n, 0) = 0 , для n > 0,
 s(n, k) = s(n-1, k-1) - (n-1) \cdot s(n-1, k)  для 0 < k < n.
Доказательство.

Для 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

 

Вход на сайт
Поиск

Разработчики сайта: Иушина Анастасия, Михиенко Дарья. Красноярск, ИМФИ, 2025
Конструктор сайтовuCoz