스털링 수

3. 성질

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

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

:$\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. 생성함수

3. 2. 점화식

제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. 합 공식

3. 4. 특별한 값

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종 스털링 수'''는 다음과 같이 정의된다.

:$s(n,m)=(-1)^\{n-m\}\backslash left[\{n\backslash atop\; m\}\backslash right]$

4. 2. 제2종 스털링 수

제2종 스털링 수 $\backslash \backslash \}$는 $x^n$을 하강 계승 멱 $x^\{\backslash underline\{k\}\}\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종 스털링 수는 서로 역행렬 관계를 갖는다.^[1]

:$\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\}$는 크로네커 델타이다. 이 두 관계는 행렬 역관계로 이해될 수 있다.^[1]

6. 라 수 (Lah Numbers)

라 수(Lah numbers) $L(n,k)\; =\; \{n-1\; \backslash choose\; k-1\}\; \backslash frac\{n!\}\{k!\}$는 제3종 스털링 수라고도 불린다.^[4] 관례에 따라 $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^la)이라는 책에서 도입하였다.^[13][14] 닐스 닐센(Niels Nielsen)이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.^[14][15]

8. 기타

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

두 수열 $\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종 스털링 수와 관련된 다음 대칭 공식을 제시한다.^[7]

:$\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]



스털링 수는 음의 정수 값으로 확장될 수 있지만, 모든 저자가 동일한 방식으로 확장하는 것은 아니다.^[8][9][10] 제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 \}$을 정의했다.

참조

_[1] 서적 Concrete Mathematics Addison-Wesley 1988
_[2] 학술지 Two Notes on Notation https://www.jstor.or[...] 1992
_[3] 서적 A Course in Enumeration https://archive.org/[...] Springer
_[4] 서적 Handbook of Number Theory II https://books.google[...] Kluwer Academic Publishers
_[5] 문서 Concrete Mathematics exercise 13 of section 6. Note that this formula immediately implies the first positive-order Stirling number transformation given in the main article on [[generating function transformation#Derivative transformations|generating function transformations]].
_[6] 학술지 NIST Handbook of Mathematical Functions https://www.nist.gov[...] 2010
_[7] 간행물 Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 10th printing Dover
_[8] 학술지 A generalization of the Stirling numbers
_[9] 웹사이트 An extension of Stirling numbers http://www.fq.math.c[...] 1994-08
_[10] 문서 1992
_[11] 문서 Combinatorial Methods in Discrete Distributions John Wiley & Sons, Inc. 2005
_[12] 저널
_[13] 서적 http://gallica.bnf.f[...]
_[14] 저널
_[15] 서적 https://archive.org/[...]