스털링 수

1. 개요

스털링 수는 조합론과 수치해석 등 다양한 분야에서 활용되는 수의 한 종류로, 제1종 스털링 수와 제2종 스털링 수로 구분된다. 제1종 스털링 수는 n개의 원소를 k개의 순환 순열로 분할하는 경우의 수를 나타내며, 제2종 스털링 수는 n개의 원소를 k개의 공집합이 아닌 부분집합으로 분할하는 경우의 수를 나타낸다. 스털링 수는 점화식, 생성 함수, 역행렬 관계 등 다양한 성질을 가지며, 조합론적인 의미를 갖는다. 라 수와 밀접한 관련이 있으며, 음의 정수 값으로 확장될 수도 있다.

2. 정의

스털링 수는 제1종 스털링 수와 제2종 스털링 수로 나뉜다.

제1종 스털링 수는 순열과 관련된 개념으로, 부호 없는 제1종 스털링 수와 부호 있는 제1종 스털링 수로 정의된다. 부호 없는 제1종 스털링 수는 n개 원소의 순열 가운데 정확히 m개 순환으로 구성된 순열들의 수를 나타내며, 부호 있는 제1종 스털링 수는 부호 없는 제1종 스털링 수에 $(-1)^\{n-m\}$을 곱하여 정의한다.

제2종 스털링 수는 집합의 분할과 관련된 개념으로, n개 원소의 집합을 m개의 공집합이 아닌 부분집합으로 나누는 방법의 수를 나타낸다.

2.1. 제1종 스털링 수

부호 없는 제1종 스털링 수(unsigned Stirling numbers of the first kind^영어)는 다음 식으로 정의된다.
:$x(x-1)(x-2)\backslash cdots(x-n+1)=\backslash sum\_\{m=0\}^n(-1)^\{n-m\}\backslash left[\{n\backslash atop\; m\}\backslash right]x^m$
부호 없는 제1종 스털링 수는 $c(n,m)$으로 쓰기도 하며, 대괄호를 쓰는 표기법은 도널드 커누스가 도입하였다. 부호 없는 제1종 스털링 수는 n개의 원소의 순열 가운데, 정확히 m개의 순환(cycle)들로 구성된 순열들의 수이다. (이 경우, 고정점은 길이 1의 순환으로 간주한다.)

(부호 있는) 제1종 스털링 수((signed) Stirling numbers of the first kind^영어)는 다음과 같이 정의된다.
:$s(n,m)=(-1)^\{n-m\}\backslash left[\{n\backslash atop\; m\}\backslash right]$

부호 없는 제1종 스털링 수의 값은 아래 표와 같다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

n ＼ m	0	1	2	3	4	5	6	7	8	9	10
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1
10	0	362880	1026576	1172700	723680	269325	63273	9450	870	45	1

제1종 스털링 수(:en:Stirling numbers of the first kind) $[\{\backslash textstyle\{n\backslash atop\; k\}\}]$는 상승 계승 멱 $x^\{\backslash overline\{n\}\}\backslash equiv\; x(x+1)(x+2)\backslash cdots(x+n-1)$를 $x$의 멱급수로 표현했을 때의 전개 계수로 정의된다.
:$x^\{\backslash overline\{n\}\}\; =\; \backslash textstyle\backslash sum\backslash limits\_\{k=0\}^n\; \backslash displaystyle\; \backslash left[\{n\backslash atop\; k\}\backslash right]\backslash ,x^k$
이 정의에서는 $0\backslash leq\; k\backslash leq\; n$이다. 또한, 편의상 $[\{\backslash textstyle\{0\backslash atop0\}\}]\; =\; 1$로 정의한다. 제1종 스털링 수는 다음 점화식으로 계산할 수 있다.
:$\backslash left[\{n\backslash atop\; k\}\backslash right]\; =\; \backslash left[\{n-1\backslash atop\; k-1\}\backslash right]\; +\; (n-1)\backslash ,\backslash left[\{n-1\backslash atop\; k\}\backslash right]$

