제1종 스털링 수
Stirling numbers of the first kind
1. 개요
하강 계승 또는 상승 계승을 급수 표기로 나타냈을 때의 각 계수로 정의되는 수로, 제임스 스털링이 1730년에 도입하였다. 부호 없는 제1종 스털링 수 $$\begin{bmatrix} n \\ k \end{bmatrix}$$[주의]와 부호 있는 제1종 스털링 수 $$s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}$$로 나뉘며 $$0 \le k \le n \le 10$$ 범위에서[1][2] $$\begin{bmatrix} n \\ k \end{bmatrix}$$ 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 $$s(n,\,k)$$의 부호가 $$(-)$$임을 의미한다.
2. 정의
$$x$$의 $$n$$승 하강 계승 $$x^{\underline n}$$을 $$x$$의 $$n$$차식으로 나타냈을 때 $$x^k$$의 계수를 제1종 스털링 수 $$s(n,\,k)$$로 정의한다. 즉
한편, $$x$$의 $$n$$승 상승 계승 $$x^{\overline n}$$을 이용해서도 나타낼 수 있는데, 이 경우 제1종 스털링 수에 절댓값 기호가 붙는다.
$$\left| s(n,\,k) \right|$$는 종종 $$c(n,\,k)$$또는 $$\begin{bmatrix} n \\ k \end{bmatrix}$$로 나타내기도 하는데, 이를 '''부호 없는(unsigned) 제1종 스털링 수'''라고 한다.
각 하강 계승, 상승 계승을 이용한 정의식으로부터 다음과 같은 관계를 알 수 있다.
참고로 제2종 스털링 수는 $$s$$를 대문자로 쓴 $$S(n,\,k)$$이다.
$$k=0$$일 때는 상수항의 계수를 의미하며 값이 두 가지 경우로 나뉜다. $$n \ge 1$$이면 상수항이 없는 곱셈식이 되므로 $$s(n,\,0) = 0$$이지만, $$n=0$$이면 순열과의 관계로부터 $$x^{\underline 0} = {}_x {\rm P}_0 = \dfrac{x!}{x!} = 1$$이므로 편의상 $$s(0,\,0)=1$$로 정의한다. 또 부호 없는 제1종 스털링 수의 정의식에 $$x=1$$을 대입하면 다음과 같은 관계식을 유도할 수 있다.
즉, 부호 없는 제1종 스털링 수의 합은 팩토리얼과 같다.
부호 없는 제1종 스털링 수는 조합론으로도 정의할 수 있는데, 원소의 개수가 $$n$$인 집합을 구분되지 않는 $$k$$개의 순환[3]으로 분할하는 방법의 수이다.
예를 들어 $$a$$, $$b$$, $$c$$, $$d$$를 원소로 갖는 집합을 $$2$$개의 순환으로 분할해보면
$$\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & c & d \end{pmatrix}$$
$$\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & d & c \end{pmatrix}$$
$$\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & c & d \end{pmatrix}$$
$$\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & d & c \end{pmatrix}$$
$$\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b & d \end{pmatrix}$$
$$\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & d & b \end{pmatrix}$$
$$\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & b & c \end{pmatrix}$$
$$\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & c & b \end{pmatrix}$$
$$\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} c & d \end{pmatrix}$$
$$\begin{pmatrix} a & c \end{pmatrix},\,\begin{pmatrix} b & d \end{pmatrix}$$
$$\begin{pmatrix} a & d \end{pmatrix},\,\begin{pmatrix} b & c \end{pmatrix}$$
로 $$11$$가지가 얻어지며 $$\begin{bmatrix} 4 \\ 2 \end{bmatrix} = 11$$이다.
위의 두 정의가 왜 동치인지 직관적으로 와닿지 않을 수도 있는데, 각 정의를 바탕으로 점화식을 써보면 완전히 똑같은 식이 유도된다(후술).
3. 성질
3.1. 점화식
$$x$$의 $$n$$승 상승 계승식에 $$(x+n)$$을 곱해서 나타내보면 바로 위의 식이 튀어나온다.
맨 우변에 주목했을 때, $$x \cdot x^{\overline n}$$에서 $$x^{k+1}$$의 계수는 $$x^{\overline n}$$의 $$x^k$$차항 계수와 같으며 이는 $$\begin{bmatrix} n \\ k \end{bmatrix}$$에 해당한다. 제2항에서 $$x^{k+1}$$의 계수는 $$x^{\overline n}$$의 $$x^{k+1}$$차항 계수이며 이는 $$\begin{bmatrix} n \\ k+1 \end{bmatrix}$$와 같다. 맨 좌변에서 $$x^{k+1}$$의 계수는 $$\begin{bmatrix} n+1 \\ k+1 \end{bmatrix}$$이므로 정리하면 위의 식이 얻어진다.
조합론을 이용한 증명의 경우, $$n$$개 원소를 분할한 경우에서 $$(n+1)$$번째 원소를 끼워넣는 방법을 고려해서 유도할 수 있는데, $$(n+1)$$번째 원소를 길이가 $$1$$인 순환으로 남기는 방법과 다른 순환에 포함시키는 방법으로 나누어서 생각할 수 있다. 전자의 경우 $$(n+1)$$번째 원소 자체가 $$1$$개의 순환이므로 $$n$$개의 원소를 $$k$$개의 순환으로 분할한 경우의 수 $$\begin{bmatrix} n \\ k \end{bmatrix}$$가 그대로 쓰인다. 후자의 경우, $$n$$개의 원소를 $$(k+1)$$개의 순환으로 분할한 것을 대칭군 표기법으로 나열한 뒤, 각 순환의 원소에서 맨 앞, 사이 사이, 맨 뒤에 끼워넣어보면 되는데, 예를 들어 순환의 길이가 $$m$$이라고 하면 $$(n+1)$$번째 원소가 들어갈 자리의 수는 $$(m+1)$$이지만 맨 앞과 맨 뒤에 끼워넣는 경우는 같은 순환이므로 결과적으로 각 순환에서 원소 하나를 끼워넣어서 새로운 순환이 생길 경우의 수는 순환의 길이 $$m$$과 같다. 각 순환의 길이를 모두 합한 값은 원소의 총 개수 $$n$$과 같으므로 경우의 수는 $$\begin{bmatrix} n \\ k+1 \end{bmatrix}$$에 $$n$$을 곱한 값 $$n \begin{bmatrix} n \\ k+1 \end{bmatrix}$$이 된다.
또한 $$s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}$$였으므로 이를 대입해서 정리하면
3.2. 제2종 스털링 수와의 관계
- || $$\begin{bmatrix} n \\ k \end{bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix}$$ ||
두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 제2종 스털링 수에 점화식을 적용하면
이 되는데, 우변의 제2항을 이항하면
이제 각 성분을 교환하고 $$-1$$을 곱해주면 제1종 스털링 수의 점화식 꼴이 된다.
이 되는데, 우변의 제2항을 이항하면
이제 각 성분을 교환하고 $$-1$$을 곱해주면 제1종 스털링 수의 점화식 꼴이 된다.
- ||$$\displaystyle \sum_{r=k}^n s(n,\,r) S(r,\,k) = \sum_{r=k}^n S(n,\,r) s(r,\,k) = \delta_{n\,k}$$ ||
$$\delta_{n,\,k}$$는 크로네커 델타이다. 두 식 모두 라흐 수의 정의처럼 각 스털링 수의 정의를 연달아 적용함으로써 도출된다.
부호 없는 스털링 수, 그러니까 $$s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}$$표기를 이용하면 다음과 같이 된다.
두 식에서 우변의 $$-1$$의 지수가 다르지만 사실 둘 다 $$(-1)^n$$을 쓰든 $$(-1)^k$$를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 $$\delta_{n,\,k} = 1$$, 즉 $$n=k$$일 때 뿐이며, 좌변에서 $$n=k$$란 곧 $$(-1)^k \begin{bmatrix} k \\ k \end{bmatrix} \begin{Bmatrix} k \\ k \end{Bmatrix} = (-1)^k = (-1)^n$$을 의미하기 때문이다.
부호 없는 스털링 수, 그러니까 $$s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}$$표기를 이용하면 다음과 같이 된다.
두 식에서 우변의 $$-1$$의 지수가 다르지만 사실 둘 다 $$(-1)^n$$을 쓰든 $$(-1)^k$$를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 $$\delta_{n,\,k} = 1$$, 즉 $$n=k$$일 때 뿐이며, 좌변에서 $$n=k$$란 곧 $$(-1)^k \begin{bmatrix} k \\ k \end{bmatrix} \begin{Bmatrix} k \\ k \end{Bmatrix} = (-1)^k = (-1)^n$$을 의미하기 때문이다.
3.3. 생성함수
제1종 스털링 수 특성상 $$n<k$$이면 $$s(n,\,k) = \begin{bmatrix} n \\ k \end{bmatrix} = 0$$이므로 아래와 같이 축약된 식으로 많이 나타낸다.
증명에는 이항급수 $$\displaystyle (1+x)^r = \sum_{n=0}^\infty \binom rn x^n $$을 이용한다. 테일러 급수의 예에 설명되어있듯이 이항급수에서 조합 기호는 $$\displaystyle \binom rn = \frac 1{n!} \prod_{i=0}^{n-1}(r-i)$$로 재정의되고 하강 계승의 정의에 따라 $$\displaystyle \prod_{i=0}^{n-1}(r-i) = r^{\underline n}$$이므로 이항급수는 다음과 같이 고쳐 쓸 수 있다.
위 유도 과정에서 $$r$$에 $$-r$$을, $$x$$에 $$-x$$를 대입하면 다음과 같이 부호 없는 제1종 스털링 수의 생성함수로 바뀐다.
4. 관련 문서
[주의] 벡터나 행렬과 혼동할 수 있기 때문에 사전에 이것이 부호 없는 제1종 스털링 수임을 알려주어야 한다.[1] 제2종 스털링 수와의 관계식에서 알 수 있듯이 $$n \ge k$$만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제1종 스털링 수가 아니라 제2종 스털링 수지만……[2] $$n<k$$이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.[3] 방향이 있는 원순열이다. 1 → 2 → 3 → 4 → 1과 1 → 4 → 3 → 2 → 1은 같은 원순열이지만 다른 순환이다. 대칭군의 표기법으로 나타내면 전자는 $$\begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix}$$이고 후자는 $$\begin{pmatrix} 1 & 4 & 3 & 2 \end{pmatrix}$$로 극명하게 다르다는 것을 알 수 있다.