제1종 스털링 수

역사 raw
대문 랜덤 문서 최근 토론
1. 개요2. 정의3. 성질
3.1. 점화식3.2. 제2종 스털링 수와의 관계3.3. 생성함수
4. 관련 문서

Stirling numbers of the first kind

1. 개요[편집]

하강 계승 또는 상승 계승을 급수 표기로 나타냈을 때의 각 계수로 정의되는 수로, 제임스 스털링이 1730년에 도입하였다. 부호 없는 제1종 스털링 수 [nk]\begin{bmatrix} n \\ k \end{bmatrix}[주의]와 부호 있는 제1종 스털링 수 s(n,k)=(1)nk[nk]s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}로 나뉘며 0kn100 \le k \le n \le 10 범위에서[2][3] [nk]\begin{bmatrix} n \\ k \end{bmatrix} 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 s(n,k)s(n,\,k)의 부호가 ()(-)임을 의미한다.
n\kn \Big\backslash k
00
11
22
33
44
55
66
77
88
99
1010
00
11
00
11
00
11
00
22
11
11
00
33
22
33
11
00
44
66
1111
66
11
00
55
2424
5050
3535
1010
11
00
66
120120
274274
225225
8585
1515
11
00
77
720720
17641764
16241624
735735
175175
2121
11
00
88
50405040
1306813068
1313213132
67696769
19601960
322322
2828
11
00
99
4032040320
109584109584
118124118124
6728467284
2244922449
45364536
546546
3636
11
00
1010
403200403200
10265761026576
11727001172700
723680723680
269325269325
6327363273
94509450
870870
4545
11

2. 정의[편집]

xxnn하강 계승 xnx^{\underline n}xxnn차식으로 나타냈을 때 xkx^k의 계수를 제1종 스털링 수 s(n,k)s(n,\,k)로 정의한다. 즉
xn=k=0n1(xk)=x(x1)(x2)(xn+1)=k=0ns(n,k)xk\displaystyle x^{\underline n} = \prod _{k=0}^{n-1}(x-k) = x(x-1)(x-2) \cdots\cdots(x-n+1) = \sum_{k=0}^n s(n,\,k) x^k
한편, xxnn상승 계승 xnx^{\overline n}을 이용해서도 나타낼 수 있는데, 이 경우 제1종 스털링 수에 절댓값 기호가 붙는다.
xn=k=0n1(x+k)=x(x+1)(x+2)(x+n1)=k=0ns(n,k)xk\displaystyle x^{\overline n} = \prod_{k=0}^{n-1}(x+k) = x(x+1)(x+2) \cdots\cdots(x+n-1) = \sum_{k=0}^n \left| s(n,\,k) \right| x^k
s(n,k)\left| s(n,\,k) \right|는 종종 c(n,k)c(n,\,k)또는 [nk]\begin{bmatrix} n \\ k \end{bmatrix}로 나타내기도 하는데, 이를 부호 없는(unsigned) 제1종 스털링 수라고 한다.
각 하강 계승, 상승 계승을 이용한 정의식으로부터 다음과 같은 관계를 알 수 있다.
s(n,k)=(1)nkc(n,k)=(1)nk[nk]s(n,\,k) = (-1)^{n-k} c(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}
참고로 제2종 스털링 수ss를 대문자로 쓴 S(n,k)S(n,\,k)이다.

k=0k=0일 때는 상수항의 계수를 의미하며 값이 두 가지 경우로 나뉜다. n1n \ge 1이면 상수항이 없는 곱셈식이 되므로 s(n,0)=0s(n,\,0) = 0이지만, n=0n=0이면 순열과의 관계로부터 x0=xP0=x!x!=1x^{\underline 0} = {}_x {\rm P}_0 = \dfrac{x!}{x!} = 1이므로 편의상 s(0,0)=1s(0,\,0)=1로 정의한다. 또 부호 없는 제1종 스털링 수의 정의식에 x=1x=1을 대입하면 다음과 같은 관계식을 유도할 수 있다.
1n=k=1nk=n!=k=0n[nk]\displaystyle 1^{\overline n} = \prod_{k=1}^n k = n! = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix}
즉, 부호 없는 제1종 스털링 수의 합은 팩토리얼과 같다.

부호 없는 제1종 스털링 수는 조합론으로도 정의할 수 있는데, 원소의 개수가 nn인 집합을 구분되지 않는 kk개의 순환[4]으로 분할하는 방법의 수이다.
예를 들어 aa, bb, cc, dd를 원소로 갖는 집합을 22개의 순환으로 분할해보면
(a),(bcd)\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & c & d \end{pmatrix}
(a),(bdc)\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & d & c \end{pmatrix}
(b),(acd)\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & c & d \end{pmatrix}
(b),(adc)\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & d & c \end{pmatrix}
(c),(abd)\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b & d \end{pmatrix}
(c),(adb)\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & d & b \end{pmatrix}
(d),(abc)\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & b & c \end{pmatrix}
(d),(acb)\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & c & b \end{pmatrix}
(ab),(cd)\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} c & d \end{pmatrix}
(ac),(bd)\begin{pmatrix} a & c \end{pmatrix},\,\begin{pmatrix} b & d \end{pmatrix}
(ad),(bc)\begin{pmatrix} a & d \end{pmatrix},\,\begin{pmatrix} b & c \end{pmatrix}
1111가지가 얻어지며 [42]=11\begin{bmatrix} 4 \\ 2 \end{bmatrix} = 11이다.
위의 두 정의가 왜 동치인지 직관적으로 와닿지 않을 수도 있는데, 각 정의를 바탕으로 점화식을 써보면 완전히 똑같은 식이 유도된다(후술).