제1종 스털링 수 중에서 간단한 수식으로 쓸 수 있는 경우는 다음과 같다.
:$$
\left[{n\atop 0}\right] = 0,\quad
\left[{n\atop 1}\right] = (n-1)!,\quad
\left[{n\atop n-1}\right] = \left({n \atop 2}\right),\quad
\left[{n\atop n}\right] = 1

참고로, $(\{\backslash textstyle\{n\backslash atop2\}\})$는 이항 계수(이항 정리)이다.

위에 제시한 점화식에 따라 제1종 스털링 수는 아래 표와 같이 계산된다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

n ＼ k	0	1	2	3	4	5	6	7
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1

하강 계승 멱 $x^\{\backslash underline\{n\}\}\backslash equiv\; x\backslash ,(x-1)(x-2)\backslash cdots(x-n+1)$도 제1종 스털링 수를 포함하는 전개 계수를 갖는데, 이를 $x$의 멱급수로 표현하면 다음과 같다.
:$x^\{\backslash underline\{n\}\}\; =\; \backslash textstyle\backslash sum\backslash limits\_\{k=0\}^n\; (-1)^\{n+k\}\; \backslash displaystyle\; \backslash left[\; \{n\backslash atop\; k\}\backslash right]\backslash ,x^k$
즉, 전개 계수는 제1종 스털링 수에 부호 보정 $(-1)^\{n+k\}$를 더한 값이다.

다음 항등식이 성립한다.
:$\backslash begin\{align\}$
&\textstyle\sum\limits_{k=0}^n \displaystyle\left[{n\atop k}\right] = n!,\\
&\textstyle\sum\limits_{k=0}^n 2^k \displaystyle\left[{n\atop k}\right] = (n+1)!,\\
&\textstyle\sum\limits_{k=0}^n (-1)^k \displaystyle\left[{n\atop k}\right] = 0\quad(n\geq2)
\end{align}

제1종 스털링 수는 베르누이 수 $B\_k$ 와 다음과 같은 관계를 갖는다.
:$\backslash begin\{align\}$
&\frac{1}{m!} \textstyle\sum\limits_{k=0}^m \displaystyle\left[{m+1\atop k+1}\right]\,B_k = \frac{1}{m+1},\\
&\frac{1}{(m-1)!} \textstyle\sum\limits_{k=0}^m \displaystyle\left[{m\atop k}\right]\,B_k = -\frac{1}{m+1}\quad(m\geq1).
\end{align}

제1종 스털링 수 $[\{\backslash textstyle\{n\backslash atop\; k\}\}]$는 조합론에서 $n$개의 원소를 $k$개의 순환 순열로 분할하는 조합의 수를 나타낸다. 순환 순열은 반복되는 원소를 나타내는 데이터 열이다. 예를 들어, 야마노테선 역처럼 순환하는 것을 의미한다. 여기서는 순환 순열을 $(0,2,1,3)$과 같이 표기한다. 순환 순열은 순열이지만 $(0,2,1,3)$과 $(2,1,3,0)$처럼 원소를 순환 치환한 것은 동일한 것으로 간주한다. $n$개의 원소로 구성된 순환 순열의 조합은 $(n-1)!$가지이다.

4개의 원소를 2개의 순환 순열로 분할하는 조합은 다음과 같이 11가지이다.
:$\backslash begin\{array\}\{llll\}$
{} [(0),(1,2,3)], & [(0),(1,3,2)], & [(1),(0,2,3)], & [(1),(0,3,2)] \\
{} [(2),(0,1,3)], & [(2),(0,3,1)], & [(3),(0,1,2)], & [(3),(0,2,1)] \\
{} [(0,1),(2,3)], & [(0,2),(1,3)], & [(0,3),(1,2)]
\end{array}

2.2. 제2종 스털링 수

제2종 스털링 수(Stirling numbers of the second kind^영어)는 $n$개의 원소를 $m$개의 공집합이 아닌 부분집합으로 나누는 방법의 수이다. $S(n,m)$ 또는 $\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}$으로 표기하며, 중괄호를 쓰는 표기법은 도널드 커누스가 도입하였다.

