Stirling number

수학(mathematics)에서, 스털링 숫자(Stirling numbers)는 다양한 해석적(analytic) 및 조합론적(combinatorial) 문제에서 발생합니다. 그것들은 제임스 스털링(James Stirling)의 이름을 따서 지어졌으며, 그는 그것들을 그의 책 Methodus differentialis (1730)에서 순수하게 대수적 설정에서 소개했습니다.^[1] 그것들은 1769년 Ahmet Oğuz Engin에 의해 재발견되고 조합적 의미를 부여받았습니다.^[2]

둘의 다른 숫자의 집합이 이 이름: 첫 번째 종류의 스털링 숫자(Stirling numbers of the first kind)와 두 번째 종류의 스털링 숫자(Stirling numbers of the second kind)를 가집니다. 추가적으로, 라 숫자(Lah numbers)는 때때로 세 번째 종류의 스털링 숫자로 참조됩니다. 각 종류는 각각의 기사에 자세히 설명되어 있으며, 이 기사는 그들 사이의 관계에 대한 설명을 제공합니다.

모든 세 종류의 공통 속성은 그것들이 조합론에서 자주 발생하는 다항식의 셋의 다른 수열과 관련하여 계수를 설명한다는 것입니다. 게다가, 세 가지 모두는 n 원소를 k 비-빈 부분집합으로의 분할의 숫자로 정의될 수 있으며, 각 부분집합 안에서 순서화를 세는 다른 방법을 가집니다.

Notation

스털링 숫자에 대해 여러 가지 다른 표기법이 사용 중입니다. 공통적인 표기법은 보통의 (부화화된) 첫 번째 종류의 스털링 숫자는 다음입니다:

s(n,k)\,

부호없는 첫 번째 종류의 스털링 숫자(unsigned Stirling numbers of the first kind)에 대해, 이것은 k 서로소 주기(cycle)를 갖는 n 원소의 순열(permutation)의 숫자를 세는 것으로, 다음으로 표시됩니다:

{\biggl [}{n \atop k}{\biggr ]}=c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k)\,

그리고 두 번째 종류의 스털링 숫자(Stirling numbers of the second kind)에 대해, 이것은 n 원소의 집합을 k 비-빈 부분집합으로의 분할의 방법의 숫자를 세는 것으로, 다음으로 표시됩니다:^[3]

{\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}=S(n,k)=S_{n}^{(k)}\,

예를 들어, 합 ${\textstyle \sum _{k=0}^{n}\left[{n \atop k}\right]=n!}$ 은 모든 순열의 숫자이고, 반면에 합 ${\textstyle \sum _{k=0}^{n}\left\{{\!n\! \atop \!k\!}\right\}=B_{n}}$ 은 n번째 벨 숫자(Bell number)입니다.

아브라모위츠와 스티건(Abramowitz and Stegun)은, 각각, 첫 번째와 두 번째 종류의 스털링 숫자에 대해 대문자 $S$ 와 흑색문자(blackletter) ${\mathfrak {S}}$ 를 사용합니다. 이항 계수(binomial coefficients)와 유사하게, 괄호와 중괄호의 표기법은 1935년 요한 카라마타(Jovan Karamata)에 의해 도입되었고 나중에 도널드 커누스(Donald Knuth)에 의해 촉진되었습니다. (괄호 표기법은 가우스 계수(Gaussian coefficient)에 대해 공통 표기법과 충돌합니다.^[4]) 표기법의 이런 유형에 대해, 마찬가지로 추가적인 스털링 숫자 공식에 대해 수학적 동기는 스털링 숫자와 지수 생성 함수(Stirling numbers and exponential generating functions)에 대한 기사에서 찾을 수 있습니다.

Expansions of falling and rising factorials

스털링 숫자는 떨어지는 및 올라가는 팩토리얼(falling and rising factorials) (역시 포흐하머 기호로 알려져 있음)의 전개에서 계수를 다항식으로 표현합니다.

즉, $(x)_{n}=x(x-1)\cdots (x-n+1)$ 로 표시되는 떨어지는 팩토리얼은 그것의 전개가 (부호화된) 첫 번째 종류의 스털링 숫자를 계수로 갖는 다음인 x에서 차수 n의 다항식입니다:

