Stirling numbers of the first kind

Original article: w:Stirling numbers of the first kind

수학(mathematics), 특히 조합론(combinatorics)에서, 첫 번째 종류의 스털링 숫자(Stirling numbers of the first kind)는 순열의 연구에서 발생합니다. 특히, 첫 번째 종류의 스털링 숫자는 주기(cycles)의 숫자에 따라 순열(permutation)을 셉니다 (고정 점을 길이 1의 주기로 셉니다).

첫 번째와 두 번째 종류의 스털링 숫자는 삼각 행렬(triangular matrices)로 볼 때 서로의 역으로 이해될 수 있습니다. 이 기사는 첫 번째 종류의 스털링 숫자에 대해 자세히 설명합니다. 두 종류를 연결하는 항등식은 일반적으로 스털링 숫자(Stirling numbers)에 관한 기사에 나와 있습니다.

Definitions

첫 번째 종류의 스털링 숫자의 원래 정의는 대수적이었습니다: 그것들은 다음 떨어지는 팩토리얼(falling factorial)

$(x)_{n}=x(x-1)(x-2)\cdots (x-n+1)$

를 변수 $x$의 거듭제곱으로 전개할 때 계수 $s(n,k)$입니다:

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

예를 들어, $(x)_{3}=x(x-1)(x-2)=x^{3}-3x^{2}+2x$, 값 $s(3,3)=1$, $s(3,2)=-3$, 및 $s(3,1)=2$로 이어집니다.

결과적으로, 이들 숫자의 절댓값 $|s(n,k)|$은 특정 종류의 순열(permutations)의 숫자와 같다는 것이 발견되었습니다. 첫 번째 종류의 부호-없는 스털링 숫자로 알려진 이들 절댓값은 종종 $c(n,k)$ 또는 $\left[{n \atop k}\right]$로 표시됩니다. 그것들은 $k$개의 서로소 주기를 갖는 $n$개 원소의 순열의 숫자로 직접 정의될 수 있습니다. 예를 들어, 3개 원소의 $3!=6$ 순열 중, 3개의 주기(cycles)를 갖는 하나의 순열 (항등 순열, $123$에 의해 한-줄 표기법 또는 $(1)(2)(3)$에 의해 주기 표기법으로 제공됨), 2주기를 갖는 3개 순열 ($132=(1)(23)$, $213=(12)(3)$, 및 $213=(12)(3)$), 및 1주기의 2개 순열 ($312=(132)$와 $231=(123)$)가 있습니다. 따라서, $\left[{3 \atop 2}\right]=3$, $\left[{3 \atop 2}\right]=3$, 및 $\left[{3 \atop 1}\right]=2$. 이것들은 $n=3$에 대한 $s(n,k)$의 이전 계산과 일치하는 것으로 볼 수 있습니다. Alfréd Rényi는 부호-없는 스털링 숫자 $\left[{n \atop k}\right]$가 $k$ 왼쪽에서-오른쪽으로 최댓값을 갖는 크기 $n$의 순열의 숫자도 계산한다는 사실을 관찰했습니다.

부호-없는 스털링 숫자는 올라가는 팩토리얼(rising factorial)의 계수로 대수적으로 정의될 수도 있습니다:

$x^{\overline {n}}=x(x+1)\cdots (x+n-1)=\sum _{k=0}^{n}\left[{n \atop k}\right]x^{k}$.

스털링 숫자에 대해 이 페이지에서 사용된 표기법은 보편적이지 않고, 다른 출처의 표기법과 충돌할 수 있습니다. (대괄호 표기법 $\left[{n \atop k}\right]$도 가우스 계수에 대한 공통적인 표기법입니다.)

Definition by permutation

$\left[{n \atop k}\right]$는 $k$ 주기를 갖는 $n$ 원소에 대한 순열의 숫자로 정의될 수 있습니다.

s(4,2)=11

오른쪽에 있는 이미지는 $\left[{4 \atop 2}\right]=11$임을 보여줍니다; 4 대상에 대한 대칭 그룹(symmetric group)은 다음 형식의 3 순열을 가지고

$(\bullet \bullet )(\bullet \bullet )$ (having 2 orbits, each of size 2),

다음 형식의 8 순열을 가집니다:

$(\bullet \bullet \bullet )(\bullet )$ (having 1 orbit of size 3 and 1 orbit of size 1).

이들 숫자는 궤도를 켤레 클래스 (마지막 글머리 기호)로 고려함으로써 계산될 수 있습니다.

Signs

첫 번째 종류의 (부호-있는) 스털링 숫자의 부호는 예측 가능하고 n − k의 패리티에 따라 달라집니다. 특히,

$s(n,k)=(-1)^{n-k}\left[{n \atop k}\right].$

Recurrence relation

첫 번째 종류의 부호-없는 스털링 숫자는 $k>0$에 대해 다음과 같은 재귀 관계(recurrence relation)에 의해 계산될 수 있습니다:

$\left[{n+1 \atop k}\right]=n\left[{n \atop k}\right]+\left[{n \atop k-1}\right]$

이때, $n>0$에 대해 다음 초기 조건을 가집니다:

$\left[{0 \atop 0}\right]=1\quad {\mbox{and}}\quad \left[{n \atop 0}\right]=\left[{0 \atop n}\right]=0$

첫 번째 종류의 (부호-있는) 스털링 숫자가 다음 재귀를 만족시킨다는 것은 바로 이어집니다:

$s(n+1,k)=-n\cdot s(n,k)+s(n,k-1)$.

Algebraic proof