이는 다음의 전개식으로 정의된다.
:$x^n=\backslash sum\_\{m=0\}^n\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}x(x-1)\backslash cdots(x-m+1)$

제2종 스털링 수는 다음과 같은 점화식으로 표현될 수 있다.

:$S\_\{n,m\}\; =\; S\_\{n-1,m-1\}\; +\; m\backslash cdot\; S\_\{n-1,m\}$

제2종 스털링 수의 값은 다음과 같다.

3. 성질

스털링 수는 생성 함수, 점화식, 합 공식 등 다양한 성질을 가진다. 제1종 및 제2종 스털링 수는 서로 역행렬 관계이며, 이항 계수와 유사한 성질을 많이 가지고 있다.

제1종 및 제2종 스털링 수는 서로 역행렬 관계로, 다음 식을 만족한다.

:$\backslash sum\_\{j=k\}^n\; s(n,j)\; S(j,k)\; =\; \backslash sum\_\{j=k\}^n\; (-1)^\{n-j\}\; \backslash biggl[\{n\; \backslash atop\; j\}\backslash biggr]\; \backslash biggl\backslash \; =\; \backslash textstyle\backslash sum\backslash limits\_\{k=0\}^n\; (-1)^\{n+k\}\; \backslash displaystyle\; \backslash left[\; \{n\backslash atop\; k\}\backslash right]\backslash ,x^k$

전개 계수는 제1종 스털링 수에 부호 보정 $(-1)^\{n+k\}$를 더한 값이다.

:$\backslash begin\{align\}$
&\textstyle\sum\limits_{k=0}^n \displaystyle\left[{n\atop k}\right] = n!,\\
&\textstyle\sum\limits_{k=0}^n 2^k \displaystyle\left[{n\atop k}\right] = (n+1)!,\\
&\textstyle\sum\limits_{k=0}^n (-1)^k \displaystyle\left[{n\atop k}\right] = 0\quad(n\geq2)
\end{align}

첫 번째 관계식은 $1^\{\backslash overline\{n\}\}=n!$ 에서 유도된다.

제1종 스털링 수는 베르누이 수 $B\_k$ 와 다음과 같은 관계를 가진다.

:$\backslash begin\{align\}$
&\frac{1}{m!} \textstyle\sum\limits_{k=0}^m \displaystyle\left[{m+1\atop k+1}\right]\,B_k = \frac{1}{m+1},\\
&\frac{1}{(m-1)!} \textstyle\sum\limits_{k=0}^m \displaystyle\left[{m\atop k}\right]\,B_k = -\frac{1}{m+1}\quad(m\geq1).
\end{align}

첫 번째 관계식은 상승 계승의 합 공식:
:$\backslash textstyle\backslash sum\backslash limits\_\{k=0\}^\{n-1\}\; (k+1)^\{\backslash overline\{m\}\}\; =\; \backslash dfrac\{n^\{\backslash overline\{m+1\}\}\}\{m+1\}$
에서 유도할 수 있다.

제2종 스털링 수 $\backslash left\backslash \backslash equiv\; x\backslash ,(x-1)(x-2)\backslash cdots(x-k+1)$의 급수로 전개했을 때의 전개 계수로 정의된다.

:$x^n\; =\; \backslash textstyle\backslash sum\backslash limits\_\{k=0\}^n\; \backslash displaystyle\backslash left\backslash$

거듭제곱 $x^n$은 상승 계승 멱 $x^\{\backslash overline\{k\}\}$으로 전개한 경우에도 제2종 스털링 수를 포함하는 전개 계수를 가진다.

:$x^n\; =\; \backslash textstyle\backslash sum\backslash limits\_k^n\; (-1)^\{n+k\}\; \backslash displaystyle\backslash left\backslash$

전개 계수는 제2종 스털링 수에 부호 보정 $(-1)^\{n+k\}$를 더한 값이다.

3.1. 생성함수

