Что такое число Стирлинга первого рода?
Знаковые числа Стирлинга первого рода, которые обозначают как \(s(n,k)\), — это коэффициенты, возникающие при разложении убывающего факториала \(x(x-1)(x-2)\dots(x-n+1)\) по обычным степеням \(x\). Их абсолютные значения \(c(n,k) = |s(n,k)|\) показывают, сколько перестановок из \(n\) элементов раскладываются ровно на \(k\) непересекающихся циклов. Связь между ними задаётся правилом знака \(s(n,k) = (-1)^{n-k} c(n,k)\). Этот калькулятор возвращает именно знаковое значение — то, что соответствует коэффициентам убывающего факториала.
Как пользоваться калькулятором
Введите два целых неотрицательных числа: \(n\) (параметр размера) и \(k\) (число циклов, оно же — индекс степени). Нажмите «Вычислить», и калькулятор выдаст \(s(n,k)\). Если \(k\) больше \(n\), результат равен 0; значение \(s(n,n)\) всегда равно 1; а \(s(0,0)\) по определению равно 1.
Разбор формулы
Калькулятор строит небольшую таблицу методом динамического программирования по рекуррентной формуле $$s(n+1,k) = s(n,k-1) - n\, s(n,k)$$ начиная с \(s(0,0)=1\), где \(s(n,0)=0\) при \(n>0\) и \(s(0,k)=0\) при \(k>0\). Каждая новая строка вычисляется из предыдущей, поэтому хранить громоздкую таблицу не нужно. Именно отрицательное слагаемое в рекуррентной формуле и порождает чередующиеся знаки.
Пример с решением
Вычислим \(s(5,2)\). Беззнаковые числа циклов для строки 5 таковы: \(c(5,1)=24\), \(c(5,2)=50\), \(c(5,3)=35\), \(c(5,4)=10\), \(c(5,5)=1\). Знак равен \((-1)^{5-2} = -1\), поэтому \(s(5,2) = -50\). Проверим: $$x(x-1)(x-2)(x-3)(x-4) = x^5 - 10x^4 + 35x^3 - 50x^2 + 24x$$ и коэффициент при \(x^2\) действительно равен \(-50\).
Частые вопросы
Почему результат может быть отрицательным? Потому что это знаковая версия: коэффициент при \(x^k\) в убывающем факториале меняет знак по правилу \((-1)^{n-k}\).
Как получить беззнаковое число циклов? Возьмите абсолютное значение: \(c(n,k) = |s(n,k)|\).
Чему равна сумма беззнаковых значений по строке? Сумма \(c(n,k)\) по всем \(k\) равна \(n!\) (n факториал).