우리는 올라가는 팩토리얼의 관점에서 스털링 숫자의 정의를 사용하여 재귀 관계를 입증합니다. 곱의 마지막 항을 분배하여, 다음을 가집니다:

$x^{\overline {n+1}}=x(x+1)\cdots (x+n-1)(x+n)=n\cdot x^{\overline {n}}+x\cdot x^{\overline {n}}.$

이 방정식의 왼쪽 변에서 $x^{k}$의 계수는 $\left[{n+1 \atop k}\right]$. $n\cdot x^{\overline {n}}$에서 $x^{k}$의 계수는 $n\cdot \left[{n \atop k}\right]$이지만, $x\cdot x^{\overline {n}}$에서 $x^{k}$의 계수는 $\left[{n \atop k-1}\right]$입니다. 두 변이 다항식으로 같기 때문에, 양쪽 변에서 $x^{k}$의 계수는 같아야 하고, 그 결과가 따라옵니다.

Combinatorial proof

우리는 주어진 숫자의 주기 (또는 동등하게, 궤도)를 갖는 순열의 관점에서 스털링 숫자의 정의를 사용하여 재귀 관계를 입증합니다.

구별되는 대상을 추가함으로써 $n$ 대상의 순열에서 $n+1$ 대상의 순열을 형성하는 것을 생각해 보십시오. 이것이 달성될 수 있는 정확히 두 개의 방법이 있습니다. 우리는 한원소 주기를 형성함으로써, 즉, 여분의 대상을 단독으로 남김으로써 이를 수행할 수 있습니다. 이것은 주기의 숫자를 1만큼 증가시키고 따라서 재귀 공식에서 $\left[{n \atop k-1}\right]$ 항을 설명합니다. 우리는 기존 주기 중 하나에 새로운 대상을 삽입할 수도 있습니다. $k$ 주기를 갖는 $n$ 대상의 임의적인 순열을 고려하고 그 순열이 다음에 의해 표현되도록 대상 $a_{1},\dots ,a_{n}$에 레이블을 지정합니다:

$\displaystyle \underbrace {(a_{1}\ldots a_{j_{1}})(a_{j_{1}+1}\ldots a_{j_{2}})\ldots (a_{j_{k-1}+1}\ldots a_{n})} _{k\ \mathrm {cycles} }.$

$n+1$ 대상과 $k$ 주기의 새로운 순열을 형성하기 위해, 새로운 대상을 이 배열에 삽입해야 합니다. 이 삽입을 수행하기 위해 $n$ 방법이 있는데, 이미 존재하는 $a_{i}$ 바로 뒤에 새로운 대상을 삽입합니다. 이것은 재귀 관계의 $n\left[{n \atop k}\right]$ 항을 설명합니다. 이들 두 가지 경우는 모든 가능성을 포함하므로, 재귀 관계가 따릅니다.

Table of values

