\(i\) 次方程式 \(g_i, f_i\) が
\begin{align}
&g_i=\sum_{j=0}^i a(i,j)f_j\\
&f_i=\sum_{j=0}^i b(i,j)g_j
\end{align}
を満たすとき、任意の数列 \((c_i)_{i=0}^n,(d_i)_{i=0}^n\) について
\begin{align}
&d_i=\sum_{j=0}^i a(i,j)c_j\\
\Leftrightarrow\ &c_i=\sum_{j=0}^i b(i,j)d_j
\end{align}
が成り立つ。
二項反転公式
\begin{align}
(x+1)^i=&\sum_{j=0}^i {i \choose j}x^j \\
x^i=&\sum_{j=0}^i (-1)^{i-j} {i \choose j} (x+1)^j
\end{align}
\(AB\) が単位行列となることから、\(\sum_j {i \choose k}{k \choose j} (-1)^{k-j}= \delta_{i,j}\) も分かる。
スターリングの反転公式
第1種スターリング数 \([{n\atop k}]\) を、区別可能な \(n\) 要素を \(k\) 個のサイクルに分割する方法の個数、第2種スターリング数 \(\{{n \atop k}\}\) を、区別可能な \(n\) 要素を \(k\) 個の非空なグループに分割する方法の個数とすると、
\begin{align}
x^{n} =& \sum_{k=0}^{n} \left\{{n\atop k}\right\} x(x + 1)(x + 2)\cdots(x + k-1)\\
x(x + 1)(x + 2)\cdots(x + n-1)=&\sum_{k=0}^{n} \left[{n\atop k}\right]x^k
\end{align}が成り立つ。1つ目の式は、\(x=i\) を代入すると、区別可能な \(n\) 要素を \(i\) 個の区別可能なグループに分割する方法（空集合可）の個数を表しており、右辺はそれを、非空なグループの個数で分類して数えていることから、成立が分かる。
\(AB\) が単位行列となることから、\(\sum_k \left[{i\atop k}\right]\left\{{k\atop j}\right\} =\sum_k \left\{{i\atop k}\right\} \left[{k\atop j}\right]= \delta_{i,j}\) も分かる。
非空な集合の指数型母関数が \(\exp(x)-1\), サイクルの指数型母関数が \(-\log(1-x)\) であることから、\(f(\exp(x)-1)=g(x) \Leftrightarrow f(x)=g(-(-\log(1-(-x))))\) の変換をしていると捉えても良い。
Comments