스털링 수

1. 개요

스털링 수 Stirling numbers
제2종 $S(n,k)$	$n$ 개 원소를 비어 있지 않은 $k$ 개 묶음으로 나누는 방법 수
제1종 $c(n,k)$	$n$ 개 원소의 순열 중 사이클이 정확히 $k$ 개인 것의 수
부호 있는 제1종	$s(n,k) = (-1)^{n-k}c(n,k)$
기저 변환	$x^n = \sum_k S(n,k)\,x^{\underline k}$, $x^{\underline n} = \sum_k s(n,k)\,x^k$
행 합	$\sum_k S(n,k)$ = 벨 수, $\sum_k c(n,k) = n!$
이름	제임스 스털링, 『미분법』(Methodus Differentialis, 1730)

거듭제곱 $x^n$ 과 내림 거듭제곱 $x(x-1)\cdots(x-n+1)$ 사이를 오가는 환율표. 한쪽 방향은 안전하고, 반대 방향은 부호가 엇갈려 수치적으로 위험하다.

스털링 수(Stirling numbers)는 두 종류의 정수 삼각형이다. 제2종 스털링 수 $S(n, k)$ 는 원소 $n$ 개짜리 집합을 비어 있지 않은 $k$ 개의 부분집합으로 나누는 방법의 수이고, 제1종 스털링 수 $c(n, k)$ (부호 없는 판)는 $n$ 개 원소의 순열 가운데 사이클이 정확히 $k$ 개인 것의 수다. 표기가 문헌마다 갈려서 크누스 계열은 $\left\{ n \atop k \right\}$ 와 $\left[ n \atop k \right]$ 를 쓰고, DLMF·수치 라이브러리는 부호 있는 $s(n, k)$ 와 $S(n, k)$ 를 쓴다. 이 문서는 후자를 따른다.¹

조합론의 개수 세기로 소개되지만, 계산 쪽에서 스털링 수가 하는 일은 두 다항식 기저 사이의 변환 행렬이다. 단항식 $x^k$ 와 내림 거듭제곱(falling factorial) $x^{\underline k} = x(x-1)\cdots(x-k+1)$ 은 차분 연산에서 각각 미분의 $x^k$ 에 해당하는 역할을 한다. 그래서 합 공식(파울하버 공식), 유한차분, 이산 분포의 적률이 모두 이 표를 거친다. 이름은 1730년 『미분법』에서 이 계수들을 표로 낸 제임스 스털링에서 왔다 — 팩토리얼 근사 「스털링 공식」의 그 스털링이지만, 두 결과는 직접 관계가 없다.²

2. 정의와 점화식

작은 값부터 보자.

$n$	$S(n,1..n)$	벨 수 $B_n$	$s(n,1..n)$
1	1	1	1
2	1, 1	2	−1, 1
3	1, 3, 1	5	2, −3, 1
4	1, 7, 6, 1	15	−6, 11, −6, 1
5	1, 15, 25, 10, 1	52	24, −50, 35, −10, 1

두 삼각형 모두 「마지막 원소를 어디에 넣는가」로 점화식이 나온다.

$$S(n, k) = k\,S(n-1, k) + S(n-1, k-1),\qquad c(n, k) = (n-1)\,c(n-1, k) + c(n-1, k-1)$$

제2종에서 $n$ 번째 원소는 기존 $k$ 개 묶음 중 하나에 들어가거나($k$ 가지) 혼자 새 묶음을 만든다. 제1종에서는 기존 사이클의 $n-1$ 개 원소 중 하나 뒤에 끼어들거나 혼자 고정점 사이클을 만든다. 경계는 $S(0,0) = c(0,0) = 1$, $n \ge 1$ 이면 $S(n, 0) = c(n, 0) = 0$.

행 합: $\sum_k c(n, k) = n!$ (모든 순열), $\sum_k S(n, k) = B_n$ (벨 수, 집합 분할의 총수 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …). 닫힌 꼴로는