아래는 형태가 파스칼의 삼각형(Pascal's triangle)과 유사한 첫 번째 종류의 스털링 숫자에 대한 부호-없는 값의 삼각형 배열(triangular array)입니다. 이들 값은 이전 섹션의 재귀 관계를 사용하여 쉽게 생성하는 것이 쉽습니다.

k n	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

Properties

Simple identities

비록 다음이지만, 그 뒤의 내용을 주목하십시오:

$\left[{0 \atop 0}\right]=1$

우리는 n > 0이면 $\left[{n \atop 0}\right]=0$임을 가집니다.

그리고

만약 k > 0이면, $\left[{0 \atop k}\right]=0$, 또는 보다 일반적으로 k > n이면 $\left[{n \atop k}\right]=0$.

역시

$\left[{n \atop 1}\right]=(n-1)!,\quad \left[{n \atop n}\right]=1,\quad \left[{n \atop n-1}\right]={n \choose 2},$

그리고

$\left[{n \atop n-2}\right]={\frac {1}{4}}(3n-1){n \choose 3}\quad {\mbox{ and }}\quad \left[{n \atop n-3}\right]={n \choose 2}{n \choose 4}.$

스털링 숫자와 관련된 유사한 관계가 베르누이 다항식(Bernoulli polynomials)에 대해 유지됩니다. 스털링 숫자에 대한 많은 관계는 이항 계수(binomial coefficients)에서 유사한 관계를 나타냅니다. 이들 '그림자 관계'에 대한 연구는 움브랄 미적분(umbral calculus)이라고 이름-짓고 셰퍼 수열(Sheffer sequences)의 이론에서 절정에 이릅니다. 임의적인 복소-값 입력에 대한 두 종류의 스털링 숫자(Stirling numbers)의 일반화는 이들 삼각형과 스털링 합성곱 다항식(Stirling convolution polynomials)의 관계를 통해 확장될 수 있습니다.

Combinatorial proofs

이들 항등식은 순열을 직접 열거함으로써 유도될 수 있습니다. 예를 들어, n − 3 주기를 갖는 "n" 원소의 순열은 다음 형식 중 하나를 가져야 합니다:

• n − 6 고정된 점과 3개의 2-주기
• n − 5 고정된 점, 하나의 3-주기와 하나의 2-주기, 또는
• n − 4 고정된 점과 하나의 4-주기.

세 가지 유형은 다음과 같이 열거될 수 있습니다:

• 2-주기에 들어가는 6개의 원소를 선택하고, 2-주기로 분해하고 주기의 순서가 중요하지 않다는 점을 고려하십시오:

${n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}$

• 3-주기와 2-주기에 들어가는 5개의 원소를 선택하고, 3-주기의 원소를 선택하고 3개의 원소가 2개의 3-주기를 생성한다는 점을 고려하십시오:

${n \choose 5}{5 \choose 3}\times 2$

• 4-주기의 4개 원소를 선택하고 4개의 원소가 6개의 4-주기를 생성한다는 점을 고려하십시오:

${n \choose 4}\times 6.$

세 개의 부분을 합해서 다음을 얻습니다:

${n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}+{n \choose 5}{5 \choose 3}\times 2+{n \choose 4}\times 6={n \choose 2}{n \choose 4}.$

위의 모든 조합론적 증명은 $n$의 이항 또는 다항을 사용함을 주목하십시오.

그러므로 만약 $p$가 소수이면, 다음과 같습니다:

$p|\left[{p \atop k}\right]$ for $1<k<p$.

Other relations

Expansions for fixed k

스털링 숫자는 근 0, 1, ..., n − 1을 갖는 다항식의 계수이기 때문에, 비에타의 공식(Vieta's formulas)에 의해 다음을 가집니다:

$$\left[{\begin{matrix}n\\n-k\end{matrix}}\right]=\sum _{0\leq i_{1}<i_{2}<\ldots <i_{k}<n}i_{1}i_{2}\cdots i_{k}.$$

다시 말해서, 첫 번째 종류의 스털링 숫자는 0, 1, ..., n − 1에서 평가되는 기본 대칭 다항식(elementary symmetric polynomials)에 의해 제공됩니다. 이 형식에서, 위에 주어진 단순 항등식은 다음 형식을 취합니다:

$$\left[{\begin{matrix}n\\n-1\end{matrix}}\right]=\sum _{i=0}^{n-1}i={\binom {n}{2}},$$ $$\left[{\begin{matrix}n\\n-2\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}ij={\frac {3n-1}{4}}{\binom {n}{3}},$$$$\left[{\begin{matrix}n\\n-3\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}\sum _{k=0}^{j-1}ijk={\binom {n}{2}}{\binom {n}{4}},$$ 그리고 이런 식으로 계속됩니다.

우리는 약간의 대수적 조작에 의해 선행되는 유사한 접근 방식을 갖는 첫 번째 종류의 스털링 숫자에 대한 대안적인 형식을 생성할 수 있습니다: 다음이기 때문에,

$(x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot (x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right),$

일반화된 조화 숫자(generalized harmonic numbers)의 관점에서 첫 번째 종류의 스털링 숫자를 확장할 수 있다는 것은 뉴턴의 공식(Newton's formulas)에서 따라옵니다. 이것은 다음과 같은 항등식을 생성합니다:

$\left[{n \atop 2}\right]=(n-1)!\;H_{n-1},$

$\left[{n \atop 3}\right]={\frac {1}{2}}(n-1)!\left[(H_{n-1})^{2}-H_{n-1}^{(2)}\right]$

$\left[{n \atop 4}\right]={\frac {1}{3!}}(n-1)!\left[(H_{n-1})^{3}-3H_{n-1}H_{n-1}^{(2)}+2H_{n-1}^{(3)}\right],$

여기서 H_n은 조화 숫자(harmonic number) $H_{n}={\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}$이고 H_n^(m)은 다음과 같은 일반화된 조화 숫자입니다: $$H_{n}^{(m)}={\frac {1}{1^{m}}}+{\frac {1}{2^{m}}}+\ldots +{\frac {1}{n^{m}}}.$$

이들 관계는 다음을 제공하기 위해 일반화될 수 있습니다:

${\frac {1}{(n-1)!}}\left[{\begin{matrix}n\\k+1\end{matrix}}\right]=\sum _{i_{1}=1}^{n-1}\sum _{i_{2}=i_{1}+1}^{n-1}\cdots \sum _{i_{k}=i_{k-1}+1}^{n-1}{\frac {1}{i_{1}i_{2}\cdots i_{k}}}={\frac {w(n,k)}{k!}}$

여기서 w(n, m)은 다음에 의해 일반화된 조화 숫자의 관점에서 재귀적으로 정의됩니다:

$w(n,m)=\delta _{m,0}+\sum _{k=0}^{m-1}(1-m)_{k}H_{n-1}^{(k+1)}w(n,m-1-k).$

(여기서 δ는 크로네커 델타 함수(Kronecker delta function)이고 $(m)_{k}$는 포흐하머 기호(Pochhammer symbol)입니다.)

고정된 $n\geq 0$에 대해, 이들 가중된 조화 숫자 전개는 다음 생성하는 함수에 의해 생성됩니다:

${\frac {1}{n!}}\left[{\begin{matrix}n+1\\k\end{matrix}}\right]=[x^{k}]\exp \left(\sum _{m\geq 1}{\frac {(-1)^{m-1}H_{n}^{(m)}}{m}}x^{m}\right),$

여기서 표기법 $[x^{k}]$는 다음 형식적 거듭제곱 급수에서 $x^{k}$의 계수의 추출을 의미합니다 (비-지수 벨 다항식과 의 섹션 3 참조).

보다 일반적으로, 첫 번째 종류의 스털링 숫자의 이들 가중된 조화 숫자 전개와 관련된 합계는 생성하는 함수의 일반화된 제타 급수 변환을 통해 정의될 수 있습니다.

우리는 역시 $k$-차수 조화 숫자의 관점에서 주어진 이들 스털링 숫자에 대해 첫 번째 종류의 스털링 숫자를 포함하는 항의 가중된 합의 관점에서 정수-차수 일반화된 조화 숫자를 작성하기 위해 "반전"할 수 있습니다. 예를 들어, $k=2,3$일 때, 2-차와 3-차 조화 숫자는 다음과 같이 지정됩니다:

$(n!)^{2}\cdot H_{n}^{(2)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{2}-2\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]$

$(n!)^{3}\cdot H_{n}^{(3)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{3}-3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\2\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]+3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]^{2}\left[{\begin{matrix}n+1\\4\end{matrix}}\right].$

보다 일반적으로, 정수 $m\geq 2$에 대해 다음임을 얻기 위해 $m$-차 조화 숫자(harmonic numbers)의 관점에서 확장된 스털링 숫자에 대한 벨 다항식(Bell polynomial) 생성하는 함수를 반전할 수 있습니다.

$H_{n}^{(m)}=-m\times [x^{m}]\log \left(1+\sum _{k\geq 1}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\frac {(-x)^{k}}{n!}}\right).$

Factorial-related sums

모든 양의 정수 m과 n에 대해, 다음을 가집니다:

$$(n+m)!=\sum _{k=0}^{n}\sum _{j=0}^{m}m^{\overline {n-k}}\left[{m \atop j}\right]{\binom {n}{k}}k!,$$

여기서 $a^{\overline {b}}=a(a+1)\cdots (a+b-1)$는 올라가는 팩토리얼입니다. 이 공식은 벨 숫자(Bell numbers)에 대한 스파이비의 결과(Spivey's result)의 이중입니다.

떨어지는 팩토리얼, 첫 번째 종류의 스털링 숫자, 및 경우에 따라 두 번째 종류의 스털링 숫자(Stirling numbers of the second kind)와 관련된 다른 관련된 공식은 다음과 같습니다:

$${\begin{aligned}n^{\underline {n-m}}&=\sum _{k}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}(-1)^{m-k}\\{\binom {n}{m}}(n-1)^{\underline {n-m}}&=\sum _{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}\\{\binom {n}{m}}&=\sum _{k}\left\{{\begin{matrix}n+1\\k+1\end{matrix}}\right\}\left[{\begin{matrix}k\\m\end{matrix}}\right](-1)^{m-k}\\\left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]&=\sum _{0\leq k\leq n}\left[{\begin{matrix}k\\m\end{matrix}}\right]n^{\underline {n-k}}.\end{aligned}}$$

Inversion relations and the Stirling transform

모든 정수 $n\geq 0$에 의해 다음에 의해 주어진 유한 합 스털링 숫자 공식과 관련된, 임의의 수열의 쌍, $\{f_{n}\}$와 $\{g_{n}\}$에 대해,

$g_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}f_{k},$

우리는 다음에 의해 주어진 $f_{n}$에 대한 대응하는 반전 공식(inversion formula)을 가지고 있습니다:

$f_{n}=\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right](-1)^{n-k}g_{k}.$

두 수열 사이의 이들 반전 관계는 다음과 같은 스털링 (생성 함수) 변환에 의해 주어진 수열 지수 생성 함수 사이의 함수형 방정식으로 변환됩니다:

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

그리고

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

미분 연산자(differential operators) $D=d/dz$와 $\vartheta =zD$는 모든 정수 $n\geq 0$에 대해 다음 공식과 관련됩니다:

$\vartheta ^{n}=\sum _{k}S(n,k)z^{k}D^{k}$

$z^{n}D^{n}=\sum _{k}s(n,k)\vartheta ^{k}$

스털링 숫자를 포함하는 또 다른 한 쌍의 "반전" 관계는 함수 $f(x)$의 순방향 차이(forward differences)와 보통의 $n^{th}$ 도함수(derivatives)와 관련되며, 이는 다음 공식에 의해 모든 $x$에 대해 해석적입니다:

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

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

Congruences

다음 합동 항등식은 생성 함수-기반 접근 방식을 통해 입증될 수 있습니다:

${\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&\equiv {\binom {\lfloor n/2\rfloor }{m-\lceil n/2\rceil }}=[x^{m}]\left(x^{\lceil n/2\rceil }(x+1)^{\lfloor n/2\rfloor }\right)&&{\pmod {2}},\end{aligned}}$

단일 팩토리얼 함수와 일반화된 팩토리얼-관련 곱을 생성하는 야코비-유형 J-분수를 제공하는 보다 최근의 결과는 첫 번째 종류의 스털링 숫자에 대한 다른 새로운 합동 결과로 이어집니다. 예를 들어, 모듈로 2로 작업하면, 다음을 입증할 수 있습니다:

${\begin{aligned}\left[{\begin{matrix}n\\1\end{matrix}}\right]&\equiv {\frac {2^{n}}{4}}[n\geq 2]+[n=1]&&{\pmod {2}}\\\left[{\begin{matrix}n\\2\end{matrix}}\right]&\equiv {\frac {3\cdot 2^{n}}{16}}(n-1)[n\geq 3]+[n=2]&&{\pmod {2}}\\\left[{\begin{matrix}n\\3\end{matrix}}\right]&\equiv 2^{n-7}(9n-20)(n-1)[n\geq 4]+[n=3]&&{\pmod {2}}\\\left[{\begin{matrix}n\\4\end{matrix}}\right]&\equiv 2^{n-9}(3n-10)(3n-7)(n-1)[n\geq 5]+[n=4]&&{\pmod {2}}\\\left[{\begin{matrix}n\\5\end{matrix}}\right]&\equiv 2^{n-13}(27n^{3}-279n^{2}+934n-1008)(n-1)[n\geq 6]+[n=5]&&{\pmod {2}}\\\left[{\begin{matrix}n\\6\end{matrix}}\right]&\equiv {\frac {2^{n-15}}{5}}(9n^{2}-71n+120)(3n-14)(3n-11)(n-1)[n\geq 7]+[n=6]&&{\pmod {2}},\end{aligned}}$

그리고 모듈로 3으로 작업하면 유사하게 다음을 입증할 수 있습니다:

${\begin{aligned}\left[{\begin{matrix}n\\1\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{36}}\left(9-5j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 2]+[n=1]&&{\pmod {3}}\\\left[{\begin{matrix}n\\2\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{216}}\left((44n-41)-(25n-24)\cdot j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 3]+[n=2]&&{\pmod {3}}\\\left[{\begin{matrix}n\\3\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{15552}}\left((1299n^{2}-3837n+2412)-(745n^{2}-2217n+1418)\cdot j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 4]+[n=3]&&{\pmod {3}}\\\left[{\begin{matrix}n\\4\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{179936}}{\bigl (}(6409n^{3}-383778n^{2}+70901n-37092)-(3690n^{3}-22374n^{2}+41088n-21708)\cdot j{\sqrt {3}}{\bigr )}\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 5]+[n=4]&&{\pmod {3}}.\end{aligned}}$

더 일반적으로, 고정된 정수 $h\geq 3$에 대해 만약 우리가 순서화된 근을 다음과 같이 정의하면:

$\left(\omega _{h,i}\right)_{i=1}^{h-1}:=\left\{\omega _{j}:\sum _{i=0}^{h-1}{\binom {h-1}{i}}{\frac {h!}{(i+1)!}}(-\omega _{j})^{i}=0,\ 1\leq j<h\right\},$

우리는 다음과 같은 계수로 정의된 이들 스털링 숫자에 대한 합동을 확장할 수 있습니다:

$\left[{\begin{matrix}n\\m\end{matrix}}\right]=[R^{m}]R(R+1)\cdots (R+n-1),$

이때, 함수 $p_{h,i}^{[m]}(n)$은 각 $h$, $m$, 및 $i$에 대해 $n$에서 차수 $m$의 고정된 다항식을 나타냅니다:

$\left[{\begin{matrix}n\\m\end{matrix}}\right]=\left(\sum _{i=0}^{h-1}p_{h,i}^{[m]}(n)\times \omega _{h,i}^{n}\right)[n>m]+[n=m]\qquad {\pmod {h}},$

위에 인용된 참고 문헌의 섹션 6.2는 $r$-차수 조화 숫자(harmonic numbers)와 일반화된 팩토리얼 곱(generalized factorial products) $p_{n}(\alpha ,R):=R(R+\alpha )\cdots (R+(n-1)\alpha )$에 대해 이들 합동과 관련된 보다 명확한 전개를 제공합니다. 이전 예제에서, 표기법 $[{\mathtt {cond}}]$는 아이버슨의 관례(Iverson's convention)를 나타냅니다.

Generating functions

다양한 항등식은 생성 함수를 조작함으로써 유도될 수 있습니다 (기저의 변경을 참조):

$H(z,u)=(1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}s(n,k)u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}s(n,k).$

다음 상등을 사용하여

$(1+z)^{u}=e^{u\log(1+z)}=\sum _{k=0}^{\infty }(\log(1+z))^{k}{\frac {u^{k}}{k!}},$

다음일을 따릅니다:

$\sum _{n=k}^{\infty }(-1)^{n-k}\left[{n \atop k}\right]{\frac {z^{n}}{n!}}={\frac {\left(\log(1+z)\right)^{k}}{k!}}.$

(이 항등식은 형식적 거듭제곱 급수(formal power series)에 대해 유효하고, 합은 |z| < 1에 대해 복소 평면(complex plane)에서 수렴합니다.) 다른 항등식은 합의 순서를 교환하고, 도함수를 취하고, z 또는 u, 등을 대체함으로써 발생합니다. 예를 들어, 우리는 다음을 도출할 수 있습니다:

$(1-z)^{-u}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}\left[{n \atop k}\right]=e^{u\log(1/(1-z))}$

그리고

${\frac {\log ^{m}(1+z)}{1+z}}=m!\sum _{k=0}^{\infty }{\frac {s(k+1,m+1)\,z^{k}}{k!}},\qquad m=1,2,3,\ldots \quad |z|<1$

또는

$\sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(n!)}}=\zeta (i+1),\qquad i=1,2,3,\ldots$

그리고

$\sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(v)_{n}}}=\zeta (i+1,v),\qquad i=1,2,3,\ldots \quad \Re (v)>0$

