記事ソース/nCkはなぜ整数か
をテンプレートにして作成
査読
rst2hooktail
進行表
執筆中
かぎマニュ
物理のかぎプロジェクト
トップ
最近の更新
ヘルプ
開始行:
#rst2hooktail_source
=========================================================...
nCkはなぜ整数か
=========================================================...
確率、場合の数でよく出てくる $_nC_k = \dfrac{n!}{(n-k)!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)!$ に...
<tex>
\sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \rfloor -...
</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}...
</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 \...
</tex>
<tex>
- \dfrac{n-k}{p^i} \leq - \lfloor \dfrac{n-k}{p^i} \rfloo...
</tex>
<tex>
- \dfrac{k}{p^i} \leq - \lfloor \dfrac{k}{p^i} \rfloor < ...
</tex>
式 $(6) \sim (8)$ を辺々足して、
<tex>
-1 < \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}...
</tex>
よって、式 $(9)$ の値は整数なので、 $0$ か $1$ になるので、
式 $(4)$ が成立することになります。これで、 $_nC_k$ が整...
さらに言えば、式 $(9)$ の中辺を $i$ で和をとった値 $d_p$ 、
<tex>
d_p := \sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \r...
</tex>
は、 $_nC_k$ は $p^{d_p}$ で割れることを示しています。
今日はここまで、お疲れ様でした。
@@author:クロメル@@
@@accept:2019-12-24@@
@@category:物理数学@@
@@id:combiIsInt@@
終了行:
#rst2hooktail_source
=========================================================...
nCkはなぜ整数か
=========================================================...
確率、場合の数でよく出てくる $_nC_k = \dfrac{n!}{(n-k)!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)!$ に...
<tex>
\sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \rfloor -...
</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}...
</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 \...
</tex>
<tex>
- \dfrac{n-k}{p^i} \leq - \lfloor \dfrac{n-k}{p^i} \rfloo...
</tex>
<tex>
- \dfrac{k}{p^i} \leq - \lfloor \dfrac{k}{p^i} \rfloor < ...
</tex>
式 $(6) \sim (8)$ を辺々足して、
<tex>
-1 < \lfloor \dfrac{n}{p^i} \rfloor - \lfloor \dfrac{n-k}...
</tex>
よって、式 $(9)$ の値は整数なので、 $0$ か $1$ になるので、
式 $(4)$ が成立することになります。これで、 $_nC_k$ が整...
さらに言えば、式 $(9)$ の中辺を $i$ で和をとった値 $d_p$ 、
<tex>
d_p := \sum_{i=1}^\infty \left( \lfloor \dfrac{n}{p^i} \r...
</tex>
は、 $_nC_k$ は $p^{d_p}$ で割れることを示しています。
今日はここまで、お疲れ様でした。
@@author:クロメル@@
@@accept:2019-12-24@@
@@category:物理数学@@
@@id:combiIsInt@@
ページ名:
Modified by
物理のかぎプロジェクト
PukiWiki 1.4.6
Copyright © 2001-2005
PukiWiki Developers Team
. License is
GPL
.
Based on "PukiWiki" 1.3 by
yu-ji
Powered by PHP 5.3.29 HTML convert time to 0.002 sec.