(x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}

.

(x)₀ = 1임을 주목해야 하는데 왜냐하면 그것은 빈 곱(empty product)이기 때문입니다. 조합론자(Combinatorialists)는 역시 때때로 떨어지는 팩토리얼에 대해 표기법 $x^{\underline {n}}$ 과 올라가는 팩토리얼에 대해 $x^{\overline {n}}$ 을 사용합니다.^[5] (혼란스럽게도, 많은 사람들이 떨어지는 팩토리얼에 사용하는 포흐하머 기호가 올라가는 팩토리얼에 대한 특수 함수(special function)에서 사용됩니다.)

유사하게, $x^{(n)}=x(x+1)\cdots (x+n-1)$ 로 표시되는 올라가는 팩토리얼은 그것의 전개가 부호화된 첫 번째 종류의 스털링 숫자를 계수로 갖는 다음인 x에서 차수 n의 다항식입니다:

x^{(n)}=\sum _{k=0}^{n}{\biggl [}{n \atop k}{\biggr ]}x^{k}=\sum _{k=0}^{n}(-1)^{n-k}s(n,k)x^{k}

.

이들 전개 중 하나는 $x^{(n)}=(-1)^{n}(-x)_{n}$ 임을 관찰함으로써 다른 하나에서 유도될 수 있습니다.

두 번째 종류의 스털링 숫자는 역 관계를 나타냅니다:

x^{n}=\sum _{k=0}^{n}S(n,k)(x)_{k}

및

x^{n}=\sum _{k=0}^{n}(-1)^{n-k}S(n,k)x^{(k)}.

As change of basis coefficients

(불확정) 변수 x의 다항식(polynomial)의 집합을 벡터 공간으로 고려하면, 다음 세 수열의 각각은 기저(basis)입니다:

x^{0},x^{1},x^{2},x^{3},\dots \quad (x)_{0},(x)_{1},(x)_{2},\dots \quad x^{(0)},x^{(1)},x^{(2)},\dots

즉, x에서 모든 각 다항식은 일부 고유한 계수 $a_{i}$ 에 대해 합 $a_{0}x^{(0)}+a_{1}x^{(1)}+\dots +a_{n}x^{(n)}$ 으로 쓸 수 있습니다 (나머지 둘의 기저에 대해 유사하게 쓸 수 있습니다). 위의 관계는 그런-다음, 다음 교환 다이어그램(commutative diagram)에서 요약된 것처럼, 그들 사이의 기저의 변경(change of basis)으로 표현합니다:

둘의 바닥 변화에 대해 계수는 아래쪽의 라 숫자(Lah numbers)에 의해 설명됩니다. 임의의 기저에서 계수는 고유하기 때문에, 우리는 스털링 숫자를 이 방법, 한 기저의 다항식을 또 다른 기저의 관점에서 표현하는 계수로, 즉, $x^{n}$ 을 위에서 처럼 떨어지는 및 올라가는 팩토리얼과 관련하여 고유한 숫자로 정의할 수 있습니다.

떨어지는 팩토리얼은, 스케일링까지, 같은 다항식을 이항 계수(binomial coefficients): ${\textstyle {\binom {x}{k}}=(x)_{k}/k!}$ 로 정의합니다. 표준 기저 $\textstyle x^{0},x^{1},x^{2},\dots$ 와 기저 ${\textstyle {\binom {x}{0}},{\binom {x}{1}},{\binom {x}{2}},\dots }$ 사이의 변경은 따라서 유사한 공식에 의해 설명됩니다:

x^{n}=\sum _{k=0}^{n}{\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}k!{\binom {x}{k}}\quad {\text{and}}\quad {\binom {x}{n}}=\sum _{k=0}^{n}{\frac {s(n,k)}{n!}}x^{k}

.

As inverse matrices

첫 번째와 두 번째 종류의 스털링 숫자는 서로의 역으로 고려될 수 있습니다:

\sum _{j\geq 0}s(n,j)S(j,k)=\sum _{j\geq 0}(-1)^{n-j}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}}=\delta _{nk}