$$S(n, k) = \frac{1}{k!}\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}i^n$$

가 있다(포함-배제). 다만 이 교대합은 아래에서 보듯 부동소수점으로 계산하면 안 된다.

3. 기저 변환 — 안전한 방향과 위험한 방향

두 삼각형은 서로 역행렬이다.

$$x^n = \sum_{k=0}^n S(n,k)\,x^{\underline k},\qquad x^{\underline n} = \sum_{k=0}^n s(n,k)\,x^k$$

예컨대 $x^3 = x^{\underline 3} + 3x^{\underline 2} + x^{\underline 1}$ 이고 $x^{\underline 5} = x^5 - 10x^4 + 35x^3 - 50x^2 + 24x$ 다.

왜 내림 거듭제곱인가. 전진 차분 $\Delta f(x) = f(x+1) - f(x)$ 에 대해 $\Delta x^{\underline k} = k\,x^{\underline{k-1}}$ 이 성립해서, 미분에서 $x^k$ 가 하는 일을 차분에서는 $x^{\underline k}$ 가 한다. 그래서 「단항식으로 주어진 것을 차분·합 하고 싶으면 $S$ 로 내림 거듭제곱 기저로 옮기고, 거기서 연산한 뒤 $s$ 로 돌아온다」가 이산 미적분의 기본 패턴이다. 같은 이유로 $\Delta^k x^n\big|_{x=0} = k!\,S(n,k)$ 이다(예: $\Delta^3 x^5|_0 = 150 = 3!\cdot25$). 유한차분법의 고차 차분 계수, 그레고리-뉴턴 전진 차분 보간의 계수가 이 관계로 단항식 계수와 이어진다.

두 방향은 수치적으로 전혀 다르다. $S(n,k)$ 는 전부 양수라 $x \ge n-1$ 처럼 $x^{\underline k}$ 들이 모두 양수인 영역에서 $\sum S(n,k)\,x^{\underline k}$ 는 상쇄가 전혀 없고, 그 밖에서도 큰 항들은 같은 부호라 상쇄가 약하다. 반면 $s(n,k)$ 는 부호가 번갈아 나오고 크기가 엄청나다. $n = 20$ 에서 $\max_k S(20,k) = S(20,8) \approx 1.5\times10^{13}$ 인 데 비해 $\max_k|s(20,k)| = |s(20,3)| \approx 6.7\times10^{17}$ 이다. 배정밀도로 재면:

• $x^{20}$ 을 $\sum_k S(20,k)\,(10.5)^{\underline k}$ 로 계산 → 상대오차 $1.2\times10^{-16}$.
• $(10.5)^{\underline{20}} = -4.5184\times10^{11}$ 을 $\sum_k s(20,k)\,(10.5)^k$ 로 계산 → $-4.5247\times10^{11}$, 상대오차 $1.4\times10^{-3}$.

뒤쪽은 크기 $10^{25}$ 쯤의 항들이 소거해 $10^{11}$ 이 남는 구조라 유효숫자 열세 자리가 날아간다.³ 호너 방법 문서의 「단항식 계수로 적은 순간 조건수가 폭발한다」와 같은 현상이다. 내림 거듭제곱 값이 필요하면 곱 $x(x-1)\cdots$ 을 직접 하라. 위 교대합 공식의 $S(n,k)$ 계산도 같은 이유로 정수 산술이나 점화식으로 한다.

4. 확률에서 — 적률과 점유 문제

포아송 적률. $N \sim \mathrm{Poisson}(\lambda)$ 의 팩토리얼 적률은 $\mathbb E[N^{\underline k}] = \lambda^k$ 로 아주 단순하다. 그래서 보통 적률은

$$\mathbb E[N^n] = \sum_{k} S(n,k)\,\lambda^k$$

