1. 개요
하강 계승 또는 상승 계승을 급수 표기로 나타냈을 때의 각 계수로 정의되는 수로, 제임스 스털링이 1730년에 도입하였다. 부호 없는 제1종 스털링 수 [math(begin{bmatrix} n \ k end{bmatrix})][주의]와 부호 있는 제1종 스털링 수 [math(s(n,,k) = (-1)^{n-k} begin{bmatrix} n \ k end{bmatrix})]로 나뉘며 [math(0 le k le n le 10)] 범위에서[2]만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제1종 스털링 수가 아니라 제2종 스털링 수지만……][3]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.] [math(begin{bmatrix} n \ k end{bmatrix})] 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 [math(s(n,,k))]의 부호가 [math((-))]임을 의미한다.
[math(n Bigbackslash k)]
| [math(0)]
| [math(1)]
| [math(2)]
| [math(3)]
| [math(4)]
| [math(5)]
| [math(6)]
| [math(7)]
| [math(8)]
| [math(9)]
| [math(10)]
|
[math(0)]
| [math(1)]
| [math(0)]
| |||||||||
[math(1)]
| [math(0)]
| [math(1)]
| [math(0)]
| ||||||||
[math(2)]
| [math(1)]
| [math(1)]
| [math(0)]
| ||||||||
[math(3)]
| [math(2)]
| [math(3)]
| [math(1)]
| [math(0)]
| |||||||
[math(4)]
| [math(6)]
| [math(11)]
| [math(6)]
| [math(1)]
| [math(0)]
| ||||||
[math(5)]
| [math(24)]
| [math(50)]
| [math(35)]
| [math(10)]
| [math(1)]
| [math(0)]
| |||||
[math(6)]
| [math(120)]
| [math(274)]
| [math(225)]
| [math(85)]
| [math(15)]
| [math(1)]
| [math(0)]
| ||||
[math(7)]
| [math(720)]
| [math(1764)]
| [math(1624)]
| [math(735)]
| [math(175)]
| [math(21)]
| [math(1)]
| [math(0)]
| |||
[math(8)]
| [math(5040)]
| [math(13068)]
| [math(13132)]
| [math(6769)]
| [math(1960)]
| [math(322)]
| [math(28)]
| [math(1)]
| [math(0)]
| ||
[math(9)]
| [math(40320)]
| [math(109584)]
| [math(118124)]
| [math(67284)]
| [math(22449)]
| [math(4536)]
| [math(546)]
| [math(36)]
| [math(1)]
| [math(0)]
| |
[math(10)]
| [math(403200)]
| [math(1026576)]
| [math(1172700)]
| [math(723680)]
| [math(269325)]
| [math(63273)]
| [math(9450)]
| [math(870)]
| [math(45)]
| [math(1)]
| |
2. 정의
[math(x)]의 [math(n)]승 하강 계승 [math(x^{underline n})]을 [math(x)]의 [math(n)]차식으로 나타냈을 때 [math(x^k)]의 계수를 제1종 스털링 수 [math(s(n,,k))]로 정의한다. 즉
[math(displaystyle x^{underline n} = prod _{k=0}^{n-1}(x-k) = x(x-1)(x-2) cdotscdots(x-n+1) = sum_{k=0}^n s(n,,k) x^k)]
|
한편, [math(x)]의 [math(n)]승 상승 계승 [math(x^{overline n})]을 이용해서도 나타낼 수 있는데, 이 경우 제1종 스털링 수에 절댓값 기호가 붙는다.
[math(displaystyle x^{overline n} = prod_{k=0}^{n-1}(x+k) = x(x+1)(x+2) cdotscdots(x+n-1) = sum_{k=0}^n left| s(n,,k) right| x^k)]
|
[math(left| s(n,,k) right|)]는 종종 [math(c(n,,k))]또는 [math(begin{bmatrix} n \ k end{bmatrix})]로 나타내기도 하는데, 이를 부호 없는(unsigned) 제1종 스털링 수라고 한다.
각 하강 계승, 상승 계승을 이용한 정의식으로부터 다음과 같은 관계를 알 수 있다.
각 하강 계승, 상승 계승을 이용한 정의식으로부터 다음과 같은 관계를 알 수 있다.
[math(s(n,,k) = (-1)^{n-k} c(n,,k) = (-1)^{n-k} begin{bmatrix} n \ k end{bmatrix})]
|
참고로 제2종 스털링 수는 [math(s)]를 대문자로 쓴 [math(S(n,,k))]이다.
[math(k=0)]일 때는 상수항의 계수를 의미하며 값이 두 가지 경우로 나뉜다. [math(n ge 1)]이면 상수항이 없는 곱셈식이 되므로 [math(s(n,,0) = 0)]이지만, [math(n=0)]이면 순열과의 관계로부터 [math(x^{underline 0} = {}_x {rm P}_0 = dfrac{x!}{x!} = 1)]이므로 편의상 [math(s(0,,0)=1)]로 정의한다. 또 부호 없는 제1종 스털링 수의 정의식에 [math(x=1)]을 대입하면 다음과 같은 관계식을 유도할 수 있다.
[math(k=0)]일 때는 상수항의 계수를 의미하며 값이 두 가지 경우로 나뉜다. [math(n ge 1)]이면 상수항이 없는 곱셈식이 되므로 [math(s(n,,0) = 0)]이지만, [math(n=0)]이면 순열과의 관계로부터 [math(x^{underline 0} = {}_x {rm P}_0 = dfrac{x!}{x!} = 1)]이므로 편의상 [math(s(0,,0)=1)]로 정의한다. 또 부호 없는 제1종 스털링 수의 정의식에 [math(x=1)]을 대입하면 다음과 같은 관계식을 유도할 수 있다.
[math(displaystyle 1^{overline n} = prod_{k=1}^n k = n! = sum_{k=0}^n begin{bmatrix} n \ k end{bmatrix})]
|
즉, 부호 없는 제1종 스털링 수의 합은 팩토리얼과 같다.
부호 없는 제1종 스털링 수는 조합론으로도 정의할 수 있는데, 원소의 개수가 [math(n)]인 집합을 구분되지 않는 [math(k)]개의 순환[4]이고 후자는 [math(begin{pmatrix} 1 & 4 & 3 & 2 end{pmatrix})]로 극명하게 다르다는 것을 알 수 있다.]으로 분할하는 방법의 수이다.
예를 들어 [math(a)], [math(b)], [math(c)], [math(d)]를 원소로 갖는 집합을 [math(2)]개의 순환으로 분할해보면
[math(begin{pmatrix} a end{pmatrix},,begin{pmatrix} b & c & d end{pmatrix})]
[math(begin{pmatrix} a end{pmatrix},,begin{pmatrix} b & d & c end{pmatrix})]
[math(begin{pmatrix} b end{pmatrix},,begin{pmatrix} a & c & d end{pmatrix})]
[math(begin{pmatrix} b end{pmatrix},,begin{pmatrix} a & d & c end{pmatrix})]
[math(begin{pmatrix} c end{pmatrix},,begin{pmatrix} a & b & d end{pmatrix})]
[math(begin{pmatrix} c end{pmatrix},,begin{pmatrix} a & d & b end{pmatrix})]
[math(begin{pmatrix} d end{pmatrix},,begin{pmatrix} a & b & c end{pmatrix})]
[math(begin{pmatrix} d end{pmatrix},,begin{pmatrix} a & c & b end{pmatrix})]
[math(begin{pmatrix} a & b end{pmatrix},,begin{pmatrix} c & d end{pmatrix})]
[math(begin{pmatrix} a & c end{pmatrix},,begin{pmatrix} b & d end{pmatrix})]
[math(begin{pmatrix} a & d end{pmatrix},,begin{pmatrix} b & c end{pmatrix})]
로 [math(11)]가지가 얻어지며 [math(begin{bmatrix} 4 \ 2 end{bmatrix} = 11)]이다.
위의 두 정의가 왜 동치인지 직관적으로 와닿지 않을 수도 있는데, 각 정의를 바탕으로 점화식을 써보면 완전히 똑같은 식이 유도된다(후술).
부호 없는 제1종 스털링 수는 조합론으로도 정의할 수 있는데, 원소의 개수가 [math(n)]인 집합을 구분되지 않는 [math(k)]개의 순환[4]이고 후자는 [math(begin{pmatrix} 1 & 4 & 3 & 2 end{pmatrix})]로 극명하게 다르다는 것을 알 수 있다.]으로 분할하는 방법의 수이다.
예를 들어 [math(a)], [math(b)], [math(c)], [math(d)]를 원소로 갖는 집합을 [math(2)]개의 순환으로 분할해보면
[math(begin{pmatrix} a end{pmatrix},,begin{pmatrix} b & c & d end{pmatrix})]
[math(begin{pmatrix} a end{pmatrix},,begin{pmatrix} b & d & c end{pmatrix})]
[math(begin{pmatrix} b end{pmatrix},,begin{pmatrix} a & c & d end{pmatrix})]
[math(begin{pmatrix} b end{pmatrix},,begin{pmatrix} a & d & c end{pmatrix})]
[math(begin{pmatrix} c end{pmatrix},,begin{pmatrix} a & b & d end{pmatrix})]
[math(begin{pmatrix} c end{pmatrix},,begin{pmatrix} a & d & b end{pmatrix})]
[math(begin{pmatrix} d end{pmatrix},,begin{pmatrix} a & b & c end{pmatrix})]
[math(begin{pmatrix} d end{pmatrix},,begin{pmatrix} a & c & b end{pmatrix})]
[math(begin{pmatrix} a & b end{pmatrix},,begin{pmatrix} c & d end{pmatrix})]
[math(begin{pmatrix} a & c end{pmatrix},,begin{pmatrix} b & d end{pmatrix})]
[math(begin{pmatrix} a & d end{pmatrix},,begin{pmatrix} b & c end{pmatrix})]
로 [math(11)]가지가 얻어지며 [math(begin{bmatrix} 4 \ 2 end{bmatrix} = 11)]이다.
위의 두 정의가 왜 동치인지 직관적으로 와닿지 않을 수도 있는데, 각 정의를 바탕으로 점화식을 써보면 완전히 똑같은 식이 유도된다(후술).
3. 성질
3.1. 점화식
[math(begin{bmatrix} n+1 \ k+1 end{bmatrix} = begin{bmatrix} n \ k end{bmatrix} + n begin{bmatrix} n \ k+1 end{bmatrix})]
|
[math(x)]의 [math(n)]승 상승 계승식에 [math((x+n))]을 곱해서 나타내보면 바로 위의 식이 튀어나온다.
[math(displaystyle x^{overline{n+1}} = prod_{k=0}^n(x+k) = (x+n)prod _{k=0}^{n-1}(x+k) = (x+n) x^{overline n} = x cdot x^{overline n} + n cdot x^{overline n})]
|
맨 우변에 주목했을 때, [math(x cdot x^{overline n})]에서 [math(x^{k+1})]의 계수는 [math(x^{overline n})]의 [math(x^k)]차항 계수와 같으며 이는 [math(begin{bmatrix} n \ k end{bmatrix})]에 해당한다. 제2항에서 [math(x^{k+1})]의 계수는 [math(x^{overline n})]의 [math(x^{k+1})]차항 계수이며 이는 [math(begin{bmatrix} n \ k+1 end{bmatrix})]와 같다. 맨 좌변에서 [math(x^{k+1})]의 계수는 [math(begin{bmatrix} n+1 \ k+1 end{bmatrix})]이므로 정리하면 위의 식이 얻어진다.
조합론을 이용한 증명의 경우, [math(n)]개 원소를 분할한 경우에서 [math((n+1))]번째 원소를 끼워넣는 방법을 고려해서 유도할 수 있는데, [math((n+1))]번째 원소를 길이가 [math(1)]인 순환으로 남기는 방법과 다른 순환에 포함시키는 방법으로 나누어서 생각할 수 있다. 전자의 경우 [math((n+1))]번째 원소 자체가 [math(1)]개의 순환이므로 [math(n)]개의 원소를 [math(k)]개의 순환으로 분할한 경우의 수 [math(begin{bmatrix} n \ k end{bmatrix})]가 그대로 쓰인다. 후자의 경우, [math(n)]개의 원소를 [math((k+1))]개의 순환으로 분할한 것을 대칭군 표기법으로 나열한 뒤, 각 순환의 원소에서 맨 앞, 사이 사이, 맨 뒤에 끼워넣어보면 되는데, 예를 들어 순환의 길이가 [math(m)]이라고 하면 [math((n+1))]번째 원소가 들어갈 자리의 수는 [math((m+1))]이지만 맨 앞과 맨 뒤에 끼워넣는 경우는 같은 순환이므로 결과적으로 각 순환에서 원소 하나를 끼워넣어서 새로운 순환이 생길 경우의 수는 순환의 길이 [math(m)]과 같다. 각 순환의 길이를 모두 합한 값은 원소의 총 개수 [math(n)]과 같으므로 경우의 수는 [math(begin{bmatrix} n \ k+1 end{bmatrix})]에 [math(n)]을 곱한 값 [math(n begin{bmatrix} n \ k+1 end{bmatrix})]이 된다.
또한 [math(s(n,,k) = (-1)^{n-k} begin{bmatrix} n \ k end{bmatrix})]였으므로 이를 대입해서 정리하면
조합론을 이용한 증명의 경우, [math(n)]개 원소를 분할한 경우에서 [math((n+1))]번째 원소를 끼워넣는 방법을 고려해서 유도할 수 있는데, [math((n+1))]번째 원소를 길이가 [math(1)]인 순환으로 남기는 방법과 다른 순환에 포함시키는 방법으로 나누어서 생각할 수 있다. 전자의 경우 [math((n+1))]번째 원소 자체가 [math(1)]개의 순환이므로 [math(n)]개의 원소를 [math(k)]개의 순환으로 분할한 경우의 수 [math(begin{bmatrix} n \ k end{bmatrix})]가 그대로 쓰인다. 후자의 경우, [math(n)]개의 원소를 [math((k+1))]개의 순환으로 분할한 것을 대칭군 표기법으로 나열한 뒤, 각 순환의 원소에서 맨 앞, 사이 사이, 맨 뒤에 끼워넣어보면 되는데, 예를 들어 순환의 길이가 [math(m)]이라고 하면 [math((n+1))]번째 원소가 들어갈 자리의 수는 [math((m+1))]이지만 맨 앞과 맨 뒤에 끼워넣는 경우는 같은 순환이므로 결과적으로 각 순환에서 원소 하나를 끼워넣어서 새로운 순환이 생길 경우의 수는 순환의 길이 [math(m)]과 같다. 각 순환의 길이를 모두 합한 값은 원소의 총 개수 [math(n)]과 같으므로 경우의 수는 [math(begin{bmatrix} n \ k+1 end{bmatrix})]에 [math(n)]을 곱한 값 [math(n begin{bmatrix} n \ k+1 end{bmatrix})]이 된다.
또한 [math(s(n,,k) = (-1)^{n-k} begin{bmatrix} n \ k end{bmatrix})]였으므로 이를 대입해서 정리하면
[math(s(n+1,,k+1) = s(n,,k) - n s(n,,k+1))]
|
3.2. 제2종 스털링 수와의 관계
- [math(begin{bmatrix} n \ k end{bmatrix} = begin{Bmatrix} -k \ -n end{Bmatrix})]두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 제2종 스털링 수에 점화식을 적용하면[math(begin{Bmatrix} -k \ -n end{Bmatrix} = begin{Bmatrix} -k-1 \ -n-1 end{Bmatrix} - n begin{Bmatrix} -k-1 \ -n end{Bmatrix})]이 되는데, 우변의 제2항을 이항하면[math(begin{Bmatrix} -k-1 \ -n-1 end{Bmatrix} = begin{Bmatrix} -k \ -n end{Bmatrix} + n begin{Bmatrix} -k-1 \ -n end{Bmatrix})]이제 각 성분을 교환하고 [math(-1)]을 곱해주면 제1종 스털링 수의 점화식 꼴이 된다.[math(begin{bmatrix} n+1 \ k+1 end{bmatrix} = begin{bmatrix} n \ k end{bmatrix} + n begin{bmatrix} n \ k+1 end{bmatrix})]
- [math(displaystyle sum_{r=k}^n s(n,,r) S(r,,k) = sum_{r=k}^n S(n,,r) s(r,,k) = delta_{n,k})][math(displaystyle begin{aligned} x^{underline n} &= sum_{r=0}^n s(n,,r) x^r = sum_{r=0}^n s(n,,r) sum_{k=0}^r S(r,,k) x^{underline k} = sum_{r=0}^n sum_{k=0}^r s(n,,r) S(r,,k) x^{underline k} \ &= sum_{k=0}^n sum_{r=0}^n s(n,,r) S(r,,k) x^{underline k} = sum_{k=0}^n left( sum_{r=0}^n s(n,,r) S(r,,k) right) x^{underline k} end{aligned} \ therefore sum_{r=0}^n s(n,,r) S(r,,k) = sum_{r=k}^n s(n,,r) S(r,,k) = delta_{n,,k} \ begin{aligned} x^n &= sum_{r=0}^n S(n,,r) x^{underline r} = sum_{r=0}^n S(n,,r) sum_{k=0}^r s(r,,k) x^k = sum_{r=0}^n sum_{k=0}^r S(n,,r) s(r,,k) x^k \ &= sum_{k=0}^n sum_{r=0}^n S(n,,r) s(r,,k) x^k = sum_{k=0}^n left( sum_{r=0}^n S(n,,r) s(r,,k) right) x^k end{aligned} \ therefore sum_{r=0}^n S(n,,r) s(r,,k) = sum_{r=k}^n S(n,,r) s(r,,k) = delta_{n,,k})]부호 없는 스털링 수, 그러니까 [math(s(n,,k) = (-1)^{n-k} begin{bmatrix} n \ k end{bmatrix})]표기를 이용하면 다음과 같이 된다.[math(displaystyle begin{aligned} sum_{r=k}^n(-1)^r begin{bmatrix} n \ r end{bmatrix} begin{Bmatrix} r \ k end{Bmatrix} &= (-1)^n delta_{n,,k} \ sum_{r=k}^n(-1)^r begin{Bmatrix} n \ r end{Bmatrix} begin{bmatrix} r \ k end{bmatrix} &= (-1)^k delta_{n,,k} end{aligned})]두 식에서 우변의 [math(-1)]의 지수가 다르지만 사실 둘 다 [math((-1)^n)]을 쓰든 [math((-1)^k)]를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 [math(delta_{n,,k} = 1)], 즉 [math(n=k)]일 때 뿐이며, 좌변에서 [math(n=k)]란 곧 [math((-1)^k begin{bmatrix} k \ k end{bmatrix} begin{Bmatrix} k \ k end{Bmatrix} = (-1)^k = (-1)^n)]을 의미하기 때문이다.
3.3. 생성함수
[math(displaystyle begin{aligned} frac{left{ ln(1+x) right}^k}{k!} &= sum_{n=0}^infty s(n,,k) frac{x^n}{n!} \ frac{ left{ - ln(1-x) right}^k}{k!} &= sum_{n=0}^infty begin{bmatrix} n \ k end{bmatrix} frac{x^n}{n!} end{aligned})]
|
제1종 스털링 수 특성상 [math(n<k)]이면 [math(s(n,,k) = begin{bmatrix} n \ k end{bmatrix} = 0)]이므로 아래와 같이 축약된 식으로 많이 나타낸다.
[math(displaystyle begin{aligned} frac{left{ ln(1+x) right}^k}{k!} &= sum_{n=k}^infty s(n,,k) frac{x^n}{n!} \ frac{ left{ - ln(1-x) right}^k}{k!} &= sum_{n=k}^infty begin{bmatrix} n \ k end{bmatrix} frac{x^n}{n!} end{aligned})]
|
증명에는 이항급수 [math(displaystyle (1+x)^r = sum_{n=0}^infty binom rn x^n )]을 이용한다. 테일러 급수의 예에 설명되어있듯이 이항급수에서 조합 기호는 [math(displaystyle binom rn = frac 1{n!} prod_{i=0}^{n-1}(r-i))]로 재정의되고 하강 계승의 정의에 따라 [math(displaystyle prod_{i=0}^{n-1}(r-i) = r^{underline n})]이므로 이항급수는 다음과 같이 고쳐 쓸 수 있다.
[math(displaystyle begin{aligned}(1+x)^r &= sum_{n=0}^infty frac{r^{underline n}}{n!} x^n = sum_{n=0}^infty left{ sum_{k=0}^n s(n,,k) r^k right} frac{x^n}{n!} = sum_{k=0}^infty r^k sum_{n=0}^infty s(n,,k) frac{x^n}{n!} \ &= e^{ln(1+x)^r} = e^{r ln(1+x)} = sum_{k=0}^infty frac{ left{r ln(1+x) right}^k}{k!} = sum_{k=0}^infty r^k frac{ left{ ln(1+x) right}^k}{k!} end{aligned} \ therefore frac{ left{ ln(1+x) right}^k}{k!} = sum_{n=0}^infty s(n,,k) frac{x^n}{n!} = sum_{n=k}^infty s(n,,k) frac{x^n}{n!})]
|
위 유도 과정에서 [math(r)]에 [math(-r)]을, [math(x)]에 [math(-x)]를 대입하면 다음과 같이 부호 없는 제1종 스털링 수의 생성함수로 바뀐다.
[math(displaystyle begin{aligned}(1-x)^{-r} &= sum_{n=0}^infty frac{(-r)^{underline n}}{n!}(-x)^n = sum_{n=0}^infty frac{(-1)^n r^{overline n}}{n!}(-1)^n x^n = sum_{n=0}^infty frac{ r^{overline n}}{n!} x^n = sum_{n=0}^infty left{ sum_{k=0}^n begin{bmatrix} n \ k end{bmatrix} r^k right} frac{x^n}{n!} = sum_{k=0}^infty r^k sum_{n=0}^infty begin{bmatrix} n \ k end{bmatrix} frac{x^n}{n!} \ &= e^{ln(1-x)^{-r}} = e^{-r ln(1-x)} = sum_{k=0}^infty frac{ left{ -r ln(1-x) right}^k}{k!} = sum_{k=0}^infty r^k frac{ left{ -ln(1-x) right}^k}{k!} end{aligned} \ therefore frac{ left{ -ln(1-x) right}^k}{k!} = sum_{n=0}^infty begin{bmatrix} n \ k end{bmatrix} frac{x^n}{n!} = sum_{n=k}^infty begin{bmatrix} n \ k end{bmatrix} frac{x^n}{n!} )]
|