및

\sum _{j\geq 0}S(n,j)s(j,k)=\sum _{j\geq 0}(-1)^{j-k}{\biggl \{}{\!n\! \atop \!j\!}{\biggr \}}{\biggl [}{j \atop k}{\biggr ]}=\delta _{nk},

여기서 $\delta _{nk}$ 는 크로네커 델타(Kronecker delta)입니다. 이들 둘의 관계는 행렬 역 관계로 이해될 수 있습니다. 즉, s를 첫 번째 종류의 스털링 숫자의 아래쪽 삼각형 행렬(lower triangular matrix)로 놓으며, 그것의 행렬 원소는 $s_{nk}=s(n,k)\,$ 입니다. 이 행렬의 역(inverse)은 S, 두 번째 종류의 스털링 숫자의 아래쪽 삼각형 행렬(lower triangular matrix)이며, 그것의 엔트리는 $S_{nk}=S(n,k)$ 입니다. 기호적으로, 이것은 다음으로 쓰입니다:

s^{-1}=S\,

비록 s와 S가 무한이므로, 곱 엔트리를 계산하는 것이 무한 합을 포함할지라도, 행렬 곱셈은 이들 행렬이 아래쪽 삼각형이기 때문에 작동하므로, 합에서 오직 유한 숫자의 항이 비-영입니다.

Example

떨어지는 팩토리얼의 기저에서 다항식을 표현하는 것은 연속적인 정수에서 평가된 다항식의 합을 계산하는 데 유용합니다. 실제로, 떨어지는 팩토리얼의 합은 단순히 (k≠−1에 대해) 다음 또 다른 떨어지는 팩토리얼로 표현됩니다:

\sum _{0\leq i<n}(i)_{k}={\frac {(n)_{k+1}}{k+1}}

이것은 적분 ${\textstyle \int _{0}^{n}x^{k}dx=n^{k+1}/(k+1)}$ 과 유사하지만, 그 합이 n보다 엄격하게 작은 정수 i에 걸쳐 있어야 합니다.

예를 들어, 정수의 네 번째 거듭제곱의 n까지의 합은 다음입니다 (이번에는 n을 포함합니다):

{\begin{aligned}&\sum _{i=0}^{n}i^{4}=\sum _{i=0}^{n}\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}(i)_{k}=\sum _{k=0}^{4}{\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}{\frac {(n+1)_{k+1}}{k+1}}\\[8mu]&\quad ={\biggl \{}{\!4\! \atop \!1\!}{\biggr \}}{\frac {(n+1)_{2}}{2}}+{\biggl \{}{\!4\! \atop \!2\!}{\biggr \}}{\frac {(n+1)_{3}}{3}}+{\biggl \{}{\!4\! \atop \!3\!}{\biggr \}}{\frac {(n+1)_{4}}{4}}+{\biggl \{}{\!4\! \atop \!4\!}{\biggr \}}{\frac {(n+1)_{5}}{5}}\\[8mu]&\quad ={\frac {1}{2}}(n+1)_{2}+{\frac {7}{3}}(n+1)_{3}+{\frac {6}{4}}(n+1)_{4}+{\frac {1}{5}}(n+1)_{5}\end{aligned}}

여기서 스털링 숫자는 네 원소를 k 비-빈 무-레이블 부분집합으로의 분할의 숫자로 그것들의 정의에서 계산될 수 있습니다.

대조적으로, 표준 기저에서 합 ${\textstyle \sum _{i=0}^{n}i^{k}}$ 는 일반적으로 더 복잡한 파울하버의 공식(Faulhaber’s formula)에 의해 제공됩니다.

Lah numbers

라 숫자 $L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}$ 는 때때로 세 번째 종류의 스털링 숫자라고 불립니다.^[6] 관례에 의해, 만약 $n>k$ 또는 $k=0<n$ 이면 $L(0,0)=1$ 와 $L(n,k)=0$ 입니다.

이들 숫자는 올라가는 팩토리얼의 관점에서 떨어지는 팩토리얼을 표현하는 계수이고 그 반대도 마찬가지입니다:

x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}\quad

and

