第一種，第二種スターリング数 - 数学の命題示しました

第一種および第二種スターリング数と呼ばれる数列を定義して，その組合せ論的な意味付けを紹介します．

参考とした本：
Martin Aigner, A course in Enumeration, GTM 238, 2007.

変数 $x$ の昇冪 $(x)^{(n)}$ と降冪 $(x)_n$ を

$(x)^{(n)}\triangleq x(x+1)\cdots (x+n-1)=\prod_{i=0}^{n-1}(x+i),$
$(x)_n\triangleq x(x-1)\cdots(x-n+1)=\prod_{i=0}^{n-1}(x-i),\quad n=1,2,3,\ldots$

$(x)^{(0)}=(x)_0\triangleq 1$
と定義します．
多項式の集合 $\{1,x,x^2,x^3,\ldots\}$ と $\{1,(x)_1,(x)_2,(x)_3,\ldots\}$ はどちらも $\mathbb{R}[x$ ]の基底だから，ある係数 $s(n,k),t(n,k)\in\mathbb{R}$ を使って

$\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}s(n,k) x^k$ ,
$\displaystyle x^n = \sum_{k=0}^n t(n,k) (x)_k,\quad n=0,1,2,\ldots$

と書けます．
この展開の係数として出てくる $s(n,k)$ と $t(n,k)$ はそれぞれ第一種，第二種スターリング数と呼ばれていて，組合せ論的な解釈が与えられています．
以下に見るように，第一種スターリング数は置換のサイクル分解と関係し，第二種スターリング数は有限集合の直和分割に関連します．

第一種スターリング数

$\mathfrak{S}_n$ で $n$ 文字 $\{1,\ldots,n\}$ の置換の集合を表します．
任意の置換は互いに交差しない $(a_1 a_2 \cdots a_r)$ の形の置換の積として，積の順番を除いて一意的に表すことができます．その積表示のことを置換のサイクル分解といいます．
また，置換 $\sigma\in\mathfrak{S}_n$ のサイクル分解に現れる因子の個数を $\sigma$ のサイクル数といいます．
以下の図はサイクル分解を説明する例です．

f:id:iwalion:20200224170713p:plain — サイクル分解の説明

定理１ $\mathfrak{S}_n$ に含まれるサイクル数 $k$ の置換の個数は，第一種スターリング数 $s(n,k)$ である．

証明
$\mathfrak{S}_n$ に含まれる，サイクル数 $k$ の置換の個数を $S(n,k)$ と書きます．
すると
$\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}S(n,k) x^k,\quad n=0,1,2,\ldots$
が成り立つことを示します．

証明には以下の①，②を使います．

① $S(n,k)$ は以下の漸化式を満たします．
$S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k)\quad n,k\geq 0.$
これは， $\mathfrak{S}_n$ に含まれるサイクル数 $k$ の置換を，例えば $1$ を動かすものと動かさないものに分けることで示せます．
説明：文字 $1$ を動かさない置換の数は， $1$ を除いた $n-1$ 文字の置換で $k-1$ 個のサイクルを持つものの数に等しいので $S(n-1,k-1)$ 個．
文字 $1$ を動かす置換の数は， $1$ を除いた $n-1$ 文字の置換のうちサイクル数 $k-1$ のものを考え，どこかのサイクルに $1$ を入れる方法の数なので $(n-1)S(n-1,k)$ 通りです．

②昇冪について，次の式が成り立ちます．
$(x)^{(n)}=(x+n-1)\cdot (x)^{(n-1)}=x\cdot(x)^{(n-1)}+(n-1)\cdot(x)^{(n-1)}$

我々は目的の式
$\displaystyle (x)_n = \sum_{k=0}^n (-1)^{n-k}S(n,k) x^k$
を直接示すのではなく，それと同等な
$\displaystyle (x)^{(n)} = \sum_{k=0}^n S(n,k) x^k$
を示します．（二つが同等であることは， $(-x)^{(n)}=(-1)^n(x)_n$ からわかります．）
証明は $n$ に関する帰納法でします． $n-1$ のとき成立と仮定します．②から
$(x)^{(n)}=x\cdot(x)^{(n-1)}+(n-1)\cdot(x)^{(n-1)}$
帰納法の仮定から
$\displaystyle (x)^{(n)}=x\sum_{k=0}^{n-1}S(n-1,k)x^k+(n-1)\sum_{k=0}^{n-1}S(n-1,k)x^{k}$
$\displaystyle =\sum_{k=0}^{n-1}S(n-1,k)x^{k+1}+\sum_{k=0}^{n-1}(n-1)S(n-1,k)x^{k}$
$\displaystyle =\sum_{k=1}^{n}S(n-1,k-1)x^{k}+\sum_{k=0}^{n-1}(n-1)S(n-1,k)x^{k}$
$\displaystyle =\sum_{k=0}^{n}\left\{S(n-1,k-1)+(n-1)S(n-1,k)\right\}x^k$