스털링 수는 다음과 같은 생성함수를 갖는다.
:$\backslash sum\_\{n=0\}^\backslash infty\backslash left[\{n\backslash atop\; m\}\backslash right]x^n/n!=\backslash frac\{(-\backslash ln(1-x))^m\}\{m!\}$
:$\backslash sum\_\{n=0\}^\backslash infty\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}x^n/n!=\backslash frac\{(\backslash exp(x)-1)^m\}\{m!\}$

3.2. 점화식

스털링 수는 다음 점화식을 만족한다.

:$\backslash left[\{n+1\backslash atop\; m\}\backslash right]\; =\; n\; \backslash left[\{n\backslash atop\; m\}\backslash right]\; +\; \backslash left[\{n\backslash atop\; m-1\}\backslash right]$

:$\backslash left\backslash \{\{n+1\backslash atop\; m\}\backslash right\backslash \}=m\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}+\backslash left\backslash \{\{n\backslash atop\; m-1\}\backslash right\backslash \}$

또한, 다음과 같은 공식이 존재한다.

:$\backslash sum\_\{p=k\}^n\backslash left[\{n\backslash atop\; p\}\backslash right]\backslash binom\; pk\; =\; \backslash left[\{n+1\backslash atop\; k+1\}\backslash right]$

제1종 스털링 수는 다음 점화식으로 계산할 수 있다.

:$\backslash left[\{n\backslash atop\; k\}\backslash right]\; =\; \backslash left[\{n-1\backslash atop\; k-1\}\backslash right]\; +\; (n-1)\backslash ,\backslash left[\{n-1\backslash atop\; k\}\backslash right]$

제2종 스털링 수는 다음 점화식으로 계산할 수 있다.

:$\backslash left\backslash \{\{n\backslash atop\; k\}\backslash right\backslash \}\; =\; \backslash left\backslash \{\{n-1\backslash atop\; k-1\}\backslash right\backslash \}\; +\; k\backslash ,\backslash left\backslash \{\{n-1\backslash atop\; k\}\backslash right\backslash \}$

3.3. 합 공식

다음은 스털링 삼각형에서 각 열을 더한 값이다.

:$\backslash sum\_\{m=0\}^n\; \backslash left[\{n\backslash atop\; m\}\backslash right]\; =\; n!$
:$\backslash sum\_\{m=0\}^n\backslash left\backslash =n!$ 에서 유도된다. 두 번째 관계식은 $2^\{\backslash overline\{n\}\}=(n+1)!$ 에서 유도된다. 세 번째 관계식은 $n\backslash geq2$ 에 관하여 $(-1)^\{\backslash overline\{n\}\}=0$ 이기 때문에 유도된다.

3.4. 특별한 값

$m>n$이면 스털링 수는 0이다.
:$\backslash left[\{n\backslash atop\; m\}\backslash right]=\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}=0\backslash qquad(m>n)$
$m=0$인 경우 스털링 수는 크로네커 델타 $\backslash delta\_\{n,0\}$이다.
:
$m=1$인 경우는 다음과 같다.
:$\backslash left[\{n\backslash atop1\}\backslash right]\; =\; (n-1)!\backslash qquad(n\backslash ge1)$
:$\backslash left\backslash \{\{n\backslash atop1\}\backslash right\backslash \}=1\backslash qquad(n\backslash ge1)$
$m=2$인 경우는 다음과 같다. 여기서 $H\_k$는 조화수이다.
:$\backslash left[\{n\backslash atop2\}\backslash right]\; =\; (n-1)!H\_\{n-1\}=(n-1)!\backslash sum\_\{k=1\}^\{n-1\}\backslash frac1k$
:$\backslash left\backslash \{\{n\backslash atop2\}\backslash right\backslash \}\; =\; 2^\{n-1\}-1$
$m=n$인 경우 스털링 수는 항상 1이다.
:$\backslash left[\{n\backslash atop\; n\}\backslash right]=\backslash left\backslash \{\{n\backslash atop\; n\}\backslash right\backslash \}=1\backslash qquad(n\backslash ge0)$
$m=n-1$인 경우는 다음과 같다.
:$\backslash left[\{n\backslash atop\; n-1\}\backslash right]=\backslash left\backslash \{\{n\backslash atop\; n-1\}\backslash right\backslash \}\; =\backslash binom\; n2$
$m=n-2$인 경우는 다음과 같다.
:$\backslash left[\{n\backslash atop\; n-2\}\backslash right]=\; \backslash frac\{1\}\{4\}\; (3n-1)\backslash binom\; n3$
:$\backslash left\backslash \{\{n\backslash atop\; n-2\}\backslash right\backslash \}=\backslash frac\{3n-5\}4\backslash binom\; n3$