여기서 $\zeta (k)$와 $\zeta (k,v)$는 각각 리만 제타 함수(Riemann zeta function)와 후르비츠 제타 함수(Hurwitz zeta function)이고, 심지어 이 적분을 평가합니다:

$\int _{0}^{1}{\frac {\log ^{z}(1-x)}{x^{k}}}\,dx={\frac {(-1)^{z}\Gamma (z+1)}{(k-1)!}}\sum _{r=1}^{k-1}s(k-1,r)\sum _{m=0}^{r}{\binom {r}{m}}(k-2)^{r-m}\zeta (z+1-m),\qquad \Re (z)>k-1,\quad k=3,4,5,\ldots$

여기서 $\Gamma (z)$는 감마 함수(gamma function)입니다. 스털링 숫자를 포함하는 제타 함수에 대한 더 복잡한 표현도 존재합니다. 예를 들어, 다음을 가집니다:

${\frac {k!}{(s-k)_{k}}}\sum _{n=0}^{\infty }{\frac {1}{(n+k)!}}\left[{n+k \atop n}\right]\sum _{l=0}^{n+k-1}\!(-1)^{l}{\binom {n+k-1}{l}}(l+v)^{k-s}=\zeta (s,v),\quad k=1,2,3,\ldots$

이 급수는 후르비츠 제타-함수(Hurwitz zeta-function)에 대한 하세의 급수를 일반화합니다 (우리는 k=1을 설정함으로써 하세의 급수를 얻습니다).

