_nＣ_m は整数 　　　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「ＹＩ」からの疑問です。（平成２６年４月４日付け）

　以前からずっと疑問に思っていたことです。　_nＣ_m = n!/m!(n-m)! という式は普段当たり前
のように使っていますが、よく考えてみると、n!がm!(n-m)!で割り切れる保証はどこにもない
ように感じます。

　_nＣ_m が必ず整数になることは証明できるのでしょうか？


　DD++さんからのコメントです。（平成２６年４月５日付け）

　大学入試風の誘導をつけるなら、

(1) 　任意の自然数ｎについて、_nＣ₀=1　および　_nＣ_ｎ=1　を証明せよ。

(2) 　1≦m≦n-1　なる任意の自然数m、nについて、等式　_nＣ_m=_n-1Ｃ_m+_n-1Ｃ_m-1が成り立つこ
　　とを証明せよ。

(3)　「0≦m≦n　なる任意の非負整数mについて、_nＣ_mは自然数」が任意の自然数nで正しい
　　ことをnに関する数学的帰納法で証明せよ。

　連続ｎ整数の積は、n!の倍数であることを素因数で考えて証明するという方法もあるでしょ
うが、私はこっちが簡単だと思います。


　ＡＢＣＤＥＦさんからのコメントです。（平成２６年４月５日付け）

　_nＣ_mを、「相異なるn個のものからm個とる組合せの総数」で定義し、_nＣ_m = n! / m!(n-m)!　を

証明したのであれば、_nＣ_mは当然整数であり、従って、n!はm!(n-m)!で割り切れると、これで

終わりですが、感覚的に納得できないということなのか、それとも

　　「_nＣ_m = n! / m!(n-m)!で、_nＣ_mを定義したとき、_nＣ_mが整数になる」

ことの証明はどうすればいいのかという意味でしょうか？

　_nＣ_m = n! / m!(n-m)!=n(n-1)･･･(n-m+1)は、n-m+1から始まる連続m整数の積だから、kか

ら始まる連続n整数の積k(k+1)･･･(k+n-1)がn!で割り切れることを示せばいい。

　相異なるk+n-1個のものからn個とる組合せの総数がk(k+1)･･･(k+n-1)/n!であることから証
明するのが一番簡単でしょうが、それは駄目ということなのでしょう。

　a(k，n)=k(k+1)･･･(k+n-1) が、ｎ!で割り切れる

ことを、数学的帰納法により証明する。

（証明）　k=1 のときは明らか。n=1 のときも明らか。

　k+n に関する数学的帰納法で証明する。

　k+n≦N のとき正しいとして、k+n=N+1の場合を考える。

　k=1やn=1のときは成り立つから、k＞1、n＞1としてよい。

　　a(k，n)=k(k+1)･･･(k+n-1)=k(k+1)･･･(k+n-2)(k-1)+k(k+1)･･･(k+n-2)n

　　　　　 =(k-1)k(k+1)･･･(k-1+n-1)+k(k+1)･･･(k+n-1-1)n=a(k-1，n)+a(k，n-1)n

　 (k-1)+n=k+(n-1)=N　より、帰納法の仮定より、a(k-1，n)は、ｎ!で割り切れ、a(k，n-1)は、

　(ｎ-1)!で割り切れる。

　だから、a(k，n-1)nは、ｎ!で割り切れ、a(k，n)は、ｎ!で割り切れる。　　（証終）

　実質的には、DD++さんが書かれてるのと同じだろうと思います。

　すべての素数pについて、

　　[k(k+1)･･･(k+n-1)に含まれる素因数pの個数]≧[n!に含まれる素因数pの個数]

を示すのも感覚的には難しくないんだけど、表現が難しそうです。やはり組合せの数を考え
るのが一番いいと思いますが．．．。


　ＹＩ さんからのコメントです。（平成２６年４月５日付け）

　丁寧な回答をありがとうございます。つまり、こういうことでしょうか。

　「相異なるｎ個のものからｍ個とる組合せの総数」をxとし、ｎ個の中から順列でｍ個選び出
す組み合わせ数は、x・ｍ!で、「ｎ個の中から順列でｍ個選び出す組み合わせ数」をまた別の
方法で求めると、_nＰ_m = ｎ!/(ｎ-ｍ)! （これは証明済み）。よって、x = n!/m!(n-m)! で、定義上
x は整数なので、_nＣ_mは整数になる。

