第二種 Stirling 数の一般化

第二種 Stirling 数の一般化である associated Stirling number of the second kind についてのメモ。

本記事を通し $[n]=\{1,\cdots,n\}$ と表します。

第二種 Stirling 数

まず第二種 Stirling 数とは何なのかを簡単に復習します。

定義１ $[n]$ の空でない $k$ 個の部分集合への分割の個数を $S(n,k)$ と表し，第二種 Stirling 数（Stirling number of the second kind）という．

第二種 Stirling 数があるなら当然第一種 Stirling 数もあるわけですが、本記事では触れません。

命題２ $S(n,k)$ は漸化式

\begin{split} S(n + 1, k) = k S(n, k) + S(n, k - 1) \end{split}

を満たす．

定理３ \begin{split} S(n, k) = \frac{1}{k!} \sum_{i = 0}^k (-1)^i \binom{k}{i} (k - i)^n. \end{split}

Associated Stirling numbers of the second kind

以下では $r \geq 1$ とします。

定義４ $[n]$ の $k$ 個の部分集合への分割で，各部分集合が少なくとも $r$ 元を持つものの個数を $S_r(n,k)$ と表し， $r$ -associated Stirling number of the second kind という．

$r=1$ のとき $S_1 (n,k)=S(n,k)$ なので、これは第二種 Stirling 数の一般化になっています。

命題５ $S_r(n,k)$ は漸化式

\begin{split} S_r (n + 1, k) = k S_r (n, k) + \binom{n}{r-1} S_r (n - r + 1, k - 1) \end{split}

を満たす．

証明 $[n + 1] = X_1 \sqcup \cdots \sqcup X_k$ を集合の分割で $|X_i| \geq r,1\leq i \leq k$ を満たすものとする． $n + 1\in X_{i_0}$ となる $1\leq i_0 \leq k$ をとっておく．

i) $|X_{i_0}| \gt r$ のとき

$Y_{i_0}=X_{i_0} \setminus \{n+1\}$ ， $i \neq i_0$ のとき $Y_i=X_i$ とおけば $\{Y_1,\cdots,Y_k\}$ は $[n]$ の分割で $|Y_i| \geq r,1\leq i \leq k$ を満たすもの． $i_0$ の可能性が $k$ 通りなので，このような $\{X_1,\cdots,X_k\}$ の数は $k S_r (n, k)$ 個．

ii) $|X_{i_0}| = r$ のとき

$X_{i_0} \setminus \{n + 1\}$ の可能性は $\binom{n}{r-1}$ 通り．また $\{X_i | i \neq i_0 \}$ は $n - r + 1$ 元集合の分割．よってこのような $\{X_1,\cdots,X_k\}$ の数は $\binom{n}{r-1} S_r (n - r + 1, k - 1)$ 個．

(i),(ii) より等式が示された．証明終

次の補題は定義から直ちに従います（もしよければ証明を考えてみてください）。

補題６ \begin{split} S_r (n, k) = \frac{1}{k!} \sum_{ \substack{i_1, \cdots, i_k \geq r \\ i_1 + \cdots + i_k =n} } \binom{n}{i_1, \cdots, i_k}. \end{split}

この補題から $S_r(n,k)$ の母関数が求まります。

定理７ $S_r(n,k)$ の指数型母関数を

\begin{split} F_r (t, u) = \sum_{n,k \geq 0} S_r (n, k) u^k \frac{t^n}{n!} \end{split}

とおくと

\begin{split} F_r (t, u) = \exp \left( u \sum_{i \geq r} \frac{t^i}{i!} \right). \end{split}

証明

\begin{align} \exp \left( u \sum_{i \geq r} \frac{t^i}{i!} \right) &= \sum_{k \geq 0} \frac{1}{k!} \left( u \sum_{i \geq r} \frac{t^i}{i!} \right)^k \\ &= \sum_{k \geq 0} \frac{1}{k!} u^k \sum_{n \geq 0} t^n \sum_{ \substack{i_1, \cdots, i_k \geq r \\ i_1 + \cdots + i_k =n} } \frac{1}{i_1! \cdots i_k!}\\ &= \sum_{n,k \geq 0} \left( \frac{1}{k!} \sum_{ \substack{i_1, \cdots, i_k \geq r \\ i_1 + \cdots + i_k =n} } \binom{n}{i_1, \cdots, i_k} \right) u^k \frac{t^n}{n!}\\ &= F_r(t,u). \end{align}

証明終

定理８ \begin{split} S_{r+1} (n, k) = \sum_{i=0}^k (-1)^i \frac{1}{i!} \binom{n}{r, \cdots, r, n-ri} S_r(n-ri, k-i). \end{split}

証明定理７から $F_{r+1}(t,u) =\exp \left( -u \frac{t^r}{r!} \right) F_r(t,u)$ ．

また

\begin{align} \exp \left(-u \frac{t^r}{r!} \right) F_r(t,u) &= \sum_{i \geq 0} \frac{1}{i!} \left( -u \frac{t^r}{r!} \right)^i \sum_{n,k \geq 0} S_r (n, k) u^k \frac{t^n}{n!}\\ &= \sum_{i,n,k \geq 0} (-1)^i \frac{1}{i!} \frac{1}{(r!)^i} S_r(n,k) u^{i+k} \frac{t^{ri+n}}{n!}\\ &= \sum_{n,k \geq 0} \left( \sum_{i=0}^k (-1)^i \frac{1}{i!} \binom{n}{r, \cdots, r, n-ri} S_r(n-ri, k-i) \right) u^k \frac{t^n}{n!}. \end{align}

ここで二行目から三行目への変形では， $ri+n$ を $n$ ， $i+k$ を $k$ に置き換えた．証明終