이다(투샤르 다항식). $\lambda = 2$ 에서 $\mathbb E[N^4] = 2 + 7\cdot4 + 6\cdot8 + 16 = 94$ 이고, 확률질량을 직접 더한 값과 일치한다. $\lambda = 1$ 이면 $\mathbb E[N^n] = B_n$ — 평균 1 인 포아송 분포의 $n$ 차 적률이 벨 수라는 도빈스키 공식이다.

이항 적률. 마찬가지로 $\mathbb E[X^{\underline k}] = n^{\underline k}p^k$ 라 $\mathbb E[X^3] = \sum_k S(3,k)\,n^{\underline k}p^k$. $n = 10$, $p = 0.3$ 이면 $3 + 3\cdot8.1 + 19.44 = 46.74$ 이고 직접 합과 같다(이항 분포).

점유 문제. 공 $n$ 개를 상자 $m$ 개에 독립 균등하게 던질 때 정확히 $k$ 개 상자가 차는 확률은

$$P(K = k) = \binom{m}{k}\frac{k!\,S(n,k)}{m^n}$$

이다. $k!\,S(n,k)$ 가 「$n$ 개를 $k$ 개 상자에 빈 상자 없이 넣는」 전사 함수의 개수이기 때문이다. $n = m = 10$ 이면 모든 상자가 차는 확률은 $10!/10^{10} = 3.6\times10^{-4}$ 이고, 차는 상자 수 기댓값은 분포를 다 더해 $6.5132$ 로 공식 $m(1-(1-1/m)^n)$ 과 일치한다. 해시 테이블의 버킷 점유, 쿠폰 수집 문제, 몬테카를로 방법의 층화 표본에서 빈 층이 생길 확률이 이 분포다.

5. 크기와 점근

$S(n,k)$ 는 고정 $k$ 에서 $S(n,k) \sim k^n/k!$ 이다($n\to\infty$). 행 안의 최댓값 위치는 대략 $n/\ln n$ 근처로 천천히 움직인다($n = 20$ 에서 $k = 8$). 벨 수는 $\ln B_n \sim n\ln n - n\ln\ln n - n$ 정도로 팩토리얼보다 조금 느리게 자라 $B_{20} \approx 5.2\times10^{13}$ 이다. $c(n, k)$ 의 행은 $\sum_k c(n,k)x^k = x(x+1)\cdots(x+n-1)$ 의 계수라, 무작위 순열의 사이클 수가 평균 $H_n \approx \ln n$ 근처에 몰리는 분포를 이룬다. 큰 $n$ 에서 값 하나가 필요하면 점화식을 로그 공간으로 돌리거나, 안장점 근사(테마·모저-와이먼 근사)를 쓴다.

6. 관련 문서

• 파울하버 공식 · 베르누이 수 · 호너 방법 · 유한차분법 · 보간과 근사
• 포아송 분포 · 이항 분포 · 감마 함수 · 몬테카를로 방법
• 벨 수 · 생성함수 · 뉴턴 보간 · 오일러 수

7. Footnotes

1. 표기 전쟁이 치열하다. $s(n,k)$ 가 부호 있는 판인지 없는 판인지, $S$ 가 대문자인지 필기체인지 책마다 다르다. 크누스는 중괄호판을 「$n$ subset $k$」, 대괄호판을 「$n$ cycle $k$」로 읽자며 표기 통일을 시도했지만, 결과적으로 표기가 하나 더 늘었다는 게 학계의 국룰. ↩

2. 스털링 공식 $n! \approx \sqrt{2\pi n}(n/e)^n$ 도 사실 상수 $\sqrt{2\pi}$ 를 붙인 게 스털링이고 나머지는 드무아브르가 먼저 했다. 이름 붙이는 운이 좋은 사람은 두 번 좋다. ↩

3. 컴퓨터 대수 시스템이 내림 거듭제곱을 단항식으로 「친절하게」 펼쳐 준 결과를 C 코드로 내보내면 정확히 이 사고가 난다. 기호 계산은 정확했고, 부동소수점이 나머지를 망쳤다. 펼치기 전 곱 형태를 그대로 코드로 옮기는 것이 정답. ↩