Изменения

Перейти к: навигация, поиск

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

1 байт добавлено, 15:28, 14 января 2013
Рекуррентное соотношение
:<tex dpi="130"> s(0, k) = 0 </tex>, для <tex dpi="130">k > 0</tex>.
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <tex dpi="130">n</tex> элементов в виде <tex dpi="130">k</tex> циклов либо помещает последний элемент(<tex dpi="130">n-</tex>ый) в отдельный цикл <tex dpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <tex dpi="130">s(n-1, k)</tex> циклических представлений первых <tex dpi="130">(n-1)</tex> элементов. В последнем случае существует <tex dpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>(1;2;3)</tex> можно получить только 3 разных цикла: <tex dpi="130">(1;2;3;4), (1;2;4;3), (1;4;2;3)</tex>. Таким образом, рекуррентность имеет вид:
:<tex dpi="130">s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)</tex>
Анонимный участник

Навигация