この記事は現在、プロジェクトメンバーによる査読中のものです。草稿段階ですので、内容・表現の正確さについて責任を負いかねます。 リンクを正しく張れていないところが存在しますのでご注意ください。 正式公開まで、いましばらくお待ちください。
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} で割れることを示しています． 今日はここまで，お疲れ様でした．