質問: ncmが奇数であることの必要十分条件は、2進記数表記で... 自然数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 が奇数であることの必要十分条件である。 このことはどうやって証明できるのでしょうか?
回答: 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