　よく考えれば、違う数学の体系を使っているだけで、証明には違いありませんね。とはいえ、
数論的にも証明できるということで安心しました。


　ＫＳさんからのコメントです。（平成２６年４月１２日付け）

　組合せの数が「整数」なので整数になる、では証明になってないでしょうか？ただ、本質的
に、ガウス記号の不等式を使った証明が考えられます。

　[A+B]≧[A]+[B]　が成り立つので、整数a、b、素数pに対して、[(a+b)/p]≧[a/p]+[b/p]

　整数N！中にある素数p因数の個数は、[N/p]+[N/p²]+[N/p³]+…　で与えられる。

　従って、N=r+N-r なので、分子のほうが、分母の素因数の個数より多いので割り切れる。


　当ＨＰがいつもお世話になっているＨＮ「りらひい」さんから別件で質問を頂きました。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２７年２月５日付け）

　ｎ、ｒ は整数で、０＜ｒ＜ｎ が成り立っているとします。

　ｒ とｎ−ｒ の最大公約数をｄとしたとき、ｄ×_nC_r がｎの倍数である

という命題は真でしょうか？さらに、一般化した場合について、

　ｒ₁、ｒ₂、・・・、ｒ_m を正の整数とし、ｎ＝Σ_ｋ ｒ_ｋ とおきます。

　ｒ₁、ｒ₂、・・・、ｒ_m の最大公約数をｄとしたとき、ｄ×ｎ!/(Π_ｋ ｒ_ｋ) がｎの倍数である

という命題は真でしょうか？


　DD++さんが検証されました。（平成２７年２月５日付け）

　真です。

（証明）　_nC_r = n! / r!(n-r)! を用いると、

　　r × _nC_r = n! / (r-1)!(n-r)! = n × (n-1)! / (r-1)!(n-r)! = n × _n-1C<sub>r-1

　n-1</sub>C_r-1 は整数なので、r × _nC_r は n の倍数。

同様に、

　(n-r) × _nC_r = n! / r!(n-r-1)! = n × (n-1)! / r!(n-r-1)! = n × _n-1C<sub>r

　n-1</sub>C_r は整数なので、 (n-r) × _nC_r は n の倍数。

よって、r × _nC_r と (n-r) × _nC_r との最大公約数である d × _nC_r も n の倍数　　（証終）


　一般化されたものも同様に示せます。


　りらひいさんからのコメントです。（平成２７年２月５日付け）

　なるほど、確かにそうですね。r×_nC_r=n×_n-1C_r-1 という変形まではわかっていたのです
が、そのあとは公約数の性質を使えば示すことができるのですね。すっきりしました。ありが
とうございました！


　平成２７年度入試　東京大学前期理系で次のような問題が出題された。

問題　ｍを２０１５以下の正の整数とする。₂₀₁₅Ｃ_ｍが偶数となる最小のｍを求めよ。

　問題を見て、何て簡潔なんだろうというのが率直な感想。ただ整数問題が絡んでいそうで、
ちょっと難しそうというのを直感しました。

　Excel さんに協力してもらって探索しようと思いましたが、ｍ＝０、１、２、３まではすべて奇
数で、ｍ＝４以降は指数表示になって、偶奇の判断が出来ませんでした。

　「WolframAlpha」さんにもお助け願うと、

　₂₀₁₅Ｃ₄＝684849315865　、₂₀₁₅Ｃ₅＝275446394840903　、₂₀₁₅Ｃ₆＝92274542271702505　、

　₂₀₁₅Ｃ₇＝26482793631978618935　、₂₀₁₅Ｃ₈＝6647181201626633352685　、

　₂₀₁₅Ｃ₉＝1482321407962739237648755　、・・・・・・・・・・・・・・・・・・・・・・・・・・、

　₂₀₁₅Ｃ₃₂＝16186954748025166046263663997642430244064006144786443959701793710268550

で、ようやく偶数。したがって、求める答えは、ｍ＝３２なわけだが、「WolframAlpha」さんなし
でどう解決するのだろう。


　DD++さんが考察されました。（平成２７年３月５日付け）

　任意の自然数ｍに対して、　ｍ・₂₀₁₅Ｃ_m ＝(２０１６−ｍ)・₂₀₁₅Ｃ_m-1

であり、₂₀₁₅Ｃ_m および ₂₀₁₅Ｃ_m-1 が整数であることは明らかである。

