============================================================
nCkはなぜ整数か
============================================================

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

アプローチの方法
====================

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

<tex>
\sum_{i=1}^\infty \lfloor \dfrac{n}{p^i} \rfloor \tag{##}
</tex>

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

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

<tex>
\sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor \right) \tag{##}
</tex>

となります。そして、 $k!$ に含まれる $p$ の数は、

<tex>
\sum_{i=1}^\infty \lfloor \dfrac{k}{p^i} \rfloor \tag{##}
</tex>

ここで、 $i$ を任意に取った時、

<tex>
\lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor \geq \lfloor \dfrac{k}{p^i} \rfloor \tag{##}
</tex>

を示せれば、OKです。

不等式の評価
=================

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

<tex>
x-1 < \lfloor x \rfloor \leq x \tag{##}
</tex>

が言えるので、

<tex>
\dfrac{n}{p^i} -1 < \lfloor \dfrac{n}{p^i} \rfloor \leq \dfrac{n}{p^i} \tag{##}
</tex>

<tex>
- \dfrac{n-k}{p^i} \leq - \lfloor \dfrac{n-k}{p^i} \rfloor < -\dfrac{n-k}{p^i}+1 \tag{##}
</tex>

<tex>
- \dfrac{k}{p^i} \leq - \lfloor \dfrac{k}{p^i} \rfloor < -\dfrac{k}{p^i}+1 \tag{##}
</tex>

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

<tex>
-1 < \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}{p^i} \rfloor - \lfloor \dfrac{k}{p^i} \rfloor < 2 \tag{##}
</tex>

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

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

<tex>
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{##}
</tex>

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

@@author:クロメル@@
@@accept:2019-12-24@@
@@category:物理数学@@
@@id:combiIsInt@@