メニュー現在 4 名がオンラインです。 最新の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@@ |