スターリング数

\( \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. \]


戻る