■二項係数の偶奇性(その1)

1  1                 奇数2,偶数0

1  2  1              奇数2,偶数1

1  3  3  1           奇数4,偶数0

1  4  6  4  1        奇数2,偶数3

1  5  10  10  5  1     奇数4,偶数2

1  6  15  20  15  6  1  奇数4,偶数3

 パスカルの三角形のn行の奇数と偶数の割合を計算する.n→∞のとき,奇数と偶数の比は0に近づく. 

===================================

(Q)(a+b)^nの二項展開の係数は,nが2^k−1の形であるとき,そのときに限りすべて奇数となることを証明せよ.

(A)(a+b),(a+b)^2,・・・,(a+b)^n-1に対して成り立っていると仮定して,(a+b)^nに対しても成り立つことを証明する.

 両端の1を除くn−1個の二項係数は

  n/1=n,n(n−1)/1・2,・・・,n(n−1)・・・1/1・2・・・(n−1)=n

 これらがすべて奇数であるための必要十分条件は

[1]両端のnが奇数であること

[2]残りの数の分母、分子から奇数を取り去って作られる数が奇数であることである.

 n=2m+1とおけば,これらの数は

  m/1=m,m(m−1)/1・2,・・・,m(m−1)・・・1/1・2・・・(m−1)=m

で表される.m<nであるから,このm−1個の数はmが2^k-1−1の形であるとき,そのときに限りすべて奇数となる.

  n=2m+1=2(2^k-1−1)+1=2^k−1

より,QED.

===================================

[1]n=pのとき,nCmはpの倍数である

 両端nC0=nCn=1ですから,両端以外のnCm(1≦m≦n−1)について考えます.n=pのとき

  pCm=p!/m!(p−m)!

1≦m≦p−1,1≦p−m≦p−1より,分母は素因数pを含んでいない.よって,pCmはpの倍数である.

[2]n=2^kのとき,nCmは偶数である

  (a+b)^2=a^2+{係数が偶数の項}+b^2

  {(a+b)^2}^2=a^4+{係数が偶数の項}+b^4

  {(a+b)^4}^2=a^8+{係数が偶数の項}+b^8,・・・

数学的帰納法より,nCmは偶数である

[3]n=2^k−1のとき,nCmは奇数である

 [2]より,n+1Cmは偶数である.

  n+1Cm=nCm-1+nCm

  1+nC1=偶数→nC1は奇数

  nC1+nC2=偶数→nC2は奇数,・・・

よって,nCmは奇数である.

 さらに,nCmがすべては奇数になるのは,n=2^k−1のときに限るというのが冒頭の命題です.実際,他の行には偶数があるのですが,

[4]n=2^kのとき,両端以外のnCm,2^k−1個はすべて偶数である

[5]n=2^k+1のとき,真ん中のnCm,2^k−2個はすべて偶数である

[6]n=2^k+2のとき,真ん中のnCm,2^k−3個はすべて偶数である

・・・・・・・・・・・・・・・

[7]n=2^k+1−2=2^k+2^k−2のとき,真ん中のnCm,2^k−(2^k−1)=1個はすべて偶数である

[8]nCmがすべては奇数になるのは,n=2^k−1のときだけ

ということになります.

===================================

【まとめ】

 nCm(m=0〜n)がすべては奇数になるのは,n=2^k−1のときに限る.さらに,k>1に対してnCm(m=1〜n−1)がkで割り切れるための必要十分条件は,kが素数であって,n=k^mの形に書けるときに限る.

===================================