Asymptotics

오일러 감마 상수(Euler gamma constant)의 관점에서 주어진 다음 추정이 적용됩니다:

$\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]\sim {\frac {n!}{k!}}\left(\gamma +\ln n\right)^{k},\ {\text{ uniformly for }}k=o(\ln n).$

고정된 $n$에 대해, 우리는 $k\longrightarrow \infty$일 때 다음 추정을 가집니다:

$\left[{\begin{matrix}n+k\\k\end{matrix}}\right]\sim {\frac {k^{2n}}{2^{n}n!}}.$

우리는 역시 첫 번째 종류의 스털링 숫자에 대한 다른 추정을 얻기 위해 Temme의 기사에서 안장 점 점근적 방법을 적용할 수 있습니다. 이들 추정은 설명하기가 더 뒤얽혀 있고 복잡합니다. 그럼에도 불구하고, 우리는 예를 제공합니다. 특히, 우리는 로그 감마 함수(log gamma function) $\phi (x)$를 정의합니다. 이 함수의 고차 도함수는 다중-감마 함수(polygamma functions)의 관점에서 다음으로 지정됩니다:

${\begin{aligned}\phi (x)&=\ln \left[(1+1)(x+2)\cdots (x+n)\right]-m\ln x\\&=\ln \Gamma (x+n+1)-\ln \Gamma (x+1)-m\ln x\\\phi ^{\prime }(x)&=\psi (x+n+1)-\psi (x+1)-m/x,\end{aligned}}$

