제1종 스털링 수란?
부호가 있는 제1종 스털링 수는 \(s(n,k)\)로 표기하며, 하강계승(falling factorial) \(x(x-1)(x-2)\dots(x-n+1)\)을 \(x\)의 일반 거듭제곱 형태로 전개했을 때 나타나는 계수입니다. 이 값의 절댓값 \(c(n,k) = |s(n,k)|\)는 n개의 원소를 정확히 k개의 서로소인 순환(cycle)으로 분해하는 순열의 개수를 셉니다. 두 값은 부호 규칙 \(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\cdot s(n,k)$$를 이용해 작은 동적 계획법(DP) 표를 만듭니다. 초기 조건은 \(s(0,0)=1\)이며, \(n>0\)일 때 \(s(n,0)=0\), \(k>0\)일 때 \(s(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)|\).
한 행에서 부호 없는 값들의 합은 얼마인가요? 모든 k에 대한 \(c(n,k)\)의 합은 \(n!\)(n 팩토리얼)과 같습니다.
