スターリング数

\( \newcommand{\stirlingI}{\genfrac[]{0pt}{}} % 第1種スターリング数 \newcommand{\stirlingII}{\genfrac\{\}{0pt}{}} % 第2種スターリング数 \newcommand{\risingFactorial}[2]{{#1}^{\overline{#2}}} \newcommand{\fallingFactorial}[2]{{#1}^{\underline{#2}}} \)次のような記号を導入する：

\begin{align*} \risingFactorial{x}{n}&:=x(x+1)\dotsb(x+n-1), \\ \fallingFactorial{x}{n}&:=x(x-1)\dotsb(x-n+1). \end{align*} 自然数 \(n\) と \(k\) について、第1種スターリング数 \(\stirlingI{n}{k}\) と第2種スターリング数 \(\stirlingII{n}{k}\) を次の関係式により定める。 \begin{align*} \risingFactorial{x}{n}&=\sum_{k=0}^n \stirlingI{n}{k} x^k, \qquad \fallingFactorial{x}{n}=\sum_{k=0}^n \stirlingI{n}{k} (-1)^{n-k} x^k, \\ x^n&=\sum_{k=0}^n \stirlingII{n}{k} \fallingFactorial{x}{k} =\sum_{k=0}^n \stirlingII{n}{k} (-1)^{n-k} \risingFactorial{x}{k} \end{align*} スターリング数は次の漸化式によって計算できる： \begin{align*} \stirlingI{0}{k}&=\begin{cases} 1 & (k=0) \\ 0 & (k\ne 0) \end{cases} & \stirlingII{0}{k}&=\begin{cases} 1 & (k=0) \\ 0 & (k\ne 0) \end{cases} \\ \stirlingI{n+1}{k}&=\stirlingI{n}{k-1}+n\stirlingI{n}{k}, & \stirlingII{n+1}{k}&=\stirlingII{n}{k-1}+k\stirlingII{n}{k}. \end{align*}

第1種スターリング数

\(\stirlingI{n}{k}\)	\(k=0\)	1	2	3	4	5	6	7
\(n=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

\begin{align*} \stirlingI{n}{0}&=\begin{cases} 1 & (n=0) \\ 0 & (n\ne 0), \end{cases} \\ \stirlingI{n}{1}&=\begin{cases} 0 & (n=0) \\ (n-1)! & (n\ne 0), \end{cases} \\ \stirlingI{n}{n-1}&=\frac{n(n-1)}{2}, \\ \stirlingI{n}{n}&=1. \end{align*}

\(p\) が素数の時、 \[ \stirlingI{p}{k}\equiv \begin{cases} 0 & (k\ne1,p) \\ -1 & (k=1) \\ 1 & (k=p) \end{cases} \mod p. \]

第2種スターリング数

\(\stirlingII{n}{k}\)	\(k=0\)	1	2	3	4	5	6	7
\(n=0\)	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1

\begin{align*} \stirlingII{n}{0}&=\begin{cases} 1 & (n=0) \\ 0 & (n\ne 0), \end{cases} \\ \stirlingII{n}{1}&=\begin{cases} 0 & (n=0) \\ 1 & (n\ne 0), \end{cases} \\ \stirlingII{n}{2}&=\begin{cases} 0 & (n=0) \\ 2^{n-1}-1 & (n\ne 0), \end{cases} \\ \stirlingII{n}{n-1}&=\frac{n(n-1)}{2}, \\ \stirlingII{n}{n}&=1. \end{align*}

\(p\) が素数の時、 \[ \stirlingII{p}{k}\equiv \begin{cases} 0 & (k\ne1,p) \\ 1 & (k=1,p) \end{cases} \mod p. \]

（参考）二項係数

\(\binom{n}{k}\)	\(k=0\)	1	2	3	4	5	6	7
\(n=0\)	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1

\(p\) が素数の時、 \[ \binom{p}{k}\equiv \begin{cases} 0 & (k\ne 0,p) \\ 1 & (k=0,p) \end{cases} \mod p. \]

---

戻る