- 追加された行はこの色です。
- 削除された行はこの色です。
#rst2hooktail_source
============================================================
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@@
記事ソース/nCkはなぜ整数か のバックアップ差分(No.3)
