nCrが整数になることを証明したいのですが・・・。

質問

nCrが常に整数になることを証明したいのですが、

私は帰納法を使って証明しようとして途中で行き詰ってしまいました。
これを証明できる人はいませんか？
もちろん帰納法以外でも大歓迎です。

ただし、組み合わせの数だから整数になるは当たり前というのはなしでお願いします。

回答No.3

koko_u_ · ベストアンサー

別解。単純に n! が r!(n-r)! で割りきれることを示す。

補題
素数 p に対して n! を割り切る最大の p の羃指数は Σ_{i=1～∞}[n/p^i] ここで [x] は x を越えない最大の整数

これを使用すれば任意の素数 p に対して n! を割り切る p 羃指数は Σ[n/p^i] 、 r! を割り切る p 羃指数は Σ[r/p^i]、 (n-r)! を割り切る p 羃指数は Σ[(n-r)/p^i]。

容易にわかるように [n/p^i] ≧ [r/p^i] + [(n-r)/p^i] のため、n! を素因数分解したときに、その p 羃の因数は r!(n-r)! の p 羃因数で割り切れる。

補題の証明は宿題ね。

お礼

御回答どうもありがとうございます。

難しいです・・・。
力不足で補題の証明もできそうにないです・・・。

整数論の本か何かを調べれば分かるんでしょうか・・・。

回答No.5

adinat

証明にはいろんな方法があっていいと思うんですが、汎用性っていうのが僕は大事だと思っています。そういう意味では、ANo.2さんやANo.3さんの方法が優れているという気がしてきました。

ちなみに整数論の本を見るまでもなく、n!が素数pで最大何回割れるか、というのは、1～nの中にpの倍数は何個あるのか？p^2の倍数は何個あるのか？p^3の倍数は何個あるのか？ということを考えていくと分かりますよ～＾＾ヒント書いちゃいましたがいいですよね？＞ANo.3様

で、どのあたりが汎用性があるかと思ったかというと、二項係数nCr（この記号を使うのは日本ぐらいで、普通はnとrを縦に並べて（ ）でくくります。以下では(n;r)と表記することにします）とは、n人のグループをr人とn-r人の二つのグループに分割する組み合わせの総数を表しています。そこでこれを拡張して、n人をr_1人、r_2人、…、r_k人のグループに分割する場合の数を考えます。ただしn=r_1+r_2+…+r_kです。この数を多項係数(n;r_1,r_2,…,r_k)と呼んでいます。通常はnの下にr_1,r_2,…,r_kを並べて（ ）でくくって表記します。n=2のときが二項係数です。この場合はr_2=n-r_1ですので、書かないのが慣例です。この多項係数、たとえば(a_1+a_2+a_3+…+a_k)^nの展開式に現れる係数を求めるのに使われたりします。

で、(n;r_1,r_2,…,r_k)=n!/(r_1!r_2!…r_k!)なのですが、これは当然ながら自然数です。どうやって証明するかということになるわけですが、ここでANo.2さんやANo.3さんの方法が活躍するわけです。たとえばANo.2さんの方法を使えば、n!をn×(n-1)×…×1として、前から順番にr_1個、r_2個、…と分けて考えると、それがそれぞれr_1!の倍数、r_2!の倍数、…となるわけですね。ANo.3さんの方法はまったくそのまま通用します。ぜひ証明してみてください。それでは。

回答No.4

koko_u_

>力不足で補題の証明もできそうにないです・・・。
証明見たら「何だ、簡単じゃねーか」と思うこと請け合いですが、初等整数論の参考書をいくつか漁れば載ってると思います。

#証明は直接示すのが最も好き。

お礼

お返事どうもありがとうございます。

私も１冊だけ「初等整数論」（遠山啓）という整数論の本を持っていまして、まだ手付かずなのですが、パラパラとめくってみましたら
それらしい項目が載っていました。

>証明見たら「何だ、簡単じゃねーか」と思うこと請け合いですが

さすがにこうゆう訳にはいきませんでしたが、
勉強してみたいなという気持ちになりました。

>#証明は直接示すのが最も好き。

素数やガウス記号をつかう証明は今までみたことがなく、
こうゆうのをマスターできればまた別の世界が開けそうな予感がして楽しみです。

頑張ってみます。

回答No.2

zk43

nCr=n(n-1)(n-2)…(n-r+1)/r！
(r=0,1,2,…,n）
から出発します。

要点はn(n-1)(n-2)…(n-r+1)がr！で割り切れることですね。

一般的な話として、連続するr個の自然数の積はr！で割り切れます。
以下ではこれを証明します。

1個の場合は自明です。
連続するk個の自然数の積はk！で割り切れると仮定します。
nを任意の自然数として、
f(n)=n(n+1)(n+2)…(n+k)
という関数を考えます。（任意の、連続するk+1個の自然数の積）
f(i+1)-f(i)
=(i+1)(i+2)…(i+k)(i+k+1)-i(i+1)(i+2)…(i+k)
=(i+1)(i+2)…(i+k)(i+k+1-i)
=(i+1)(i+2)…(i+k)(k+1)
ここに、(i+1)(i+2)…(i+k)は連続するk個の自然数の積なので仮定
によりk！で割り切れる。
よって、
f(i+1)-f(i)=（k！の倍数）×(k+1)=(k+1)！の倍数
これを、i=1,2,…,n-1として足してやると、
f(n)-f(1)=(k+1)！の倍数の和=(k+1)！の倍数
f(1)=(k+1)！なので、f(n)=(k+1)！の倍数となって、f(n)は(k+1)！
で割り切れる。
以上、数学的帰納法により、どんな自然数rに対しても、連続する
r個の自然数の積はr！で割り切れる。

nCrの分子のn(n-1)(n-2)…(n-r+1)は連続するr個の自然数の積なので、
r！で割り切れる。すなわち、nCrは自然数である。

お礼

御回答ありがとうございます。
とても分かりやすいです。

>f(i+1)-f(i)

なるほど～、差を考えるんですか・・・。
全然思い付かなかったです・・・。

どうもありがとうございます。
助かりました！

回答No.1

adinat

帰納法で示すなら、パスカルの三角形を利用するのが一番自然で簡明だと思います。

(*) nCr + nC{r+1} = {n+1}C{r+1}

という有名な関係式（パスカルの三角形の原理）は、簡単に階乗の定義から証明できます。ただし0≦r≦n-1とします。

以下、命題Pn：「nCrは0≦r≦nについて整数である」を帰納法で示します。
(i) P1は自明。
(ii) Pkの成立を仮定すると、パスカルの三角形の原理(*)より、{k+1}C{r+1}は0≦r≦k-1に関して整数になる。また{k+1}C0={k+1}C{k+1}=1より、これも整数。したがって、P{k+1}の成立がわかる。

以上です。まあ、パスカルの三角形を描いてみて、帰納的に明らか、っていう感じですね、気分は。

お礼

御回答どうもありがとうございます。

>nCr + nC{r+1} = {n+1}C{r+1}

この公式を使うんですか・・・。
そういえば習ったような記憶があります。

もう一度確率の分野の参考書を見直して、復習してみます。

どうもありがとうございました。