4. 조합론적 의미

제1종 및 제2종 스털링 수는 조합론적으로 서로 다른 의미를 갖는다.

제1종 스털링 수 $[\{\backslash textstyle\{n\backslash atop\; k\}\}]$는 n개의 원소를 k개의 순환 순열로 분할하는 조합의 수를 나타낸다. 순환 순열은 야마노테 선 역처럼 반복되는 원소를 나타내는 데이터 열이다. 예를 들어 순환 순열 $(0,2,1,3)$은 0, 2, 1, 3 순서로 숫자가 반복되는 것을 의미한다. 순환 순열의 경우, $(0,2,1,3)$과 $(2,1,3,0)$처럼 원소를 순환 치환한 것은 동일한 것으로 간주한다. $n$개의 원소로 구성된 순환 순열의 조합은 $(n-1)!$가지이며, $(1)$은 1개의 원소로 구성된 순환 순열로 간주한다.

예를 들어 4개의 원소를 2개의 순환 순열로 분할하는 경우, 구성 원소가 1개와 3개인 순환 순열로 분할하는 조합과 2개와 2개인 순환 순열로 분할하는 조합이 있다. 전자는 4개의 원소 중 1개를 선택하고 나머지 3개의 원소로 순환 순열을 만드는 조합으로, 4 × 2 = 8가지이다. 후자는 4개의 원소 중 2개를 선택하는 조합이 6가지이고, 2개의 원소로 구성된 순환 순열은 1가지뿐이지만, 동일한 순환 순열 2개가 생기므로 6/2 = 3가지이다. 따라서 4개의 원소를 2개의 순환 순열로 분할하는 조합은 총 8 + 3 = 11가지이며, 이는 $[\{\backslash textstyle\{4\backslash atop2\}\}]$와 일치한다.

제2종 스털링 수 $\backslash \backslash \}$는 n개의 원소를 k개의 공집합이 아닌 부분집합으로 나누는 방법의 수이다.

4.1. 제1종 스털링 수

부호 없는 제1종 스털링 수는 n개의 원소의 순열 가운데, 정확히 m개의 순환(cycle)들로 구성된 순열들의 수이다. (이 경우, 고정점은 길이 1의 순환으로 간주한다.) 예를 들어 $\backslash textstyle\backslash left[\{4\backslash atop\; 2\}\backslash right]=11$인데, 이는 4개의 원소를 2개의 순환으로 분할하는 방법이 11가지임을 의미한다.

4개의 원소를 2개의 순환 순열로 분할하는 11가지 방법은 다음과 같다.

:$\backslash begin\{array\}\{llll\}$
{} [(0),(1,2,3)], & [(0),(1,3,2)], & [(1),(0,2,3)], & [(1),(0,3,2)] \\
{} [(2),(0,1,3)], & [(2),(0,3,1)], & [(3),(0,1,2)], & [(3),(0,2,1)] \\
{} [(0,1),(2,3)], & [(0,2),(1,3)], & [(0,3),(1,2)]
\end{array}

제1종 스털링 수 $[\{\backslash textstyle\{n\backslash atop\; k\}\}]$는 조합론에서 $n$개의 원소를 $k$개의 순환 순열로 분할하는 조합의 수를 나타낸다. 순환 순열은 야마노테 선 역처럼 반복되는 원소를 나타내는 데이터 열이다. 예를 들어, 순환 순열 $(0,2,1,3)$은 0, 2, 1, 3 순서로 숫자가 반복되는 것을 의미한다. 순환 순열의 경우, $(0,2,1,3)$과 $(2,1,3,0)$처럼 원소를 순환 치환한 것은 동일한 것으로 간주한다.