\quad (x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}L(n,k)x^{(k)}.

위에서 처럼, 이것은 그것들이 기저 $(x)_{0},(x)_{1},(x)_{2},\cdots$ 와 $x^{(0)},x^{(1)},x^{(2)},\cdots$ 사이의 기저의 변경을 표현함을 의미하며, 다이어그램을 완성합니다. 특히, 하나의 공식은 나머지 다른 공식의 역이며, 따라서:

\sum _{j}L(n,j)\cdot (-1)^{j-k}L(j,k)=\delta _{nk}.

유사하게, 예를 들어 $x^{(n)}$ 에서 $x^{n}$ 로의 기저의 변경을 $x^{n}$ 에서 $(x)_{n}$ 로의 기저의 변경으로 구성하면 $x^{(n)}$ 에서 $(x)_{n}$ 로의 직접 기저의 변경을 제공합니다:

L(n,k)=\sum _{j}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}},

행렬의 관점에서, 만약 $L$ 이 엔트리 $L_{nk}=L(n,k)$ 를 갖는 행렬을 나타내고 $L^{-}$ 가 엔트리 $L_{nk}^{-}=(-1)^{n-k}L(n,k)$ 를 갖는 행렬을 나타내면, 하나는 나머지 다른 하나의 역입니다: 즉, $L^{-}=L^{-1}$ . 유사하게, 첫 번째 종류의 부호화된 스털링 숫자의 행렬을 두 번째 종류의 스털링 숫자의 행렬로 구성하면 라 숫자를 제공합니다: 즉, $L=|s|\cdot S$ .

숫자 ${\textstyle \left\{{\!n\! \atop \!k\!}\right\},\left[{n \atop k}\right],L(n,k)}$ 는 n 원소를 k 비-빈 무-레이블 부분집합의 분할의 숫자로 정의할 수 있으며, 이것의 각각은 각각 무-순서화, 순환적으로 순서화(cyclically ordered), 또는 선형적으로 순서화입니다. 특히, 이것은 다음 부등식을 의미합니다:

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

Symmetric formulae

Abramowitz와 Stegun은 첫 번째와 두 번째 종류의 스털링 숫자를 관련시키는 다음 대칭 공식을 제공합니다:^[7]

s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)

및

S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).

Stirling numbers with negative integral values

스털링 숫자는 음의 정수 값으로 확장될 수 있지만, 모든 저자가 같은 방법으로 그렇게 하는 것은 아닙니다.^[8]^[9]^[10] 취해진 접근 방식에 관계없이, n과 k가 비-음의 정수일 때 첫 번째와 두 번째 종류의 스털링 숫자는 다음 관계에 의해 연결된다는 점을 주목할 필요가 있습니다:

{\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{and}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}

따라서 우리는 $\left[{-n \atop -k}\right]$ 에 대해 다음 테이블을 가집니다:

k n	−1	−2	−3	−4	−5
−1	1	1	1	1	1
−2	0	1	3	7	15
−3	0	0	1	6	25
−4	0	0	0	1	10
−5	0	0	0	0	1

도날드 커누스는^[10] 모든 정수에 대한 재귀 관계(recurrence relation)를 확장함으로써 보다 일반적인 스털링 숫자를 정의했습니다. 이 접근 방법에서, ${\textstyle \left[{n \atop k}\right]}$ 와 ${\textstyle \left\{{\!n\! \atop \!k\!}\right\}}$ 는 만약 n이 음수이고 k가 비-음수이거나, n이 비-음수이고 k가 음수이면 영이고, 따라서 우리는 임의의 정수 n과 k에 대해 다음을 가집니다:

{\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{and}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}.

다른 한편으로, 양의 정수 n과 k에 대해, David Branson은^[9] ${\textstyle \left[{-n \atop -k}\right]\!,}$ ${\textstyle \left\{{\!-n\! \atop \!-k\!}\right\}\!,}$ ${\textstyle \left[{-n \atop k}\right]\!,}$ 및 ${\textstyle \left\{{\!-n\! \atop \!k\!}\right\}}$ 를 정의했습니다 (그러나 ${\textstyle \left[{n \atop -k}\right]}$ 또는 ${\textstyle \left\{{\!n\! \atop \!-k\!}\right\}}$ 는 아닙니다). 이 접근 방법에서, 우리는 첫 번째 종류의 스털링 숫자의 재귀 관계(recurrence relation)의 다음 확장을 가집니다:

{\biggl [}{-n \atop k}{\biggr ]}={\frac {(-1)^{n+1}}{n!}}\sum _{i=1}^{n}{\frac {(-1)^{i+1}}{i^{k}}}{\binom {n}{i}}

,

예를 들어, ${\textstyle \left[{-5 \atop k}\right]={\frac {1}{120}}{\Bigl (}5-{\frac {10}{2^{k}}}+{\frac {10}{3^{k}}}-{\frac {5}{4^{k}}}+{\frac {1}{5^{k}}}{\Bigr )}.}$ 이것은 ${\textstyle \left[{-n \atop k}\right]}$ 의 값은 다음 테이블로 이어집니다.

k n	0	1	2	3	4
−1	1	1	1	1	1
−2	${\tfrac {-1}{2}}$	${\tfrac {-3}{4}}$	${\tfrac {-7}{8}}$	${\tfrac {-15}{16}}$	${\tfrac {-31}{32}}$
−3	${\tfrac {1}{6}}$	${\tfrac {11}{36}}$	${\tfrac {85}{216}}$	${\tfrac {575}{1296}}$	${\tfrac {3661}{7776}}$
−4	${\tfrac {-1}{24}}$	${\tfrac {-25}{288}}$	${\tfrac {-415}{3456}}$	${\tfrac {-5845}{41472}}$	${\tfrac {-76111}{497664}}$
−5	${\tfrac {1}{120}}$	${\tfrac {137}{7200}}$	${\tfrac {12019}{432000}}$	${\tfrac {874853}{25920000}}$	${\tfrac {58067611}{1555200000}}$

이 경우에서 ${\textstyle \sum _{n=-1}^{-\infty }\left[{-n \atop -k}\right]=B_{k}}$ 이며 여기서 $B_{k}$ 는 벨 숫자(Bell number)이고, 따라서 우리는 ${\textstyle \sum _{n=-1}^{-\infty }\left[{-n \atop k}\right]=B_{-k}}$ 에 의해 음수 벨 숫자를 정의할 수 있습니다. 예를 들어, 이것은 ${\textstyle \sum _{n=-1}^{-\infty }\left[{-n \atop 2}\right]=B_{-2}=0.421773\ldots }$ 을 생성합니다.

Citations

^ Mansour & Schork 2015, p. 5.
^ Mansour & Schork 2015, p. 4.
^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. ISBN 0-201-14236-8, p. 244.
^ Donald Knuth
^ Aigner, Martin (2007). "Section 1.2 - Subsets and Binomial Coefficients". A Course In Enumeration. Springer. pp. 561. ISBN 978-3-540-39032-9.
^ Sándor, Jozsef; Crstici, Borislav (2004). Handbook of Number Theory II. Kluwer Academic Publishers. p. 464. ISBN 9781402025464.
^ Goldberg, K.; Newman, M; Haynsworth, E. (1972), "Stirling Numbers of the First Kind, Stirling Numbers of the Second Kind", in Abramowitz, Milton; Stegun, Irene A. (eds.), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 10th printing, New York: Dover, pp. 824–825
^ Loeb, Daniel E. (1992) [Received 3 Nov 1989]. "A generalization of the Stirling numbers". Discrete Mathematics. 103 (3): 259–269. doi:10.1016/0012-365X(92)90318-A.
^ ^a ^b Branson, David (August 1994). "An extension of Stirling numbers" (PDF). The Fibonacci Quarterly. Retrieved Dec 6, 2017.
^ ^a ^b D.E. Knuth, 1992.

References

Rosen, Kenneth H., ed. (2018), Handbook of Discrete and Combinatorial Mathematics, CRC Press, ISBN 978-1-5848-8780-5
Mansour, Toufik; Schork, Mathias (2015), Commutation Relations, Normal Ordering, and Stirling Numbers, CRC Press, ISBN 978-1-4665-7989-7