여기서 우리는 함수의 (고유한) 안장 점 $x_{0}$을 $1\leq m\leq n$일 때 $\phi ^{\prime }(x)=0$의 해로 고려합니다. 그런-다음 $t_{0}=m/(n-m)$와 다음 상수에 대해

$B=\phi (x_{0})-n\ln(1+t_{0})+m\ln t_{0}$

$g(t_{0})={\frac {1}{x_{0}}}{\sqrt {\frac {m(n-m)}{n\phi ^{\prime \prime }(x_{0})}}},$

우리는 $n\longrightarrow \infty$일 때 다음과 같은 점근적 추정을 가집니다:

$\left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]\sim e^{B}g(t_{0}){\binom {n}{m}}.$

Finite sums

순열은 주기의 숫자로 분할되기 때문에, 다음을 가집니다:

$\sum _{k=0}^{n}\left[{n \atop k}\right]=n!$

다음 항등식은

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

스털링 숫자와 지수 생성 함수 페이지의 기술에 의해 입증될 수 있습니다.

Concrete Mathematics의 섹션 6.1에서 테이블은 스털링 숫자를 포함하는 유한 합의 일반화된 형식을 제공합니다. 이 기사와 관련된 몇 가지 특정 유한 합은 다음을 포함합니다:

${\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&=\sum _{k}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\binom {k}{m}}(-1)^{m-k}\\\left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]&=\sum _{k=0}^{n}\left[{\begin{matrix}k\\m\end{matrix}}\right]{\frac {n!}{k!}}\\\left[{\begin{matrix}m+n+1\\m\end{matrix}}\right]&=\sum _{k=0}^{m}(n+k)\left[{\begin{matrix}n+k\\k\end{matrix}}\right]\\\left[{\begin{matrix}n\\l+m\end{matrix}}\right]{\binom {l+m}{l}}&=\sum _{k}\left[{\begin{matrix}k\\l\end{matrix}}\right]\left[{\begin{matrix}n-k\\m\end{matrix}}\right]{\binom {n}{k}}.\end{aligned}}$

예를 들어 NIST Handbook of Mathematical Functions (Section 26.8)에서 발견된 첫 번째 종류의 부호-있는 스털링 숫자를 포함하는 다른 유한 합 항등식은 다음 합을 포함합니다:

${\begin{aligned}{\binom {k}{h}}s(n,k)&=\sum _{j=k-h}^{n-h}{\binom {n}{j}}s(n-j,h)s(j,k-h)\\s(n+1,k+1)&=n!\times \sum _{j=k}^{n}{\frac {(-1)^{n-j}}{j!}}s(j,k)\\s(n,n-k)&=\sum _{j=0}^{k}(-1)^{j}{\binom {n-1+j}{k+j}}{\binom {n+k}{k-j}}S(k+j,j)\\s(n,k)&=\sum _{j=k}^{n}s(n+1,j+1)n^{j-k}.\end{aligned}}$

추가적으로, 만약 우리가 삼각 재귀 관계에 의해 2-차 오일러 숫자를 정의하면,

$E_{2}(n,k)=(k+1)E_{2}(n-1,k)+(2n-1-k)E_{2}(n-1,k-1)+\delta _{n,0}\delta _{k,0},$

우리는 두 스털링 숫자 삼각형을 입력 $x$의 임의적인 실수, 또는 복소-값으로 일반화하기 위해 사용될 수 있는 스털링 합성곱 다항식(Stirling convolution polynomials)의 형식과 관련된 다음 항등식에 도달합니다:

$\left[{\begin{matrix}x\\x-n\end{matrix}}\right]=\sum _{k}E_{2}(n,k){\binom {x+k}{2n}}.$