$n$개의 원소로 구성된 순환 순열의 조합은 $(n-1)!$가지이다. $(1)$은 1개의 원소로 구성된 순환 순열로 간주한다.

제1종 스털링 수는 다음 점화식으로 계산할 수 있다.
:$\backslash left[\{n\backslash atop\; k\}\backslash right]\; =\; \backslash left[\{n-1\backslash atop\; k-1\}\backslash right]\; +\; (n-1)\backslash ,\backslash left[\{n-1\backslash atop\; k\}\backslash right]$

간단한 수식으로 표현되는 제1종 스털링 수는 다음과 같다.
:$$
\left[{n\atop 0}\right] = 0,\quad
\left[{n\atop 1}\right] = (n-1)!,\quad
\left[{n\atop n-1}\right] = \left({n \atop 2}\right),\quad
\left[{n\atop n}\right] = 1

여기서 $(\{\backslash textstyle\{n\backslash atop2\}\})$는 이항 계수이다.

부호 없는 제1종 스털링 수의 값은 아래 표와 같다.


(부호 있는) 제1종 스털링 수는 다음과 같이 정의된다.
:$s(n,m)=(-1)^\{n-m\}\backslash left[\{n\backslash atop\; m\}\backslash right]$

4.2. 제2종 스털링 수

제2종 스털링 수(Stirling numbers of the second kind^영어)는 n개의 원소를 m개의 공집합이 아닌 부분집합으로 나누는 방법의 수이다. 도널드 커누스가 도입한 중괄호 표기법 $\backslash textstyle\backslash left\backslash \{\{n\backslash atop\; m\}\backslash right\backslash \}$ 또는 $S(n,m)$으로 쓴다.

제2종 스털링 수는 다음 점화식으로 계산할 수 있다.

:$\backslash left\backslash \{\{n\backslash atop\; k\}\backslash right\backslash \}\; =\; \backslash left\backslash \{\{n-1\backslash atop\; k-1\}\backslash right\backslash \}\; +\; k\backslash ,\backslash left\backslash \backslash equiv\; x\backslash ,(x-1)(x-2)\backslash cdots(x-k+1)$의 급수로 전개했을 때의 전개 계수로 정의된다.
:$x^n\; =\; \backslash textstyle\backslash sum\backslash limits\_\{k=0\}^n\; \backslash displaystyle\backslash left\backslash$

5. 역행렬 관계

제1종 스털링 수와 제2종 스털링 수는 서로 역행렬 관계를 갖는다.

:$\backslash sum\_\{j=k\}^n\; s(n,j)\; S(j,k)\; =\; \backslash sum\_\{j=k\}^n\; (-1)^\{n-j\}\; \backslash biggl[\{n\; \backslash atop\; j\}\backslash biggr]\; \backslash biggl\backslash \{\{\backslash !j\backslash !\; \backslash atop\; \backslash !k\backslash !\}\backslash biggr\backslash \}\; =\; \backslash delta\_\{n,k\}$

:$\backslash sum\_\{j=k\}^n\; S(n,j)\; s(j,k)\; =\; \backslash sum\_\{j=k\}^n\; (-1)^\{j-k\}\; \backslash biggl\backslash \{\{\backslash !n\backslash !\; \backslash atop\; \backslash !j\backslash !\}\backslash biggr\backslash \}\; \backslash biggl[\{j\; \backslash atop\; k\}\backslash biggr]=\; \backslash delta\_\{n,k\},$

여기서 $\backslash delta\_\{nk\}$는 크로네커 델타이다. 이 두 관계는 행렬 역관계로 이해될 수 있다.

6. 라 수 (Lah Numbers)

라 수(Lah numbers) $L(n,k)\; =\; \{n-1\; \backslash choose\; k-1\}\; \backslash frac\{n!\}\{k!\}$는 제3종 스털링 수라고도 불린다. 관례에 따라 $L(0,0)=1$이며,