但し，最後の行は $S(n-1,-1)= 0,\ S(n-1,n)=0$ を用いました．
①から
$\displaystyle (x)^{(n)}=\sum_{k=0}^nS(n,k)x^k$ ．[証明終わり]

第二種スターリング数

集合 $A$ の冪集合の部分集合 $\mathcal{A}$ が，
１， $\mathcal{A}$ に含まれるどの二つの集合も共通部分を持たない．
２， $\bigsqcup_{S\in\mathcal{A}}=A$
を満たすとき， $\mathcal{A}$ は $A$ の分割であるといいます．
例： $\displaystyle\left\{\{1,3\},\{2\},\{4,5,6,7\}\right\}$ は，集合 $\{1,2,3,4,5,6,7\}$ の分割のひとつです．

定理２ 集合 $\{1,\ldots,n\}$ の分割で，要素数が $k$ のものの個数は，第二種スターリング数 $t(n,k)$ である．

証明
集合 $\{1,\ldots,n\}$ の分割で要素数が $k$ のものの個数を $T(n,k)$ と書くことにします．
すると
$\displaystyle x^n = \sum_{k=0}^n T(n,k) (x)_k,\quad n=0,1,2,\ldots$
が成立することを示します．

そのためにまず，非負整数 $n,r=0,1,2,\ldots$ について
$\displaystyle r^n = \sum_{k=0}^r T(r,k) (r)_k$ が成り立つことを示します．
これが示せれば，我々が示したいところの多項式の等式
$\displaystyle x^n = \sum_{k=0}^n T(n,k) (x)_k,\quad n=0,1,2,\ldots$
も言えます．
説明：左辺と右辺は変数 $x$ の $n$ 次多項式であり，それらは無数の点 $x=0,1,2,\ldots$ で等しいから，多項式として等しいことがわかります．

集合 $A$ から集合 $B$ への写像の集合を ${\rm Map}(A,B)$ ，全射の集合を ${\rm Surj}(A,B)$ とかきます．
自然数 $n$ に対し $[n]\triangleq\{1,\ldots,n\}$ と書きます．

まず，
$\left|{\rm Map}([n],[r])\right|=r^n,$
$\left|{\rm Surj}([n],[r])\right|=r!T(n,r)$
が成り立ちます．
説明：全射の個数は，集合 $\{1,\ldots,n\}$ を $r$ 個の部分集合に分けて，その $r$ 個を一列に並べる方法の数なので， $r!T(n,r)$ 個です．

次に，集合 ${\rm Map}([n],[r])$ と集合 $\displaystyle \bigsqcup_{A\subseteq [r]}{\rm Surj}([n],A)$ の間には全単射が存在します．
さらに後者の集合は
$\displaystyle \bigsqcup_{A\subseteq [r]}{\rm Surj}([n],A)=\bigsqcup_{k=0}^r\bigsqcup_{|A|=k,\ A\subseteq[r]}{\rm Surj}([n],A)$
と書けます．
ここから，上の濃度の議論を使えば，
$\displaystyle r^n=\sum_{k=0}^r\binom{r}{k}k!T(n,k)=\sum_{k=0}^r\frac{r!k!}{k!(r-k)!}T(n,k)=\sum_{k=0}^rT(n,k)\cdot(r)_k$
が成り立ちます．
ここから更に，和を $r$ までではなく $n$ までにした
$\displaystyle r^n=\sum_{k=0}^nT(n,k)\cdot(r)_k$
が成り立ちます．
説明： $n\lt r$ のときは， $T(n,r)=0$ なので成立．また， $n\geq k\gt r$ のときは，和の中の降冪が $(r)_k=0$ となるの成立．
[証明終わり]

今後？とか

第一種スターリング数と第二種スターリング数は似た定義の概念なのに，本で紹介されていた証明方法は二つでけっこう違うものだったのが面白いなって思ってこの記事を書きました．
この記事の続編があるなら，以下のトピックから選んで書こうと思います

第一種，第二種スターリング数には指数型母関数が知られています．
$q$ -スターリング数というものがあるらしいです．
スターリング数は，格子路による意味付けを持つらしいです．
定義からも分かるように，第一種スターリング数（に $(-1)^{n-k}$ をつけたもの）を並べた行列と，第二種スターリング数を並べた行列は互いの逆行列です．このことを使うと，様々な恒等式が言えます．(所謂，数列の反転公式というやつ)
スターリング数をモーメントに持つような直交多項式が研究されていないか探してみます．