nCkはなぜ整数か

確率，場合の数でよく出てくる _nC_k = \dfrac{n!}{(n-k)!k!} ですが， n と k が自然数の時， 本当に， n!/(n-k)! は k! で割りきれるのでしょうか．これを示してみます． かなり簡単に示せます．

アプローチの方法

まず， n! に含まれる素数 p の数 i は， ガウス記号を用いて，

\sum_{i=1}^\infty \lfloor \dfrac{n}{p^i} \rfloor \tag{1}

であることが少し考えればわかります．

これを使うと， n から並ぶ k 個の数の積 n!/(n-k)! に含まれる p の数は，

\sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor \right) \tag{2}

となります．そして， k! に含まれる p の数は，

\sum_{i=1}^\infty \lfloor \dfrac{k}{p^i} \rfloor \tag{3}

ここで， i を任意に取った時，

\lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor \geq \lfloor \dfrac{k}{p^i} \rfloor \tag{4}

を示せれば，OKです．

不等式の評価

式 (4) は簡単に示せます． 一般に実数 x に対して，

x-1 < \lfloor x \rfloor \leq x \tag{5}

が言えるので，

\dfrac{n}{p^i} -1 < \lfloor \dfrac{n}{p^i} \rfloor \leq \dfrac{n}{p^i} \tag{6} - \dfrac{n-k}{p^i} \leq - \lfloor \dfrac{n-k}{p^i} \rfloor < -\dfrac{n-k}{p^i}+1 \tag{7} - \dfrac{k}{p^i} \leq - \lfloor \dfrac{k}{p^i} \rfloor < -\dfrac{k}{p^i}+1 \tag{8}

式 (6) \sim (8) を辺々足して，

-1 < \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor - \lfloor \dfrac{k}{p^i} \rfloor < 2 \tag{9}

よって，式 (9) の値は整数なので， 0 か 1 になるので， 式 (4) が成立することになります．これで， _nC_k が整数になることが示せました．

さらに言えば，式 (9) の中辺を i で和をとった値 d_p ，

d_p := \sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor - \lfloor \dfrac{k}{p^i} \rfloor \right) \tag{10}

は， _nC_k は p^{d_p} で割れることを示しています． 今日はここまで，お疲れ様でした．