3. 성질[편집]

3.1. 점화식[편집]

[n+1k+1]=[nk]+n[nk+1]\begin{bmatrix} n+1 \\ k+1 \end{bmatrix} = \begin{bmatrix} n \\ k \end{bmatrix} + n \begin{bmatrix} n \\ k+1 \end{bmatrix}
xxnn승 상승 계승식에 (x+n)(x+n)을 곱해서 나타내보면 바로 위의 식이 튀어나온다.
xn+1=k=0n(x+k)=(x+n)k=0n1(x+k)=(x+n)xn=xxn+nxn\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}
맨 우변에 주목했을 때, xxnx \cdot x^{\overline n}에서 xk+1x^{k+1}의 계수는 xnx^{\overline n}xkx^k차항 계수와 같으며 이는 [nk]\begin{bmatrix} n \\ k \end{bmatrix}에 해당한다. 제2항에서 xk+1x^{k+1}의 계수는 xnx^{\overline n}xk+1x^{k+1}차항 계수이며 이는 [nk+1]\begin{bmatrix} n \\ k+1 \end{bmatrix}와 같다. 맨 좌변에서 xk+1x^{k+1}의 계수는 [n+1k+1]\begin{bmatrix} n+1 \\ k+1 \end{bmatrix}이므로 정리하면 위의 식이 얻어진다.

조합론을 이용한 증명의 경우, nn개 원소를 분할한 경우에서 (n+1)(n+1)번째 원소를 끼워넣는 방법을 고려해서 유도할 수 있는데, (n+1)(n+1)번째 원소를 길이가 11인 순환으로 남기는 방법과 다른 순환에 포함시키는 방법으로 나누어서 생각할 수 있다. 전자의 경우 (n+1)(n+1)번째 원소 자체가 11개의 순환이므로 nn개의 원소를 kk개의 순환으로 분할한 경우의 수 [nk]\begin{bmatrix} n \\ k \end{bmatrix}가 그대로 쓰인다. 후자의 경우, nn개의 원소를 (k+1)(k+1)개의 순환으로 분할한 것을 대칭군 표기법으로 나열한 뒤, 각 순환의 원소에서 맨 앞, 사이 사이, 맨 뒤에 끼워넣어보면 되는데, 예를 들어 순환의 길이가 mm이라고 하면 (n+1)(n+1)번째 원소가 들어갈 자리의 수는 (m+1)(m+1)이지만 맨 앞과 맨 뒤에 끼워넣는 경우는 같은 순환이므로 결과적으로 각 순환에서 원소 하나를 끼워넣어서 새로운 순환이 생길 경우의 수는 순환의 길이 mm과 같다. 각 순환의 길이를 모두 합한 값은 원소의 총 개수 nn과 같으므로 경우의 수는 [nk+1]\begin{bmatrix} n \\ k+1 \end{bmatrix}nn을 곱한 값 n[nk+1]n \begin{bmatrix} n \\ k+1 \end{bmatrix}이 된다.

또한 s(n,k)=(1)nk[nk]s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}였으므로 이를 대입해서 정리하면
s(n+1,k+1)=s(n,k)ns(n,k+1)s(n+1,\,k+1) = s(n,\,k) - n s(n,\,k+1)

