Stirling数
概要
Stirling数（Stirling numbers）とは、$n$ 元集合を $k$ 個の空でないブロックに分ける方法の個数である第 2 種 Stirling 数 $S(n,k)$ と、$n$ 文字の置換で巡回がちょうど $k$ 個のものの個数である符号なし第 1 種 Stirling 数 $c(n,k)$（符号をつけた $s(n,k)=(-1)^{n-k}c(n,k)$）の総称である。どちらも簡単な漸化式を満たし、冪 $x^n$ と下降・上昇階乗冪を互いに書き換える係数になるので、2 種類を並べた行列は互いに逆になる。指数型母関数は $(e^x-1)^k/k!$ などの形で表され、分割の総数である Bell 数の漸化式や級数表示も導かれる。$n!$ の近似を与える Stirling の公式とは別の主題である。
Stirling 数（Stirling numbers）は、集合の分割と置換の巡回を数える 2 種類の数で、それぞれ多項式の「ふつうの冪」と「階乗冪」を互いに書き換える係数になっている。$n$ 元集合を $k$ 個の空でないブロックに分ける方法の個数が 第 2 種 Stirling 数 $S(n,k)$、$n$ 文字の置換でちょうど $k$ 個の巡回をもつものの個数が 符号なし第 1 種 Stirling 数 $c(n,k)$ である。$n!$ の近似を与える Stirlingの公式 とは、同じ Stirling の名をもつが別の主題である。
この記事では、2 種類の Stirling 数を定義し、漸化式、冪と階乗冪の変換、2 種類の数を並べた行列が互いに逆であること（直交関係）、指数型母関数と通常母関数を証明する。最後に、集合の分割の総数である Bell 数の漸化式と、無限級数による表示（Dobiński の公式）を導く。
定義
$n\ge0$ について $[n]:=\{1,\dots,n\}$ とする（$[0]=\emptyset$）。$X$ の分割とは、$X$ の空でない部分集合（ブロック）の集合であって、どの 2 つも交わらず、和集合が $X$ になるものをいう。分割は $X$ 上の同値関係と一対一に対応する（ブロックが同値類）。ブロックの順序は区別しない。
$n,k\ge0$ について、$[n]$ の分割でブロックがちょうど $k$ 個のものの個数を $S(n,k)$ と書き、第 2 種 Stirling 数（Stirling number of the second kind）という。$[n]$ の分割の総数
$$
B_n:=\sum_{k=0}^{n}S(n,k)
$$
を Bell 数（Bell number）という。
空集合の分割は空集合 1 つだけ（ブロック $0$ 個）なので $S(0,0)=1$、$B_0=1$ である。$n\ge1$ なら $S(n,0)=0$ であり、ブロックは空でないので $k>n$ なら $S(n,k)=0$ である。
$[n]$ の置換 $\sigma$ を互いに素な巡回置換の積に分解し（置換 の記事の定理「互いに素な巡回置換の積への分解」）、不動点も長さ $1$ の巡回と数えた巡回の個数を $\operatorname{cyc}(\sigma)$ と書く。巡回は $\sigma$ が生成する部分群の $[n]$ への作用の軌道 $\{i,\sigma(i),\sigma^2(i),\dots\}$ であり、巡回全体は $[n]$ の分割をなす。
$n,k\ge0$ について、$[n]$ の置換 $\sigma$ で $\operatorname{cyc}(\sigma)=k$ となるものの個数を $c(n,k)$ と書き、符号なし第 1 種 Stirling 数（signless Stirling number of the first kind）という。
$$
s(n,k):=(-1)^{n-k}c(n,k)
$$
を（符号つきの）第 1 種 Stirling 数（Stirling number of the first kind）という。
$[0]$ の置換は空写像 1 つで巡回は $0$ 個なので $c(0,0)=1$ である。$n\ge1$ なら $c(n,0)=0$、$k>n$ なら $c(n,k)=0$ であり、すべての置換を巡回の個数で分けると $\sum_kc(n,k)=n!$ である。$\sigma$ の符号は $(-1)^{n-\operatorname{cyc}(\sigma)}$ に等しい（置換の符号 の記事の命題「符号の公式」の 2）ので、$s(n,k)$ は巡回が $k$ 個の置換の符号の和である。
変数 $x$ と $k\ge0$ について
$$
x^{\underline k}:=x(x-1)\cdots(x-k+1),\qquad x^{\overline k}:=x(x+1)\cdots(x+k-1)
$$
（どちらも $k$ 個の因子の積、$x^{\underline 0}=x^{\overline 0}:=1$）を、それぞれ $k$ 次の下降階乗冪、上昇階乗冪という。
$x^{\underline k}$ は正の整数 $x$ について、$k$ 元集合から $x$ 元集合への単射の個数である。記号には流儀があり、数列の和と差分 の記事は下降階乗冪を $x^{(k)}$ と書く。$(x)_k$ を下降・上昇のどちらに使うかも本によって違う。$S(n,k)$ を、$n$ と $k$ を上下に並べて波括弧でくくって書く流儀もある（節「補足」）。どちらの階乗冪も、$x$ を $-x$ に変えると
$$
(-x)^{\underline k}=(-1)^kx^{\overline k},\qquad(-x)^{\overline k}=(-1)^kx^{\underline k}
$$
となる（各因子から $-1$ をくくり出す）。
漸化式と表
$n\ge0$、$k\ge1$ について次が成り立つ。
- $S(n+1,k)=k\,S(n,k)+S(n,k-1)$
- $c(n+1,k)=n\,c(n,k)+c(n,k-1)$
1：$[n+1]$ の $k$ ブロックの分割を、元 $n+1$ の入り方で分ける。$\{n+1\}$ が単独でブロックをなすものは、それを除けば $[n]$ の $k-1$ ブロックの分割になり、この対応は全単射なので $S(n,k-1)$ 個ある。そうでないものは、$n+1$ を取り除くと $[n]$ の $k$ ブロックの分割が残り、逆に $[n]$ の $k$ ブロックの分割と、$n+1$ を入れるブロックの選び方（$k$ 通り）からもとの分割がただ 1 つ戻るので、$k\,S(n,k)$ 個ある。
2：$[n+1]$ の置換 $\sigma$ で巡回が $k$ 個のものを、$n+1$ が不動点かどうかで分ける。不動点なら、$[n]$ に制限すると巡回が $k-1$ 個の置換になり、この対応は全単射なので $c(n,k-1)$ 個ある。そうでないとき、$a:=\sigma^{-1}(n+1)\in[n]$ とし、$\sigma'(a):=\sigma(n+1)$、$i\ne a$ では $\sigma'(i):=\sigma(i)$ と定めると、$\sigma'$ は $n+1$ をその巡回から除いた $[n]$ の置換で、巡回の個数は $k$ のままである。逆に $[n]$ の置換 $\sigma'$ で巡回が $k$ 個のものと $a\in[n]$（$n$ 通り）から、$n+1$ を巡回の中で $a$ の直後に挿入する（$\sigma(a):=n+1$、$\sigma(n+1):=\sigma'(a)$）と $\sigma$ が戻る。2 つの対応は互いに逆なので、この場合は $n\,c(n,k)$ 個ある。$\square$
漸化式と $S(0,0)=c(0,0)=1$、$S(0,k)=c(0,k)=0$（$k\ge1$）、$S(n,0)=c(n,0)=0$（$n\ge1$）から、次の表が順に作れる。
| $n$ | $S(n,1),\dots,S(n,n)$ | $B_n$ | $c(n,1),\dots,c(n,n)$ | $n!$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1, 1 | 2 | 1, 1 | 2 |
| 3 | 1, 3, 1 | 5 | 2, 3, 1 | 6 |
| 4 | 1, 7, 6, 1 | 15 | 6, 11, 6, 1 | 24 |
| 5 | 1, 15, 25, 10, 1 | 52 | 24, 50, 35, 10, 1 | 120 |
| 6 | 1, 31, 90, 65, 15, 1 | 203 | 120, 274, 225, 85, 15, 1 | 720 |
たとえば $S(4,2)=7$ の分割は、$\{1\}\{2,3,4\}$ の型が $4$ 個、$\{1,2\}\{3,4\}$ の型が $3$ 個である。$c(4,2)=11$ の置換は、巡回の長さが $3,1$ のもの $8$ 個と、$2,2$ のもの $3$ 個である。$c(4,2)>S(4,2)$ となるのは、長さ $3$ の巡回の台 $\{a,b,c\}$ には巡回が $2$ つ（$(a\,b\,c)$ と $(a\,c\,b)$）あるからである。
漸化式から、$n\ge1$ について $S(n,1)=1$、$S(n,n)=1$、$S(n,2)=2^{n-1}-1$（$n\ge2$）、$S(n,n-1)=\binom n2$、$c(n,1)=(n-1)!$、$c(n,n-1)=\binom n2$ が帰納法で確かめられる。$S(n,2)$ は、$[n]$ を 2 つの空でない部分集合 $T$ と補集合に分ける方法の個数で、$T$ の選び方 $2^n-2$ 通りを $T$ と補集合の入れ替えで割った値としても得られる。
冪と階乗冪の変換
Stirling 数の最も基本的な性質は、冪 $x^n$ と階乗冪のあいだの書き換えの係数になることである。以下の等式は $\mathbb{Z}$ 係数の多項式としての等式である。
すべての $n\ge0$ について次が成り立つ。
- $x^{\overline n}=\displaystyle\sum_{k=0}^{n}c(n,k)\,x^k$
- $x^{\underline n}=\displaystyle\sum_{k=0}^{n}s(n,k)\,x^k$
- $x^n=\displaystyle\sum_{k=0}^{n}S(n,k)\,x^{\underline k}$
- $x^n=\displaystyle\sum_{k=0}^{n}(-1)^{n-k}S(n,k)\,x^{\overline k}$
1：$n$ についての帰納法による。$n=0$ では両辺とも $1$ である。$x^{\overline n}=\sum_kc(n,k)x^k$ を仮定すると
$$
x^{\overline{n+1}}=x^{\overline n}(x+n)=\sum_kc(n,k)x^{k+1}+\sum_kn\,c(n,k)x^k=\sum_{k}\bigl(c(n,k-1)+n\,c(n,k)\bigr)x^k
$$
であり、prop-sn-recurrence の 2 により係数は $c(n+1,k)$ である（$k=0$ の係数は $n\,c(n,0)$ で、$n=0$ でも $n\ge1$ でも $0=c(n+1,0)$ に等しい）。
2：1 で $x$ を $-x$ に変え、階乗冪の符号の入れ替え（def-sn-factorial-powers の後の等式）を使うと $(-1)^nx^{\underline n}=\sum_kc(n,k)(-1)^kx^k$ である。両辺に $(-1)^n$ を掛ければよい。
3：正の整数 $x$ について、$[n]$ から $[x]$ への写像 $f$ を、ファイバーの空でないもの $\{f^{-1}(y)\mid y\in f([n])\}$ が作る $[n]$ の分割で分類する。ブロックが $k$ 個の分割を 1 つ固定すると、それを与える $f$ は、$k$ 個のブロックに相異なる値を割り当てる方法、すなわち $k$ 元集合から $[x]$ への単射と一対一に対応し、$x^{\underline k}$ 個ある。写像は全部で $x^n$ 個なので、すべての正の整数 $x$ で $x^n=\sum_kS(n,k)x^{\underline k}$ が成り立つ。両辺の差は無限に多くの根をもつ多項式なので $0$ であり、多項式として等しい。
4：3 で $x$ を $-x$ に変え、階乗冪の符号の入れ替え（def-sn-factorial-powers の後の等式）を使うと $(-1)^nx^n=\sum_kS(n,k)(-1)^kx^{\overline k}$ である。両辺に $(-1)^n$ を掛ければよい。$\square$
表の $n=3$ の行から $x^3=x^{\underline 3}+3x^{\underline 2}+x^{\underline 1}$ であり、実際 $x(x-1)(x-2)+3x(x-1)+x=x^3$ である。逆向きには $x^{\underline 3}=x^3-3x^2+2x$、$x^{\overline 3}=x^3+3x^2+2x$ である。数列の和と差分 の記事は、3 の展開と下降階乗冪の和の公式を組み合わせて、冪の和 $\sum_{j=0}^{N-1}j^m$ を求めている（定理「べきの下降階乗冪展開」と定理「べき和の公式」）。
2 の両辺に $x=1$ を代入すると、$n\ge2$ では $1^{\underline n}=0$ なので $\sum_ks(n,k)=0$ である。$s(n,k)$ は巡回が $k$ 個の置換の符号の和なので、これは $n\ge2$ のとき符号が $+1$ の置換と $-1$ の置換が同じ個数あることを述べている。
2 と 3 を合わせると、2 種類の Stirling 数を並べた行列が互いに逆であることが分かる。$\delta_{nm}$ は $n=m$ なら $1$、そうでなければ $0$ を表す。
すべての $n,m\ge0$ について
$$
\sum_{k}S(n,k)\,s(k,m)=\delta_{nm},\qquad\sum_{k}s(n,k)\,S(k,m)=\delta_{nm}
$$
である（和は $m\le k\le n$ の範囲の有限和）。
thm-sn-conversion の 3 の右辺の $x^{\underline k}$ に 2 を代入すると
$$
x^n=\sum_kS(n,k)\sum_ms(k,m)x^m=\sum_m\Bigl(\sum_kS(n,k)s(k,m)\Bigr)x^m
$$
である。$1,x,x^2,\dots$ は多項式の空間の基底なので、係数を比べて前半を得る。$x^{\underline m}$ は最高次の係数が $1$ の $m$ 次の多項式なので、$1,x^{\underline1},x^{\underline2},\dots$ も基底である。2 の右辺の $x^k$ に 3 を代入して $x^{\underline n}=\sum_m\bigl(\sum_ks(n,k)S(k,m)\bigr)x^{\underline m}$ を得るので、同じく係数を比べて後半を得る。$\square$
$R$ を可換環とし、$(a_n)_{n\ge0}$、$(b_n)_{n\ge0}$ を $R$ の元の列とする。次の 2 条件は同値である。
- すべての $n\ge0$ について $b_n=\sum_{k=0}^nS(n,k)\,a_k$
- すべての $n\ge0$ について $a_n=\sum_{k=0}^ns(n,k)\,b_k$
1 を仮定すると、cor-sn-orthogonality の後半により
$$
\sum_ks(n,k)b_k=\sum_ks(n,k)\sum_jS(k,j)a_j=\sum_j\Bigl(\sum_ks(n,k)S(k,j)\Bigr)a_j=a_n
$$
である。逆も前半を使って同様に示せる。$\square$
たとえばすべての $k$ で $a_k:=1$ とすると、1 の右辺は $\sum_kS(n,k)=B_n$ なので、2 から $\sum_{k=0}^ns(n,k)B_k=1$（$n\ge0$）が従う。$n=3$ では $2\cdot1-3\cdot2+1\cdot5=1$ である。
生成関数
この節では $\mathbb{Q}$ 係数の形式的冪級数を使う（収束は問わない）。$(a_n)$ の指数型母関数 $\sum_na_nx^n/n!$ は 母関数 の記事の定義「通常母関数と指数型母関数」のものである。定数項が $0$ の級数 $A$ について $A^k$ は $x^k$ より低い次数の項をもたないので、$\exp(A):=\sum_{k\ge0}A^k/k!$ は係数ごとに有限和として定まる。$e^x:=\sum_nx^n/n!$ とする。
集合を $k$ 個のブロックに分け、各ブロックに何かの構造を載せる方法の個数は、次の補題で数えられる。
各有限集合 $T$ に有限集合 $\mathcal F(T)$ が対応し、その元の個数 $f_{\lvert T\rvert}$ は $T$ の元の個数だけで決まり、$f_0=0$ であるとする。$\hat F(x):=\sum_{m\ge1}f_mx^m/m!$ とおく。$[n]$ の $k$ ブロックの分割 $\pi$ と、各ブロック $T\in\pi$ ごとの元 $\alpha_T\in\mathcal F(T)$ の組 $(\pi,(\alpha_T)_T)$ の個数を $h_{n,k}$ とすると
$$
\sum_{n\ge0}h_{n,k}\frac{x^n}{n!}=\frac{\hat F(x)^k}{k!}
$$
である。
ブロックに番号を付けた組 $(T_1,\dots,T_k)$（$T_i$ は空でなく互いに交わらず、和集合が $[n]$）と $\alpha_i\in\mathcal F(T_i)$ の組を数える。大きさ $\lvert T_i\rvert=n_i$（$n_1+\dots+n_k=n$、$n_i\ge1$）を決めると、$(T_1,\dots,T_k)$ の選び方は多項係数 $\frac{n!}{n_1!\cdots n_k!}$ 通りで、$\alpha_i$ の選び方は $f_{n_1}\cdots f_{n_k}$ 通りである。よって個数は
$$
\sum_{n_1+\dots+n_k=n}\frac{n!}{n_1!\cdots n_k!}f_{n_1}\cdots f_{n_k}=n!\,[x^n]\hat F(x)^k
$$
である（$f_0=0$ なので $n_i=0$ の項は消える）。ブロックは空でなく互いに交わらないので相異なり、番号の付け方を忘れると、1 つの組 $(\pi,(\alpha_T)_T)$ にちょうど $k!$ 個の番号付きの組が対応する。よって $h_{n,k}=n![x^n]\hat F^k/k!$ である。$\square$
$L(x):=\sum_{m\ge1}x^m/m$ とおく。$k\ge0$ について次が成り立つ。
- $\displaystyle\sum_{n\ge0}S(n,k)\frac{x^n}{n!}=\frac{(e^x-1)^k}{k!}$
- $\displaystyle\sum_{n\ge0}c(n,k)\frac{x^n}{n!}=\frac{L(x)^k}{k!}$
- $\displaystyle\sum_{n\ge0}B_n\frac{x^n}{n!}=\exp(e^x-1)$
1：lem-sn-blocks で、空でない $T$ について $\mathcal F(T)$ を 1 元集合とする。$f_m=1$（$m\ge1$）で $\hat F=e^x-1$、$h_{n,k}=S(n,k)$ である。
2：$\mathcal F(T)$ を、$T$ の置換で $T$ 全体が 1 つの巡回になるもの全体とする。$\lvert T\rvert=m\ge1$ のとき、巡回 $(t_1\,t_2\,\cdots\,t_m)$ は $t_1$ を $T$ の最小元にとると、残りの並べ方 $(m-1)!$ 通りと一対一に対応するので、$f_m=(m-1)!$ で $\hat F=\sum_m(m-1)!x^m/m!=L(x)$ である。$[n]$ の置換は、巡回の台が作る分割と、各ブロックの上の 1 つの巡回の組と一対一に対応する（置換 の記事の定理「互いに素な巡回置換の積への分解」の一意性）。巡回が $k$ 個の置換は、ブロック $k$ 個の分割に対応するので、$h_{n,k}=c(n,k)$ である。
3：$B_n=\sum_kS(n,k)$ で、$k>n$ では $S(n,k)=0$ なので、1 を $k\ge0$ について足し合わせればよい。$\square$
$L(x)$ は解析的には $-\log(1-x)$ である。1 から $S(n,k)$ の明示式が出る。
$n,k\ge0$ について
$$
S(n,k)=\frac1{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom kj j^n
$$
である（$0^0:=1$）。とくに右辺は $k>n$ では $0$ になる。
$e^{jx}:=\sum_n j^nx^n/n!$ とおくと、指数型母関数の積の規則（母関数 の記事の命題「指数型母関数の積」）と二項定理 $\sum_i\binom ni j^il^{n-i}=(j+l)^n$ により $e^{jx}e^{lx}=e^{(j+l)x}$ であり、$(e^x)^j=e^{jx}$ である。二項定理で $(e^x-1)^k=\sum_j\binom kj(-1)^{k-j}e^{jx}$ と展開し、$x^n/n!$ の係数を比べると thm-sn-egf の 1 から主張を得る。$k>n$ のときは左辺が $0$ である。$\square$
$k!\,S(n,k)$ は $[n]$ から $[k]$ への全射の個数であり、この式は 数え上げ組合せ論 の記事の命題「全射の個数と明示式」で包除原理から導かれた式と同じものである。第 1 種で $n$ を固定して $k$ を動かす母関数は thm-sn-conversion の 1 の $\sum_kc(n,k)x^k=x^{\overline n}$ である。第 2 種で $k$ を固定して $n$ を動かす通常母関数は次の形になる。
$k\ge0$ について
$$
\sum_{n\ge0}S(n,k)\,x^n=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}
$$
である（$k=0$ では右辺は $1$）。
左辺を $G_k(x)$ とおくと $G_0=1$ である。$k\ge1$ では $S(0,k)=0$ なので、prop-sn-recurrence の 1 の両辺に $x^{n+1}$ を掛けて $n\ge0$ で足すと $G_k=kx\,G_k+x\,G_{k-1}$、すなわち $(1-kx)G_k=xG_{k-1}$ である。$1-kx$ は形式的冪級数として可逆なので $G_k=\frac{x}{1-kx}G_{k-1}$ であり、$k$ についての帰納法で主張を得る。$\square$
Bell 数
Bell の三角形、Touchard の合同式、大きさの評価など Bell 数そのものの性質は Bell数 の記事で扱い、ここでは Stirling 数から従う漸化式と Dobiński の公式を示す。
$n\ge0$ について $B_{n+1}=\sum_{i=0}^{n}\binom ni B_i$ である。
$[n+1]$ の分割を、$n+1$ を含むブロック $T$ で分ける。$[n]\setminus T$ の元の個数を $i$ とすると、その $i$ 個の選び方は $\binom ni$ 通り（二項係数）で、残りの分割は $[n]\setminus T$ の分割で $B_i$ 通りある。逆にこの 2 つを決めれば分割がただ 1 つ定まる。$i$ について足せばよい。$\square$
$n\ge0$ について
$$
B_n=\frac1e\sum_{j=0}^{\infty}\frac{j^n}{j!}
$$
である（右辺の級数は収束する）。
要点：cor-sn-explicit を $k\ge0$ について足し、$j$ と $k-j$ の二重級数として並べ替える。
詳しい証明を開く
cor-sn-explicit により $k>n$ では $S(n,k)=0$ なので $$ B_n=\sum_{k=0}^{\infty}S(n,k)=\sum_{k=0}^{\infty}\ \sum_{j+l=k}\frac{j^n}{j!}\cdot\frac{(-1)^l}{l!} $$ である（$\frac1{k!}\binom kj=\frac1{j!\,l!}$、$l=k-j$）。右辺は 2 つの級数 $\sum_jj^n/j!$ と $\sum_l(-1)^l/l!$ の Cauchy 積である。前者は比 $\frac{(j+1)^n/(j+1)!}{j^n/j!}=\frac{(1+1/j)^n}{j+1}\to0$ なので絶対収束し、後者は $e^{-1}$ に絶対収束する。絶対収束する 2 つの級数の Cauchy 積は、それぞれの和の積に収束するので、$B_n=e^{-1}\sum_jj^n/j!$ である。$\square$
確率の言葉では、平均 $1$ の Poisson分布 に従う確率変数 $Y$（$P(Y=j)=e^{-1}/j!$）について $B_n=E[Y^n]$ である。thm-sn-conversion の 3 を $x=Y$ に当てて期待値をとると、$E[Y^{\underline k}]=\sum_{j\ge k}\frac{e^{-1}}{(j-k)!}=1$ からも同じ式が出る。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| ブロックの順序を区別しない | $[3]$ を、ブロックに 1 番目・2 番目の順序を付けて 2 つに分ける | 個数が $S(3,2)=3$ に等しい（実際は $2!\,S(3,2)=6$） |
| ブロックの元を区別する | $4$ を 2 つの正の整数の和に分ける（$3+1$、$2+2$） | 個数が $S(4,2)=7$ に等しい（実際は $2$。分割数 の数え方） |
| 直交関係で符号つきの $s(k,m)$ を使う | $n=2$、$m=1$ で符号なしの $c$ を使う | $\sum_kS(2,k)c(k,1)=1+1=2$ が $\delta_{21}=0$ に等しい |
| thm-sn-conversion の 3 で下降階乗冪を使う | $n=2$ で上昇階乗冪に替える | $x^2=\sum_kS(2,k)x^{\overline k}$（右辺は $x^{\overline1}+x^{\overline2}=x^2+2x$） |
2 行目は、元を区別しない整数の分割（分割数）と、元を区別する集合の分割の違いである。3 行目で、符号を付けない $c(n,k)$ を並べた行列は $S(n,k)$ の行列の逆行列にならない。4 行目の正しい形は thm-sn-conversion の 4 の、符号 $(-1)^{n-k}$ の付いた式である。
補足
- 名前と記号：$s(n,k)$ を第 1 種、$c(n,k)$ を符号なし第 1 種、$S(n,k)$ を第 2 種と呼ぶ呼び方と記号は Sta11 §1.3（p. 32）・§1.9（p. 81）による。$S(n,k)$ を波括弧で書く記号は Karamata にならって Knuth が勧めたものである（FS09 §II.3, p. 109）。級数による Bell 数の表示は Dobiński（1877）による（FS09 §II.3, p. 110）。
- 組合せ論の中の位置：$S(n,k)$ と $B_n$ は、$n$ 個の区別できる玉を区別できない箱に入れる数え方に当たり、数え上げ組合せ論 の記事の定義「第2種Stirling数とBell数」と同じものである。$c(n,k)$ は、Pólyaの数え上げ定理 の記事の例「対称群と重複組合せ」でも、$\sum_\sigma m^{\operatorname{cyc}(\sigma)}=m^{\overline n}$ の係数として現れる。
- 差分との関係：下降階乗冪は差分作用素 $\Delta f(x)=f(x+1)-f(x)$ について $\Delta x^{\underline k}=kx^{\underline{k-1}}$ を満たすので、thm-sn-conversion の 3 は冪の和の計算に使える（数列の和と差分）。
- 文献：漸化式は Sta11 Lemma 1.3.6（p. 32）と式 (1.93)（p. 82）、冪と階乗冪の変換は Proposition 1.3.7（式 (1.28)、p. 33）と式 (1.94d)・(1.96)（pp. 82–83）、直交関係と反転は Proposition 1.9.1（p. 84）、明示式・母関数・Bell 数の漸化式は式 (1.94a)–(1.94f)（p. 82）にある。指数型母関数による扱いは FS09 §II.3（pp. 109–110）にもある。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