이전 항등식의 특정 전개는 $n:=1,2,3$의 처음 몇 개의 작은 값에 대해 첫 번째 종류의 스털링 숫자를 확장하는 다음 항등식으로 이어집니다:

${\begin{aligned}\left[{\begin{matrix}x\\x-1\end{matrix}}\right]&={\binom {x}{2}}\\\left[{\begin{matrix}x\\x-2\end{matrix}}\right]&={\binom {x}{4}}+2{\binom {x+1}{4}}\\\left[{\begin{matrix}x\\x-3\end{matrix}}\right]&={\binom {x}{6}}+8{\binom {x+1}{6}}+6{\binom {x+2}{6}}.\end{aligned}}$

스털링 숫자와 오일러 숫자를 포함하는 유한 합계 작업을 위한 소프트웨어 도구는 Mathematica의 RISC Stirling.m package 유틸리티에 의해 제공됩니다. 스털링 숫자와 기타 특수 삼각형을 포함하는 수열 (및 다항식 수열 합)에 대한 공식을 추측하기 위한 다른 소프트웨어 패키지는 각각 여기 및 여기에서 Mathematica 및 Sage에서 사용할 수 있습니다.

게다가, 스털링 숫자를 갖는 유한 합을 포함하는 무한 급수는 종종 특수 함수로 이어집니다. 예를 들어:

$\sum _{n=1}^{\infty }\!{\frac {(-1)^{n-1}}{n}}\cdot {\frac {1}{n!}}\sum _{l=1}^{n}\!{\frac {s(n,l)}{l+k}}=\sum _{l=2}^{\infty }\!{\frac {(-1)^{l}\cdot \zeta (l)}{l+k-1}}={\frac {1}{k-1}}-{\frac {\ln 2\pi }{k}}+{\frac {\gamma }{2}}+\!\!\!\!\sum _{l=1}^{\lfloor {\frac {1}{2}}(k-1)\rfloor }\!\!\!\!(-1)^{l}{\binom {k-1}{2l-1}}{\frac {(2l)!\cdot \zeta '(2l)}{l\cdot (2\pi )^{2l}}}+\!\!\sum _{l=1}^{\lfloor {\frac {1}{2}}k\rfloor -1}\!\!(-1)^{l}{\binom {k-1}{2l}}{\frac {(2l)!\cdot \zeta (2l+1)}{2\cdot (2\pi )^{2l}}}$

또는

$\ln \Gamma (z)=\left(z-{\frac {1}{2}}\right)\!\ln z-z+{\frac {1}{2}}\ln 2\pi +{\frac {1}{\pi }}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor {\frac {1}{2}}n\rfloor }\!{\frac {(-1)^{l}(2l)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]$

그리고

$\Psi (z)=\ln z-{\frac {1}{2z}}-{\frac {1}{\pi z}}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor {\frac {1}{2}}n\rfloor }\!{\frac {(-1)^{l}(2l+1)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]$

또는 심지어

$\gamma _{m}={\frac {1}{2}}\delta _{m,0}+{\frac {(-1)^{m}m!}{\pi }}\!\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{k=0}^{\lfloor {\frac {1}{2}}n\rfloor }{\frac {(-1)^{k}}{(2\pi )^{2k+1}}}\left[{2k+2 \atop m+1}\right]\left[{n \atop 2k+1}\right]\,$

여기서 γ_m은 스틸티어스 상수(Stieltjes constants)이고 δ_m,0은 크로네커 델타 함수(Kronecker delta function)를 나타냅니다.

Explicit formula

스털링 숫자 s(n,n-p)는 공식에서 찾을 수 있습니다:

${\begin{aligned}s(n,n-p)&={\frac {1}{(n-p-1)!}}\sum _{0\leq k_{1},\ldots ,k_{p}:\sum _{1}^{p}mk_{m}=p}(-1)^{K}{\frac {(n+K-1)!}{k_{1}!k_{2}!\cdots k_{p}!~2!^{k_{1}}3!^{k_{2}}\cdots (p+1)!^{k_{p}}}},\end{aligned}}$

여기서 $K=k_{1}+\cdots +k_{p}$입니다. 그 합은 p의 모든 분할(partitions)에 걸쳐 합입니다.

이들 스털링 숫자에 대한 또 다른 정확한 중첩 합 확장은 $(1+c_{1}x)\cdots (1+c_{n-1}x)$ 형식의 곱의 $x$에서 계수에 해당하는 기본 대칭 다항식(elementary symmetric polynomials)으로 계산됩니다. 특히, 우리는 다음임을 압니다:

${\begin{aligned}\left[{\begin{matrix}n\\k+1\end{matrix}}\right]&=[x^{k}](x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot [x^{k}](x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right)\\&=\sum _{1\leq i_{1}<\cdots <i_{k}<n}{\frac {(n-1)!}{i_{1}\cdots i_{k}}}.\end{aligned}}$

위의 확장과 결합된 뉴턴의 항등식(Newton's identities)은 위에서 이미 언급한 일반화된 조화 숫자(harmonic numbers)를 포함하는 가중된 확장의 대안적인 증명을 제공하기 위해 사용될 수 있습니다.

$n$의 역수 거듭제곱(reciprocal powers)에 대한 또 다른 명시적 공식은 정수 $p\geq 2$에 대한 다음 항등식에 의해 제공됩니다:

${\frac {1}{n^{p}}}={\frac {1}{n^{p-1}}}+{\frac {(-1)^{p-1}}{n!}}\left({\begin{bmatrix}n\\p\end{bmatrix}}+{\begin{bmatrix}n\\p-1\end{bmatrix}}\right)+{\frac {(-1)^{p}}{n\cdot n!}}{\begin{bmatrix}n+1\\p\end{bmatrix}}+\sum _{j=0}^{p-3}{\begin{bmatrix}n+1\\j+2\end{bmatrix}}{\frac {(-1)^{j+1}(n-1)}{n^{p-1-j}\cdot n!}}.$

이 마지막 항등식은 다중로그(polylogarithm) 함수, 위에 주어진 스털링 숫자 지수 생성 함수, 및 일반화된 닐센 다중로그 함수에 대한 스털링-숫자-기반 거듭제곱 급수 사이의 관계를 즉시 암시하는 것에 주목하십시오.

Relations to natural logarithm function

자연 로그(natural logarithm)의 μ-번째 거듭제곱의 n-번째 도함수(derivative)는 부호-있는 첫 번째 종류의 스털링 숫자를 포함합니다:

${\operatorname {d} ^{n}\!(\ln x)^{\mu } \over \operatorname {d} \!x^{n}}=x^{-n}\sum _{k=1}^{n}\mu ^{\underline {k}}s(n,n-k+1)(\ln x)^{\mu -k},$

여기서 $\mu ^{\underline {i}}$는 떨어지는 팩토리얼(falling factorial)이고, $s(n,n-k+1)$는 부호-있는 스털링 숫자입니다.

그것은 수학적 귀납법(mathematical induction)을 사용함으로써 입증될 수 있습니다.

Generalizations

다양한 조합론적 맥락에서 (응용에 따라) 정의될 수 있는 일반화된 스털링 숫자의 많은 개념이 있습니다. 첫 번째 종류의 스털링 숫자는 단일 팩토리얼 함수(single factorial function) $n!=n(n-1)(n-2)\cdots 2\cdot 1$의 구별되는 다항식 전개의 계수에 해당하므로, 우리는 이 개념을 곱의 보다 일반적인 클래스에 대한 삼각형 재귀 관계를 정의하기 위해 확장할 수 있습니다.

특히, 임의의 고정된 산술 함수 $f:\mathbb {N} \rightarrow \mathbb {C}$와 기호 매개변수 $x,t$에 대해, 다음 형식의 관련된 일반화된 팩토리얼 곱은

$(x)_{n,f,t}:=\prod _{k=1}^{n-1}\left(x+{\frac {f(k)}{t^{k}}}\right)$

$(x)_{n,f,t}$의 전개에서 $x$의 거듭제곱의 다음 계수와 그런-다음 그 다음의 대응하는 삼각형 재귀 관계에 의해 정의된 첫 번째 종류의 일반화된 스털링 숫자의 클래스의 관점에서 연구될 수 있습니다:

${\begin{aligned}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{f,t}&=[x^{k-1}](x)_{n,f,t}\\&=f(n-1)t^{1-n}\left[{\begin{matrix}n-1\\k\end{matrix}}\right]_{f,t}+\left[{\begin{matrix}n-1\\k-1\end{matrix}}\right]_{f,t}+\delta _{n,0}\delta _{k,0}.\end{aligned}}$

이러한 계수는 f-조화 숫자, $F_{n}^{(r)}(t):=\sum _{k\leq n}t^{k}/f(k)^{r}$와 관련된 재귀 관계와 함수형 방정식뿐만 아니라 첫 번째 종류의 스털링 숫자에 대한 것과 유사한 여러 속성을 만족시킵니다.

$t\equiv 1$에 해당하는 이들 괄호로 묶인 계수의 한 가지 특별한 경우는 배수 팩토리얼, 또는 다중-팩토리얼(multifactorial) 함수를 $n$에서 다항식으로 확장할 수 있도록 합니다 (이중 팩토리얼의 일반화를 참조하십시오).

두 종류의 스털링 숫자, 이항 계수, 및 1차 오일러 숫자와 2차 오일러 숫자는 모두 다음 형식의 삼각형 초월-재귀(super-recurrence)의 특수한 경우로 정의됩니다:

$\left|{\begin{matrix}n\\k\end{matrix}}\right|=(\alpha n+\beta k+\gamma )\left|{\begin{matrix}n-1\\k\end{matrix}}\right|+(\alpha ^{\prime }n+\beta ^{\prime }k+\gamma ^{\prime })\left|{\begin{matrix}n-1\\k-1\end{matrix}}\right|+\delta _{n,0}\delta _{k,0},$

이때 $n,k\geq 0$는 정수이고, 여기서 $n<0$ 또는 $k<0$일 때마다 $\left|{\begin{matrix}n\\k\end{matrix}}\right|\equiv 0$입니다. 이러한 의미에서, 첫 번째 종류의 스털링 숫자의 형태는 고정된 스칼라 $\alpha ,\beta ,\gamma ,\alpha ^{\prime },\beta ^{\prime },\gamma ^{\prime }$ (모두 0이 아님)에 대한 이 매개변수화된 초월-재귀에 의해 일반화될 수도 있습니다.

See also

• Stirling polynomials
• Stirling numbers
• Stirling numbers of the second kind
• Random permutation statistics

References

• The Art of Computer Programming
• Concrete Mathematics
• M. Abramowitz, I. Stegun, ed. (1972). "§24.1.3. Stirling Numbers of the First Kind". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (9th ed.). New York: Dover. p. 824.
• Stirling numbers of the first kind, s(n,k) at PlanetMath.org..
• Sloane, N. J. A. (ed.). "Sequence A008275 (Triangle read by rows of Stirling numbers of first kind)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.