　よって、₂₀₁₅Ｃ_m が偶数かつ ₂₀₁₅Ｃ_m-1 が奇数であることの必要十分条件は、

　　　２０１６−ｍ が ｍ よりも多く素因数 ２ をもつことである。

　２０１６−ｍ＝２^ａＡ　、ｍ＝２^ｂＢ （ａ、ｂ は非負整数で、ａ＞ｂ、A、B は正の奇数）とすると、

　２０１６＝２^ｂ{２^a-b A＋B} であり、 { } 内は奇数なので、　ｂ＝５　つまり、条件を満たす可能

性のある最小数は、ｍ＝２⁵ である。

　逆に、ｍ＝２⁵ のとき、２０１６−ｍ＝１９８４＝２⁶×31 となり条件を満たす。

　以上より、求める数は、　 ｍ＝２⁵＝３２


　最初のような等式（使えるのは何パターンかありそう）を作れるかどうかだけっぽいです。
２０１３から素因数分解に手間のかかる数字が続いたところから、突然、２０１６で問題に使
いやすいものが来るため、来年はそれを生かす問題のオンパレードかなと思ったら、東大
が１年先んじましたね。この手の整数問題は京大のイメージだったので、この問題は少し驚
きました。


　しぇりあさんからのコメントです。（平成２７年３月５日付け）

　東大の整数問題についてですが、一般化しました。

　_nＣ_mが初めて偶数になるｍは、ｎ＋１の２の素因数の個数をｋとすると、ｍ＝２^ｋ

　意外と簡単で拍子抜けですが、次のように言い換えると美しいです。

　ｎの２進法表示で、1の位から数えて初めて０となる位が求めるｍ

　パスカルの三角形を使って視覚的にも理解できるようです。

　この手の整数問題は確かに京大のイメージですよね。でも難易度的にはサービス問題だ
と思います。


（コメント）　計算機に限界があるのに、人間の発想力には限界がないことのいい例でした。
　　　　　　DD++さんの「ｍ・₂₀₁₅Ｃ_m ＝(２０１６−ｍ)・₂₀₁₅Ｃ_m-1から、２０１６−ｍ＝２^ａＡ　、
　　　　　　ｍ＝２^ｂＢ （ａ、ｂ は非負整数で、ａ＞ｂ、A、B は正の奇数）とおいて、
　　　　　　２０１６＝２^ｂ{２^a-b A＋B} （ { } 内は奇数）という発想は目から鱗ですね！なるほど
　　　　　　と感心させられました。


（コメント）　しぇりあさんからのコメントを参考に解答をでっち上げてみました。

　２項定理より、₂₀₁₅Ｃ_m は、（１＋ｘ）²⁰¹⁵ を展開したときの ｘ^ｍ の係数である。

　２０１５を２進法展開すると、　１１１１１０１１１１１　なので、

　　２０１５＝２¹⁰＋２⁹＋２⁸＋２⁷＋２⁶＋２⁴＋２³＋２²＋２¹＋１

　このとき、２を法として、

　（１＋ｘ）²⁰¹⁵≡（１＋ｘ²¹⁰）（１＋ｘ²⁹）（１＋ｘ²⁸）（１＋ｘ²⁷）（１＋ｘ²⁶）
　　　　　　　　　　　　　　　　　　　　　　　　　　（１＋ｘ²⁴）（１＋ｘ²³）（１＋ｘ²²）（１＋ｘ²¹）（１＋ｘ）

　よって、右辺を展開したときに ｘ^ｍ の係数が１になる場合は、ａ_ｋ＝０ または １ で、

ｍ＝ａ₀・２¹⁰＋ａ₁・２⁹＋ａ₂・２⁸＋ａ₃・２⁷＋ａ₄・２⁶＋ａ₆・２⁴＋ａ₇・２³＋ａ₈・２²＋ａ₉・２¹＋ａ₁₀・１

すなわち、２進法表示で、　*****０*****　（*は０ または １）　となる場合である。

　以上から、₂₀₁₅Ｃ_m が偶数となるのは、ｍがこの形に書けない場合であるので、一般に

２進法表示で、　*****１*****　（*は０ または １）　となる場合である。

　したがって、最小のｍは、２進法表示で　１０００００　すなわち、十進数表示で

　　　１・２⁵＋０・２⁴＋０・２³＋０・２²＋０・２¹＋０・１＝３２

である。


（コメント）　上記の解答を得て、何となくスッキリしました！



　　以下、工事中！