3.2. 제2종 스털링 수와의 관계[편집]

  • [nk]={kn}\begin{bmatrix} n \\ k \end{bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix}
    두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 제2종 스털링 수에 점화식을 적용하면
    {kn}={k1n1}n{k1n}\begin{Bmatrix} -k \\ -n \end{Bmatrix} = \begin{Bmatrix} -k-1 \\ -n-1 \end{Bmatrix} - n \begin{Bmatrix} -k-1 \\ -n \end{Bmatrix}
    이 되는데, 우변의 제2항을 이항하면
    {k1n1}={kn}+n{k1n}\begin{Bmatrix} -k-1 \\ -n-1 \end{Bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix} + n \begin{Bmatrix} -k-1 \\ -n \end{Bmatrix}
    이제 각 성분을 교환하고 1-1을 곱해주면 제1종 스털링 수의 점화식 꼴이 된다.
    [n+1k+1]=[nk]+n[nk+1]\begin{bmatrix} n+1 \\ k+1 \end{bmatrix} = \begin{bmatrix} n \\ k \end{bmatrix} + n \begin{bmatrix} n \\ k+1 \end{bmatrix}
  • r=kns(n,r)S(r,k)=r=knS(n,r)s(r,k)=δnk\displaystyle \sum_{r=k}^n s(n,\,r) S(r,\,k) = \sum_{r=k}^n S(n,\,r) s(r,\,k) = \delta_{n\,k}
    δn,k\delta_{n,\,k}크로네커 델타이다. 두 식 모두 라흐 수의 정의처럼 각 스털링 수의 정의를 연달아 적용함으로써 도출된다.
    xn=r=0ns(n,r)xr=r=0ns(n,r)k=0rS(r,k)xk=r=0nk=0rs(n,r)S(r,k)xk=k=0nr=0ns(n,r)S(r,k)xk=k=0n(r=0ns(n,r)S(r,k))xkr=0ns(n,r)S(r,k)=r=kns(n,r)S(r,k)=δn,kxn=r=0nS(n,r)xr=r=0nS(n,r)k=0rs(r,k)xk=r=0nk=0rS(n,r)s(r,k)xk=k=0nr=0nS(n,r)s(r,k)xk=k=0n(r=0nS(n,r)s(r,k))xkr=0nS(n,r)s(r,k)=r=knS(n,r)s(r,k)=δn,k\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}
    부호 없는 스털링 수, 그러니까 s(n,k)=(1)nk[nk]s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}표기를 이용하면 다음과 같이 된다.
    r=kn(1)r[nr]{rk}=(1)nδn,kr=kn(1)r{nr}[rk]=(1)kδn,k\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}
    두 식에서 우변의 1-1의 지수가 다르지만 사실 둘 다 (1)n(-1)^n을 쓰든 (1)k(-1)^k를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 δn,k=1\delta_{n,\,k} = 1, 즉 n=kn=k일 때 뿐이며, 좌변에서 n=kn=k란 곧 (1)k[kk]{kk}=(1)k=(1)n(-1)^k \begin{bmatrix} k \\ k \end{bmatrix} \begin{Bmatrix} k \\ k \end{Bmatrix} = (-1)^k = (-1)^n을 의미하기 때문이다.

3.3. 생성함수[편집]

{ln(1+x)}kk!=n=0s(n,k)xnn!{ln(1x)}kk!=n=0[nk]xnn!\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종 스털링 수 특성상 n<kn<k이면 s(n,k)=[nk]=0s(n,\,k) = \begin{bmatrix} n \\ k \end{bmatrix} = 0이므로 아래와 같이 축약된 식으로 많이 나타낸다.
{ln(1+x)}kk!=n=ks(n,k)xnn!{ln(1x)}kk!=n=k[nk]xnn!\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}
증명에는 이항급수 (1+x)r=n=0(rn)xn\displaystyle (1+x)^r = \sum_{n=0}^\infty \binom rn x^n 을 이용한다. 테일러 급수의 예에 설명되어있듯이 이항급수에서 조합 기호는 (rn)=1n!i=0n1(ri)\displaystyle \binom rn = \frac 1{n!} \prod_{i=0}^{n-1}(r-i)로 재정의되고 하강 계승의 정의에 따라 i=0n1(ri)=rn\displaystyle \prod_{i=0}^{n-1}(r-i) = r^{\underline n}이므로 이항급수는 다음과 같이 고쳐 쓸 수 있다.
(1+x)r=n=0rnn!xn=n=0{k=0ns(n,k)rk}xnn!=k=0rkn=0s(n,k)xnn!=eln(1+x)r=erln(1+x)=k=0{rln(1+x)}kk!=k=0rk{ln(1+x)}kk!{ln(1+x)}kk!=n=0s(n,k)xnn!=n=ks(n,k)xnn!\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!}
위 유도 과정에서 rrr-r을, xxx-x를 대입하면 다음과 같이 부호 없는 제1종 스털링 수의 생성함수로 바뀐다.
(1x)r=n=0(r)nn!(x)n=n=0(1)nrnn!(1)nxn=n=0rnn!xn=n=0{k=0n[nk]rk}xnn!=k=0rkn=0[nk]xnn!=eln(1x)r=erln(1x)=k=0{rln(1x)}kk!=k=0rk{ln(1x)}kk!{ln(1x)}kk!=n=0[nk]xnn!=n=k[nk]xnn!\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!}

4. 관련 문서[편집]

[주의] 벡터행렬과 혼동할 수 있기 때문에 사전에 이것이 부호 없는 제1종 스털링 수임을 알려주어야 한다.[2] 제2종 스털링 수와의 관계식에서 알 수 있듯이 nkn \ge k만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제1종 스털링 수가 아니라 제2종 스털링 수지만……[3] n<kn<k이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 00인 것으로 약속한다.[4] 방향이 있는 원순열이다. 1 → 2 → 3 → 4 → 1과 1 → 4 → 3 → 2 → 1은 같은 원순열이지만 다른 순환이다. 대칭군의 표기법으로 나타내면 전자는 (1234)\begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix}이고 후자는 (1432)\begin{pmatrix} 1 & 4 & 3 & 2 \end{pmatrix}로 극명하게 다르다는 것을 알 수 있다.