人に聞けない痔の悩み、これでスッキリ >>

自然数n,mを2進記数表記します。

n=2^p(1)+2^p(2)+ …、
m=2^q(1)+2^q(2)+ …

このとき、
{p(1),p(2), ...}⊃{q(1),q(2), ...} であることが、
nCm が奇数であることの必要十分条件である。

このことはどうやって証明できるのでしょうか?

このQ&Aに関連する最新のQ&A

A 回答 (2件)

n=2^p(1)+2^p(2)+....+2^p(i)


m=2^q(1)+2^q(2)+.....+2^q(j)
とおきます。p(1)>p(2)>.....>p(i)>=0
q(1)>q(2)>.....>q(j)>=0とします。
nCm=n!/m!(n-m)!が奇数になるということは
n!とm!(n-m)!を素因数分解したときの2のべきが等しいということです。n!の素因数分解をn!=2^P*....とおく。
n!には2^(p(1)-1)+2^(p(2)-1)+....個の2の倍数があり、2^(p(1)-2)+2^(p(2)-2)+....個の4の倍数があり......1個の2^p(1)のばいすうがあります。これから
P=2^(p(1)-1)+2^(p(2)-1)+....+2^(p(1)-2)+2^(p(2)-2)+....+1=2^p(1)-1+2^p(2)-1+....+2^p(i)-1=
n-iとなります。n!=2^(n-i)*...
同様にm!の2のべき指数はm-jです。m!=2^(m-j)*...
ここでn-m=2^r(1)+2^r(2)+.....+2^r(k)とおきます。
(n-m)!のべき指数はn-m-kです。
nCm=n!/m!(n-m)!の分子の2のべき指数はn-i,分母はm-j+n-m-k=n-(j+k)
分母分子のべき指数はi=j+kのとき等しくなる。
{p(1),p(2), ...}⊃{q(1),q(2), ...} のときは明らかに
k=i-jである。もし{p(1),p(2), ...}⊃{q(1),q(2), ...} とならないときはi<j+kとなってしまう。
このような方針で証明してはどうでしょう。
    • good
    • 0
この回答へのお礼

うーんと納得、予想以上のご回答に感謝です。

>もし{p(1),p(2), ...}⊃{q(1),q(2), ...} とならないときはi<j+kとなってしまう。

これは2進数表記(0と1を使った表記)の筆算での加法を思い浮かべると、

  m =2^q(1)+2^q(2)+.....+2^q(j)
+) n-m=2^r(1)+2^r(2)+.....+2^r(k)
------------------------------------
  n=2^p(1)+2^p(2)+.....+2^p(i)

で繰上りが無いときが、j+k=iで、
「1+1=10」といった繰り上がりが1つでもあると、「1」の個数は少なくなり、j+k>iなのですね。

お礼日時:2006/09/06 02:49

なかなかハイセンスな整数問題ですが、二項係数絡みなので、困ったときはパスカルの三角形を書いてみると何かひらめくことがあるかも知れません。

パスカルの三角形を書いて、奇数になるものに○をつけてやると証明の方針が見えるかも...

具体的にどうするかといわれると、自然に思いつく方法としては数学的帰納法のように思います。命題P(n)を、

P(n):1≦m≦nに対して、{p(1),p(2), ...}⊃{q(1),q(2), ...}ならばnCmは奇数

命題Q(n)を

Q(n):1≦m≦nに対して、nCmが奇数ならば{p(1),p(2), ...}⊃{q(1),q(2), ...}

とおいて、それぞれnについての数学的帰納法で証明するわけです。その際、パスカルの三角形でも使用する性質、nCm+nC(m+1)=(n+1)Cmが役に立つと思います。

他にもよいアイデアがあるかも知れませんが、すぐには思いつきませんでした。
    • good
    • 0
この回答へのお礼

ありがとうございます。たいへん参考になりました。

お礼日時:2006/09/21 15:29

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qコンビネーションの偶数奇数判定ってできますかね

nCm コンビネーションについてですが、n,mが偶数か奇数かによって偶数奇数判定ってできないでしょうか?
分数が入ってると偶数か奇数かわからないような気がするのですが、

階乗計算をしないでできるだけ簡単にコンビネーションの偶数奇数判定をしたいのですが、

どなたか、知恵を御貸し下さい。
お願い致します。

Aベストアンサー

http://oshiete1.goo.ne.jp/qa2385467.html


人気Q&Aランキング