이 수들은 내림 차승을 오름 차승으로, 또는 그 반대로 표현하는 계수이다.

:$x^\{(n)\}\; =\; \backslash sum\_\{k=0\}^n\; L(n,k)\; (x)\_k$ 그리고 $(x)\_n\; =\; \backslash sum\_\{k=0\}^n\; (-1)^\{n-k\}\; L(n,k)x^\{(k)\}$.

이는 $(x)\_0,(x)\_1,(x)\_2,\backslash cdots$와 $x^\{(0)\},x^\{(1)\},x^\{(2)\},\backslash cdots$ 기저 사이의 기저 변환을 표현한다. 한 공식은 다른 공식의 역수이므로 다음이 성립한다.

:$\backslash sum\_\{j=k\}^n\; (-1)^\{j-k\}\; L(n,j)\; L(j,k)\; =\; \backslash delta\_\{n,k\}$.

$x^\{(n)\}$에서 $x^n$으로의 기저 변환과 $x^n$에서 $(x)\_\{n\}$으로의 기저 변환을 결합하면 $x^\{(n)\}$에서 $(x)\_\{n\}$으로 직접 기저 변환이 이루어진다.

:$L(n,k)\; =\; \backslash sum\_\{j=k\}^n\; \backslash biggl[\{n\; \backslash atop\; j\}\backslash biggr]\; \backslash biggl\backslash \{\{\backslash !j\backslash !\; \backslash atop\; \backslash !k\backslash !\}\backslash biggr\backslash \}$

행렬 관점에서, $L$이 $L\_\{nk\}=L(n,k)$를 원소로 갖는 행렬이고, $L^\{-\}$이 $L^\{-\}\_\{nk\}=(-1)^\{n-k\}L(n,k)$를 원소로 갖는 행렬이면, 하나는 다른 것의 역행렬이다. 즉, $L^\{-\}\; =\; L^\{-1\}$이다. 부호 없는 제1종 스털링 수의 행렬과 제2종 스털링 수의 행렬을 곱하면 라 수 행렬이 된다: $L\; =\; |s|\; \backslash cdot\; S$.

조합론적으로, $\backslash left\backslash \{\{\backslash !\backslash n\backslash !\; \backslash atop\; \backslash !k\backslash !\}\backslash right\backslash \}$, $\backslash left[\{n\; \backslash atop\; k\}\backslash right]$, $L(n,k)$는 각각 n개의 원소를 k개의 비어 있지 않고 라벨이 없는 부분집합으로 분할할 때, 각 부분집합에 순서가 없는 경우, 순환 순서가 있는 경우, 선형 순서가 있는 경우의 수를 나타낸다. 따라서 다음 부등식이 성립한다.

:$\backslash biggl\backslash \{\{\backslash !n\backslash !\; \backslash atop\; \backslash !k\backslash !\}\backslash biggr\backslash \}\; \backslash leq\; \backslash biggl[\{n\; \backslash atop\; k\}\backslash biggr]\; \backslash leq\; L(n,k)$.

7. 역사

제임스 스털링(James Stirling)이 1730년에 《미분법: 무한급수의 합과 보간에 대한 논문》(Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum^라틴어)이라는 책에서 도입하였다. 닐스 닐센(Niels Nielsen)이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.

8. 기타

스털링 수는 다음과 같은 다양한 공식과 관련되어 있다.

두 수열 $\backslash \{f\_n\backslash \}$과 $\backslash \{g\_n\backslash \}$이 다음 유한 합 스털링 수 공식으로 관련되어 있을 때,

:$g\_n\; =\; \backslash sum\_\{k=0\}^\{n\}\; \backslash left\backslash \{\backslash begin\{matrix\}\; n\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right\backslash \}\; f\_k,$

모든 정수 $n\; \backslash geq\; 0$에 대해, $f\_n$에 대한 해당 역 공식은 다음과 같다.

