記事ソース/nCkはなぜ整数か
メニュー現在 7 名がオンラインです。 最新の25件2023-12-12
2023-11-11
2023-11-06
2023-07-15
2022-09-14
2022-07-01
2022-06-12
2022-04-13
2021-12-03
2021-10-07
2021-08-12
2021-07-26
2021-06-30
2021-06-06
2021-05-02
2021-04-17
2021-03-20
2021-03-19
2021-03-11
|
記事ソース/nCkはなぜ整数か†これはrst2hooktailの記事ソース保存・変換用です（詳細）． コンバート公開・更新メニュー ▼▲記事ソースの内容============================================================
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@@
|