:$f\_n\; =\; \backslash sum\_\{k=0\}^\{n\}\; \backslash left[\backslash begin\{matrix\}\; n\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right]\; (-1)^\{n-k\}\; g\_k.$

이 두 수열 간의 역 관계는 지수 생성 함수 간의 함수 방정식으로 표현되며, 이는 스털링 (생성 함수) 변환으로 주어진다.

:$\backslash widehat\{G\}(z)\; =\; \backslash widehat\{F\}\backslash left(e^z-1\backslash right)$

:$\backslash widehat\{F\}(z)\; =\; \backslash widehat\{G\}\backslash left(\backslash log(1+z)\backslash right).$

$D\; =\; d/dx$일 때, 미분 연산자 $x^nD^n$과 $(xD)^n$은 모든 정수 $n\; \backslash geq\; 0$에 대해 다음 공식으로 관련된다.

:$$
\begin{align}
(xD)^n &= \sum_{k=0}^n S(n, k) x^k D^k \\
x^n D^n &= \sum_{k=0}^n s(n, k) (xD)^k = (xD)_n = xD(xD - 1)\ldots (xD - n + 1)
\end{align}


함수 $f(x)$의 전방 차분과 일반 $n^\{th\}$ 미분을 관련시키는 공식은 다음과 같다.

:$\backslash frac\{1\}\{k!\}\; \backslash frac\{d^k\}\{dx^k\}\; f(x)\; =\; \backslash sum\_\{n=k\}^\{\backslash infty\}\; \backslash frac\{s(n,\; k)\}\{n!\}\; \backslash Delta^n\; f(x)$

:$\backslash frac\{1\}\{k!\}\; \backslash Delta^k\; f(x)\; =\; \backslash sum\_\{n=k\}^\{\backslash infty\}\; \backslash frac\{S(n,\; k)\}\{n!\}\; \backslash frac\{d^n\}\{dx^n\}\; f(x).$

Abramowitz와 Stegun은 제1종 및 제2종 스털링 수와 관련된 다음 대칭 공식을 제시한다.

:$\backslash left[\{\; n\; \backslash atop\; k\; \}\; \backslash right]\; =\; \backslash sum\_\{j=n\}^\{2n-k\}\; (-1)^\{j-k\}\; \backslash binom\{j-1\}\{k-1\}\; \backslash binom\{2n-k\}\{j\}\; \backslash left\backslash \{\{\; j-k\; \backslash atop\; j-n\}\; \backslash right\backslash \}$

:$$
\left\{{n \atop k}\right\} = \sum_{j=n}^{2n-k} (-1)^{j-k} \binom{j-1}{k-1} \binom{2n-k}{j} \left[{j-k \atop j-n } \right]


스털링 수는 음의 정수 값으로 확장될 수 있지만, 모든 저자가 동일한 방식으로 확장하는 것은 아니다. 제1종 및 제2종 스털링 수는 다음 관계를 갖는다.

: $\backslash biggl[\{n\; \backslash atop\; k\}\backslash biggr]\; =\; \backslash biggl\backslash \{\{\backslash !-k\backslash !\; \backslash atop\; \backslash !-n\backslash !\}\backslash biggr\backslash \}$ 및 $$
\biggl\{{\!n\! \atop \!k\!}\biggr\} = \biggl[{-k \atop -n}\biggr] (단, n과 k는 음이 아닌 정수)

도널드 커누스는 점화식을 모든 정수로 확장하여 보다 일반적인 스털링 수를 정의했다. 데이비드 브랜슨은 양의 정수 n과 k에 대해 $\backslash left[\{-n\; \backslash atop\; -k\}\backslash right]\backslash !,$ $\backslash left\backslash \{\{\backslash !-n\backslash !\; \backslash atop\; \backslash !-k\backslash !\}\backslash right\backslash \}\backslash !,$ $\backslash left[\{-n\; \backslash atop\; k\}\backslash right]\backslash !,$ 및 $\backslash left\backslash \{\{\backslash !-n\backslash !\; \backslash atop\; \backslash !k\backslash !\}\backslash right\backslash \}$을 정의했다.