2項係数の性質                             戻る

 2項係数に関する問題で「何か難しそう〜」という強い圧迫感を感じたものとして、次の明
治大学の問題が記憶に残る。今から数十年以上前のものだが、ときどき夢にうなされる。
(ちょっと言い過ぎかな...f(^_^;) )

明治大学入試問題

   を満たす自然数 n 、r を求めよ。

(解) 左辺=60C10・40C40+60C11・40C39+・・・+60C50・40C0 なので、多項式

  (1+x)100=(1+x)60(1+x)40

を展開したときの、x50 の項の係数を求めることに等しい。

 よって、 左辺=100C50 となり、 n=100 、 r=50 である。  (終)


 解答を見てしまえば易しくも感じられるが、解答のような発想を瞬時に思いつく高校生は日
本に何人いるのだろう。正直に告白すると、2項係数の性質をこねくり回して何とか解答をで
っちあげたような気がする。

 上記の解答は、次のように考えれば、ごく自然な発想ということが了解されるだろう。

 赤球60個、白球40個の合計100個の球から50個の球を取り出す場合の数は、

 60C10・40C40+60C11・40C39+・・・+60C50・40C0

である。


 また、最短経路問題として次のように考えてもよい。

 点Aから点Bに至る最短経路は、点P1、P2、・・・、P41 の何れかを必ず通る。

 

 平成24年度から先行実施の新学習指導要領で、2項定理がとても違和感のある扱いを
受けることになる。そもそも2項定理は、それ以前にも不遇な扱いを受けており、教材のお
まけ的扱いに甘んじている。

 しかし、2項定理から派生する種々の2項係数の性質は、豊富な数学的話題を提供し、数
学的には必ずマスターすべき重要事項という位置づけは揺るぎないものと考える。

 このページでは、教科書や問題集で語られる2項係数の性質のみならず、ありとあらゆる
性質をまとめていきたいと思う。

 既に、当HPでは、次のページで2項係数に関する話題を取り上げている。

 ある2項係数の関係  パスカルの三角形  多項式の展開

 これらのページを十分意識しつつ、新しい航海に出ようと思う。

 これから考える2項係数の性質の背景にある定理<2項定理>をまず確認しておこう。

2項定理(Binomial Theory)      

 

 ここで、nCk は、2項係数といわれ、異なる n 個のものから、異なる k 個のものをとる組
合せの数である。

 

 但し、 (n の階乗)とする。

 nCk という記号に対して、 という記号が用いられる場合もある。

(証明) (a+b)n を展開したときの各項は、an 、an-1b 、an-2b2 、・・・ 、bn である。

 an-kbk の係数は、n 個の因数 a+b のそれぞれから、a を n−k 個、b を k 個とる

組合せの数 nCk に等しい。  (証終)


 上記の証明は、教科書によくあるものだが、次のような証明も可能だろう。

(別証) 集合 S={1,2,・・・,n}と集合 A、B(但し、A∩B=φ、n(A)=a、n(B)=b)に
  ついて、写像 F : S → A∪B の個数を数える。

 S の各要素について、a+b 通りの値の取り方があるので、写像の個数は、(a+b)n で
ある。

 また、S の要素を、n−k 個と k 個(k=0、1、2、・・・、n)に分ける。その分け方の総数
は、nCk 通り。

 その1通りに対して、n−k 個の要素には、Aの要素が対応し、k 個の要素には、Bの要
素が対応すると考えると、写像の個数は、an-kbk 通り。

 したがって、

   (証終)


 この2項定理から次の展開公式(Newtonの2項定理)が導かれる。

 (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCrxr+・・・+nCnxn

 この展開公式(EP)を用いると、種々の2項係数の性質が得られる。


(参考文献:ア・ヤグロム、イ・ヤグロム 著 筒井孝胤 訳
                     初等的に解いた高等数学の問題(�U)  (東京図書))

2項係数の性質

(1) nCr=nCn-r (→ 参考:「パスカルの三角形」の(1) )

(証明) n 個のものから r 個取り出す場合の数と r 個取り残す場合の数は等しい。(証終)


 この性質(1)を活用する問題として次があげられる。(平成31年3月5日付け)

練習問題  Σk=0715Ck の正の約数はいくつあるか。

(解) Σk=0715Ck=Σk=0715C15-k=Σk=81515Ck なので、Σk=01515Ck=2Σk=0715Ck

 ところで、 Σk=01515Ck=(1+1)15=215 より、 Σk=0715Ck=214

 よって、求める正の約数の個数は、15個である。  (終)


(コメント) この問題は次のように一般化される。


問題  Σk=0n2n+1Ck の正の約数の個数は、2n+1個であることを示せ。

(解) Σk=0n2n+1Ck=Σk=0n2n+1C2n+1-k=Σk=n+12n+12n+1Ck なので、

  Σk=02n+12n+1Ck=2Σk=0n2n+1Ck

 ところで、 Σk=02n+12n+1Ck=(1+1)2n+1=22n+1 より、 Σk=0n2n+1Ck=22n

 よって、求める正の約数の個数は、2n+1個である。  (終)


(2) nCr=n-1Cr+n-1Cr-1  (1≦r≦n−1)

 (→ 参考:「パスカルの三角形」の(2) )

 この公式は、「和の公式」とも言われる。

(証明) n 個のものから r 個取り出す場合の数は、次の2つの場合の数の和である。

 特定のものを含まない場合の数は、 n-1Cr 通り
 特定のものを含む場合の数は、 n-1Cr-1 通り  (証終)


(3) k・nCk=n・n-1Ck-1 (→ 参考:「パスカルの三角形」の(5) )

(証明) n 人いる中から k 人を選んで、その中で一人班長を決める場合の数と、班長を

 一人選んで、残りの n−1 人から班員 k−1 人を選ぶ場合の数は等しい。  (証終)


 「k・nCk=n・n-1Ck-1」という式も上記の組合せ論的証明を意識すれば分かりやすい
が、初心者にとっては覚えずらいかもしれない。

 数学の専門書では、組合せの記号として、nCr の代わりに、 という記号が用いられ

る場合がある。この記号を用いると、上記の性質は

 

と表される。この公式は、「括りだしの公式」とも呼ばれるが、この表現から、その意味が
直に伝わってくるように感じる。


(4) nC0+nC1+nC2+nC3+・・・+nCr+・・・+nCn=2n

 (→ 参考:「パスカルの三角形」の(3) )

(証明) 展開公式(EP)において、x=1 とおけばよい。 (証終)


(別証) n 個の要素からなる集合Aの部分集合の個数を数える。

 部分集合の要素の個数に着目して、r 個の要素からなる部分集合の個数は、nCr 個

なので、部分集合の個数は、nC0+nC1+nC2+nC3+・・・+nCr+・・・+nCn

 ところで、n 個の要素のそれぞれが部分集合の要素になるかどうかの場合の数を考えて、

部分集合の個数は、2n 個で、明らかに、両者は等しいので、

 nC0+nC1+nC2+nC3+・・・+nCr+・・・+nCn=2n  (別証終)


(5) nC0−nC1+nC2−nC3+・・・+(−1)rnCr+・・・+(−1)nnCn=0

(証明) 展開公式(EP)において、x=−1 とおけばよい。 (証終)
  (→ 組合せ論的証明)


(6) nC0+nC2+nC4+・・・=2n-1

(証明) (4)+(5)より明らか。 (証終)   (→ 組合せ論的証明)


 当然、(4)−(5)より、 nC1+nC3+nC5+・・・=2n-1 も得られる。


 当HPがいつもお世話になっているHN「FN」さんが、この問題を拡張し、考察された。
                                      (平成23年2月23日付け)

 上記(6)のように、nCr の r が偶数のときの等式は、よく知られています。では、r が3の
倍数、4の倍数であるときの和はどうなるでしょうか。

問題  次の和を求めよ。

(イ)  nC0+nC3+nC6+・・・
 (0≦r≦n を満たす3の倍数である r すべてについて、nCr の和)

(ロ) nC0+nC4+nC8+・・・
 (0≦r≦n を満たす4の倍数である r すべてについて、nCr の和)


 大学入試に出題するなら、n を制限するでしょう。例えば、次ぐらいに...。

(イ)’ n が6の倍数であるとき、nC0+nC3+nC6+・・・+nCn の和を求めよ。

(ロ)’ n が8の倍数であるとき、nC0+nC4+nC8+・・・+nCn の和を求めよ。

#(イ)’(ロ)’は、(イ)(ロ)に比べて本質的に易しいわけではありませんが、計算はかなり楽に
 なります。

 FNさんの問いかけに、at さんが(イ)(ロ)を解かれました。(平成23年2月23日付け)

(解) f(x)=(1+x)n 、αm=cos(2π/m)+i・sin(2π/m) とする。

 このとき、

nC0+nC3+nC6+・・・

={Σ[j=1〜3]f(α3j)}/3  (← α3+α32+α33=0 )

={2n+2cos(nπ/3)}/3  (← 半角の公式とド・モアブルの定理 )

 同様にして、

nC0+nC4+nC8+・・・

={Σ[j=1〜4]f(α4j)}/4=2n-2+2(n-2)/2cos(nπ/4)  (終)


 FNさんからのコメントです。(平成23年2月23日付け)

 at さんのやりかたの練習という意味での出題なので、at さん以外の方に答えていただく
ことを想定していました。もちろんいけないわけではないのですが...。

 上記で、「(イ)’(ロ)’は、(イ)(ロ)に比べて本質的に易しいわけではありませんが、計算はか
なり楽になります。
」と書いたのは、高校レベルを意識したものです。

 現在の高校では複素数平面はやりません。もちろん、ド・モアブルの定理もありませんから、
n で場合分けして答えるしかありません。

 だから結構面倒になるので、(イ)’(ロ)’ぐらいでいいかなという気がします。


 FNさんが、(イ)’(イ)の解を与えられました。(平成23年2月24日付け)

((イ)’の解) ω を1の虚数立方根とすると、 1+ω+ω2=0 、ω3=1 である。

  (1+x)n=nC0+nC1x+nC2x2+nC3x3+nC4x4+nC5x5+・・・

 この式に、x=1、ω、ω2 を代入して、

  2n=nC0+nC1+nC2+nC3+nC4+nC5+・・・
  (1+ω)n=nC0+nC1ω+nC2ω2+nC3ω3+nC4ω4+nC5ω5+・・・
  (1+ω2)n=nC0+nC1ω2+nC2ω+nC3+nC4ω2+nC5ω+・・・

 ここで、nは6の倍数だから、 (1+ω)n=(−ω2)n=ω2n=1

 同様に、 (1+ω2)n=(−ω)n=ωn=1

 上の3式を加えると、左辺=2n+2 、右辺=3(nC0+nC3+nC6+・・・)

 したがって、 nC0+nC3+nC6+・・・+nCn=(2n+2)/3  (終)

((イ)の解) (1+ω)n+(1+ω2)n の計算以外は上と同じです。

  (1+ω)n+(1+ω2)n=(−ω2)n+(−ω)n=(−1)n(ωn+ω2n)

 ここで、 nが3の倍数のとき、 (−1)n・2 、
       nが3の倍数でないとき、 (−1)n・(−1)=(−1)n-1

 さらに詳しく分類すると、

 nを6で割った余りが0のとき、2、
 nを6で割った余りが3のとき、−2、
 nを6で割った余りが1か5のとき、1
 nを6で割った余りが2か4のとき、−1

 以上より、次のようになる。

 n≡0  (mod 6) のとき、 (2n+2)/3
 n≡3  (mod 6) のとき、 (2n−2)/3
 n≡1、5  (mod 6) のとき、 (2n+1)/3
 n≡2、4  (mod 6) のとき、 (2n−1)/3  (終)


 攻略法さんも上記の問題(イ)を解かれました。(平成23年2月24日付け)
 (→ 参考:「オメガ(ω)の真実」)

((イ)の解) α3=cos(2π/3)+i・sin(2π/3) (i は虚数単位) より、

 α3=(−1+i・)/2=ω (1の虚数立方根)

f(x)=(1+x)n より、

nC0+nC3+nC6+・・・

={(1+ω)n+(1+ω2)n+(1+ω3)n}/3

={(−ω2)n+(−ω)n+2n}/3

={(−1)n(ω2n+ωn)+2n}/3  ←式1

 これが求める値となる。 n を場合分けすれば、

n=3k の場合  (−1)n(ω2n+ωn)=(−1)k(1+1)=2(−1)k
n=3k+1 の場合
 (−1)n(ω2n+ωn)=(−1)k+1(ω2+ω)=(−1)k+1(−1)=(−1)k
n=3k+2 の場合
 (−1)n(ω2n+ωn)=(−1)k(ω+ω2)=(−1)k(−1)=−(−1)k

となるので、式1は、

n=3k の場合  (2n+2(−1)n)/3
それ以外の場合  (2n−(−1)n)/3  (終)

参考サイト: 「A024493」 、(ロ)の参考サイト: 「A038503」


 FNさんからのコメントです。(平成23年2月24日付け)

 4通りに分けるより、2通りのほうがいいかもしれません。

 できるだけ高校数学の範囲でと考えています。(ロ)もほとんど同じですが、結構面倒そうな
ので、(ロ)’の解答を書いておきます。1、ω、ω2の代わりに、1、−1、i、−i を入れるだけ
ですが...。

((ロ)’の解) (1+x)n=nC0+nC1x+nC2x2+nC3x3+nC4x4+nC5x5+・・・

 この式に、x=1、−1、i、−i を代入して、

 2n=nC0+nC1+nC2+nC3+nC4+nC5+・・・
 0=nC0−nC1+nC2−nC3+nC4−nC5+・・・
 (1+i)n=nC0+nC1i−nC2−nC3i+nC4+nC5i+・・・
 (1−i)n=nC0−nC1i−nC2+nC3i+nC4−nC5i+・・・

 この4式を加えて、 2n+(1+i)n+(1−i)n=4(nC0+nC4+nC8+・・・)

ここで、 (1±i)2=±2i 、(1±i)4=−4 、(1±i)8=16=24 で、

 nが8の倍数だから、n=8k とおくと、 (1±i)n=(24)k=2n/2

従って、 2n+(1+i)n+(1−i)n=2n+2(n+2)/2 より、

 nC0+nC4+nC8+・・・+nCn=2n-2+2(n-2)/2  (終)


 FNさんの((ロ)’の解)を参考にして、((ロ)の解)を考えてみました。

((ロ)の解)  (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n
        (5)より、 nC0−nC1+nC2−nC3+nC4−・・・+(−1)nnCn=0

 また、nC0+nC1i−nC2−nC3i+nC4+nC5i+・・・=(1+i)n
    nC0−nC1i−nC2+nC3i+nC4−nC5i+・・・=(1−i)n

 これらの4式を辺々加えて、 4(nC0+nC4+nC8+・・・)=2n+(1+i)n+(1−i)n

 ここで、ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

 (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

同様にして、 (1−i)n =2n/2(cos(nπ/4)−i・sin(nπ/4)) なので、

 4(nC0+nC4+nC8+・・・)=2n+2・2n/2cos(nπ/4) より、

 nC0+nC4+nC8+・・・=2n-2+2(n-2)/2cos(nπ/4)  (終)


(7) nC1+2nC2+3nC3+・・・+rnCr+・・・+nnCn=n・2n-1

(証明) 展開公式(EP)の両辺を微分して、x=1 とおけばよい。 (証終)


(別証) 性質(3) k・nCk=n・n-1Ck-1 より、

 1・nC1=n・n-1C0
 2・nC2=n・n-1C1
 3・nC3=n・n-1C2
  ・・・・・・・・・
 n・nCn=n・n-1Cn-1

よって、

nC1+2nC2+3nC3+・・・+nnCn
=n(n-1C0+n-1C1+n-1C2+・・・+n-1Cn-1)=n・2n-1  (別証終)


(3)を用いず、(1)を用いた別証も考えられる。方法論的に大切かな?

(別証2) 性質(1) nCr=nCn-r より、

 nC1=nCn-1
 2nC2=2nCn-2
 3nC3=3nCn-3
  ・・・・・・・・・
 nnCn=nnC0

よって、 S=nC1+2nC2+3nC3+・・・+(n−1)nCn-1+nnCn とおくと、

 S=nnC0+(n−1)nC1+(n−2)nC2+・・・+2nCn-2+nCn-1 なので、

 2S=nnC0+nnC1+nnC2+・・・+nnCn-2+nnCn-1+nnCn

  =n(nC0+nC1+nC2+・・・+nCn-2+nCn-1+nCn)=n・2n

よって、 nC1+2nC2+・・・+(n−1)nCn-1+nnCn=n・2n-1  (別証2終)

(→ 組合せ論的証明)


(8) nC1−2nC2+3nC3−・・・+(−1)r-1rnCr+・・・+(−1)n-1nnCn=0

(証明) 展開公式(EP)の両辺を微分して、x=−1 とおけばよい。 (証終)
(→ (8)の一般化)


(別証) k・nCk=n・n-1Ck-1 より、

 1・nC1=n・n-1C0
 2・nC2=n・n-1C1
 3・nC3=n・n-1C2
  ・・・・・・・・・
 n・nCn=n・n-1Cn-1

よって、

 nC1−2nC2+3nC3−・・・+(−1)n-1nnCn
=n(n-1C0−n-1C1+n-1C2−・・・+(−1)n-1n-1Cn-1)=0  (別証終)

(→ 組合せ論的証明)


(9) nC0+(1/2)nC1+(1/3)nC2+(1/4)nC3+・・・+(1/(n+1))nCn

  =(2n+1−1)/(n+1)


(証明) 展開公式(EP)の両辺を、x=0 から x=1 まで定積分すればよい。 (証終)


(別証) k・nCk=n・n-1Ck-1 より、 (k+1)・n+1Ck+1=(n+1)・nCk なので、

 1・n+1C1=(n+1)・nC0
 2・n+1C2=(n+1)・nC1
 3・n+1C3=(n+1)・nC2
  ・・・・・・・・・・・・・
 (n+1)・n+1Cn+1=(n+1)・nCn

よって、

 nC0+(1/2)nC1+(1/3)nC2+(1/4)nC3+・・・+(1/(n+1))nCn
=(n+1C1+n+1C2+n+1C3+・・・+n+1Cn+1)/(n+1)=(2n+1−1)/(n+1) (別証終)

(→ 組合せ論的証明)


(10) nC0−nC1+nC2−nC3+・・・+(−1)mnCm の値は、

  m<n のとき、 (−1)mn-1Cm 、m=n のとき、 0


(証明) k=0、1、2、・・・、m に対して、(−1)knCk は、 xn−k(1−x)n を展開したと
    きの xn の係数である。

 よって、nC0−nC1+nC2−nC3+・・・+(−1)mnCm は、

  xn(1−x)n+xn−1(1−x)n+xn−2(1−x)n+・・・+xn−m(1−x)n を展開したとき

の xn の係数である。

 ここで、

 xn(1−x)n+xn−1(1−x)n+xn−2(1−x)n+・・・+xn−m(1−x)n
=xn−m(1−x)n(1+x+x2+・・・+xm)
=xn−m(1−x)n・(1−xm+1)/(1−x)
=(1−x)n-1・(xn−m−xn+1)

なので、

 m=n のとき、 (1−x)n-1・(xn−m−xn+1)=(1−x)n-1・(1−xn+1) を展開したとき

xn の項はないので、 xn の係数は、 0

 m<n のとき、 (1−x)n-1・(xn−m−xn+1) を展開したときの xn の係数は、

 (1−x)n-1 を展開したときの xm の係数に等しい。すなわち、 (−1)mn-1Cm である。
                                                   (証終)

(コメント) m=n のとき、 nC0−nC1+nC2−nC3+・・・+(−1)mnCm=0 であるこ
  とは、 (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCnxn において、
 x=−1 とおくと、 0=nC0−nC1+nC2−nC3+・・・+(−1)nnCn から明らかだが、
 m<n のときを示すのが難しい。上記の証明の発想はとても新鮮である。


 FNさんが、(10)の別証を考えられた。(平成23年3月27日付け)

 (10)は、r>n のとき、nCr=0 と考えれば、次のようにも表現できる。


(10) nC0−nC1+nC2−nC3+・・・+(−1)mnCm=(−1)mn-1Cm


 場合の数を2通り考えることによって等式を証明するという意味での組合せ論的証明では
ないが、nCr=n-1Cr+n-1Cr-1 を使った別証である。

(別証) r=0 のとき、nC0=n-1C0 に注意して、

 左辺
=nC0−nC1+nC2−nC3+・・・+(−1)mnCm
=n-1C0−(n-1C0+n-1C1)+(n-1C1+n-1C2)
  −(n-1C2+n-1C3)+・・・+(−1)m(n-1Cm-1+n-1Cm)
=(−1)mn-1Cm  (←隣と順次消えていくパターン!)  (別証終)


 (10)で獲得した手法を用いると、次の(11)(12)も容易だろう。


(11) nCk+n+1Ck+n+2Ck+・・・+n+mCk の値は、

  k<n のとき、 n+m+1Ck+1−nCk+1 、k=n のとき、 n+m+1Cn+1

(証明) t=0、1、2、・・・、m に対して、n+tCk は、 (1+x)n+t を展開したときの xkの
    係数である。

 よって、nCk+n+1Ck+n+2Ck+・・・+n+mCk は、

 (1+x)n+(1+x)n+1+(1+x)n+2+・・・+(1+x)n+m

を展開したときの xk の係数である。

 ここで、

 (1+x)n+(1+x)n+1+(1+x)n+2+・・・+(1+x)n+m
=(1+x)n{(1+x)m+1−1}/x
={(1+x)n+m+1/x}−{(1+x)n/x}

なので、k=n のとき、 (1+x)n/x を展開したとき xn の項はないので、 求める値は、

 (1+x)n+m+1 を展開したときの xn+1 の係数 n+m+1Cn+1 に等しい。

 k<n のとき、求める値は、(1+x)n+m+1−(1+x)n を展開したときの xk+1 の係数に

等しい。すなわち、 n+m+1Ck+1−nCk+1 である。  (証終)

(→ 組合せ論的証明)


(追記) 平成27年11月22日付け

 (11)の特別な場合: nCn+n+1Cn+n+2Cn+・・・+n+mCn=n+m+1Cn+1

は、次のような図(n=2、m=3)を与えた方がわかりやすいかもしれない。筑波大学附属
高校生の研究パネルに刺激されました。

  


(追記) 平成26年10月18日付け

 平成8年度 学習院大学経済学部の入試問題において、性質(11)の考え方が有効に用
いられる。

  nを3以上の自然数とするとき、 Σk=3〜n kC3=n+1C4

(解) Σ k=3〜nkC3=3C3+4C3+5C3+・・・+nC3 において、kC3 は、(1+x)kを展開

  したときの x3 の係数である。したがって、3C3+4C3+5C3+・・・+nC3 は、

 (1+x)3+(1+x)4+(1+x)5+・・・+(1+x)n を展開したときの x3 の係数である。

ここで、

 (1+x)3+(1+x)4+(1+x)5+・・・+(1+x)n
=(1+x)3{(1+x)n-2−1}/x=(1+x)n+1/x−(1+x)3/x

 よって、x3 の係数は、n+1C4 となる。  (終)


 上記の証明は機械的で等式の持つ本来の意味が感じられない。やはりそのためには、組
合せ論的証明が求められる。(平成26年10月25日付け)

(別解) n+1個の数 {1,2,3,・・・,n,n+1} から4個とる組合せの数が、n+1C4通りで

 ある。ここで、4つの数の最大数に着目する。

 最大数がnのとき、残りの3つの数の選び方は、nC3 通り
 最大数がn−1のとき、残りの3つの数の選び方は、n-1C3 通り
   ・・・・・・・・・・・・・・・・・・・・・・・・
 最大数が4のとき、残りの3つの数の選び方は、3C3 通り

以上から、等式 3C3+4C3+5C3+・・・+nC3=n+1C4 が成り立つ。  (終)


 また、「性質(2) nCr=n-1Cr+n-1Cr-1  (1≦r≦n−1)」を用いれば、次のよう
な解答も可能である。

(別解) kC3=k+1C4−kC4 、3C4=0 なので、

 Σ k=3〜n kC3=(n+1C4−nC4)+(nC4−n-1C4)+・・・+(4C4−3C4)=n+1C4  (終)


(コメント) 組合せ論的証明も味わいがあっていいですが、間が全て消失するという上記の
      別解も爽快ですね!


 (11)で、k=n のときは、nCr=nCn-r より、次の形にも変形できる。

      nC0+n+1C1+n+2C2+・・・+n+mCm=n+m+1Cm

 この公式は、「総和の公式」とも言われる。

例 4C0+5C1+6C2+7C3=8C3=56


 和の公式(2) nCr=n-1Cr+n-1Cr-1 を繰り返し用いることにより、総和の公式を示す
ことができる。

(別証) nC0+n+1C1=n+1C0+n+1C1=n+2C1

  n+2C1+n+2C2=n+3C2

  n+3C2+n+3C3=n+4C3

    ・・・・・・・・・

  n+mCm-1+n+mCm=n+m+1Cm

 以上から、nC0+n+1C1+n+2C2+・・・+n+mCm=n+m+1Cm が成り立つ。  (別証終)


 この総和の公式を用いると、よく知られた次の和が示される。 

(A) 1+2+3+・・・+n =
(B) 12+22+32+・・・+n2 =

 実際に、(A)は、

 1+2+3+・・・+n

=1C1+2C1+3C1+・・・+nC1

=1C0+2C1+3C2+・・・+nCn-1

=n+1Cn-1=n+1C2=n(n+1)/2

 同様に、(B)は、まず、 k2=(k2−k)+k=2{k(k−1)/2}+k=2kC2+kC1 と書
けるので、

 12+22+32+・・・+n2

=2ΣkC2+ΣkC1

=2(2C2+3C2+・・・+nC2)+(1C1+2C1+・・・+nC1)  (ただし、1C2=0 )

=2(2C0+3C1+・・・+nCn-2)+(1C0+2C1+・・・+nCn-1)

=2n+1Cn-2+n+1Cn-1

=2n+1C3+n+1C2

=2(n+1)n(n−1)/6+(n+1)n/2

=(n+1)n{2(n−1)+3}/6

=n(n+1)(2n+1)/6


(コメント) 斬新な求め方ですね!


(12) 2nC0−2n-1C1+2n-2C2−・・・+(−1)nnCn の値は、k を整数として、

  n=3k のとき、1 、n=3k+1 のとき、0 、n=3k+2 のとき、−1


(証明) k=0、1、2、・・・、n に対して、2n-kCk は、 x2n-k(1−x)2n-k を展開したとき
    の x2n の係数である。

 よって、2nC0−2n-1C1+2n-2C2−・・・+(−1)nnCn は、

  x2n(1−x)2n+x2n-1(1−x)2n-1+x2n-2(1−x)2n-2+・・・+xn(1−x)n

を展開したときの x2n の係数である。ここで、

 x2n(1−x)2n+x2n-1(1−x)2n-1+x2n-2(1−x)2n-2+・・・+xn(1−x)n

に、xn-1(1−x)n-1+xn-2(1−x)n-2+・・・+x(1−x)+1 を加えても x2n の係数は変
わらない。

 このとき、x2n の係数は、次の展開により得られる。

  {1−x2n+1(1−x)2n+1}/{1−x(1−x)}={x2n+1(x−1)2n+1+1}/(x2−x+1)

 ここで、1/(x2−x+1)=(1+x)/(1+x3)=(1+x)(1−x3+x6−・・・) なので、

 x2n の係数は、

 (1+x)(1−x3+x6−・・・)
=1+x+0−x3−x4+0+x6+x7+0−x9−x10+0+・・・

から得られる。このことから、

 2n=6k すなわち、 n=3k のとき、 x2n の係数は、 1
 2n=6k+2 すなわち、 n=3k+1 のとき、 x2n の係数は、 0
 2n=6k+4 すなわち、 n=3k+2 のとき、 x2n の係数は、 −1  (証終)


(13) 2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn=22n

(証明) k=0、1、2、・・・、n に対して、2k・2n-kCn は、 2k(1+x)2n-k を展開したと
    きの xn の係数である。

 よって、 2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn は、

   (1+x)2n+2(1+x)2n-1+22(1+x)2n-2+・・・+2n(1+x)n

を展開したときの xn の係数である。

 ここで、

(1+x)2n+2(1+x)2n-1+22(1+x)2n-2+・・・+2n(1+x)n

=2n(1+x)n+2n-1(1+x)n+1+・・・+2(1+x)2n-1+(1+x)2n

=2n(1+x)n・{(1+x)n+1/2n+1−1}/{(1+x)/2−1}

={(1+x)2n+1−2n+1(1+x)n}/(x−1)

={2n+1(1+x)n−(1+x)2n+1}/(1−x)

 上式において、 1/(1−x)=1+x+x2+x3+・・・ なので、

 {2n+1(1+x)n−(1+x)2n+1}(1+x+x2+x3+・・・)

を展開したときの xn の係数である。

 2n+1(1+x)n(1+x+x2+x3+・・・) を展開したときの xn の係数は、

 2n+1(nC0+nC1+nC2+nC3+・・・+nCn)=2n+1・2n=22n+1

 (1+x)2n+1(1+x+x2+x3+・・・) を展開したときの xn の係数は、

 2n+1C0+2n+1C1+2n+1C2+・・・+2n+1Cn

 ところで、2n+1C0+2n+1C1+・・・+2n+1Cn+2n+1Cn+1+・・・+2n+1C2n+1=22n+1

において、2n+1Cn+1=2n+1Cn 、・・・、2n+1C2n+1=2n+1C0 なので、

 2(2n+1C0+2n+1C1+2n+1C2+・・・+2n+1Cn)=22n+1

より、 2n+1C0+2n+1C1+2n+1C2+・・・+2n+1Cn=22n

 以上から、求める xn の係数は、 22n+1−22n=22n となるので、

 2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn=22n

が成り立つ。  (証終)

(→ 組合せ論的証明)


(14) nC02+nC12+nC22+・・・+nCn2=2nCn

 (→ 参考:「パスカルの三角形」の(4) )

(証明) n 個の異なる赤球と、n 個の異なる白球がある。この異なる 2n 個のものから、異
    なる n 個のものをとる組合せの数 2nCn は、赤球の個数で場合分けして、赤球 k 個
    と白球 n−k 個をとる組合せの数の積 nCk・nCn-k =nCk2 の和に等しい。
                                                  (証終)

 (10)〜(13)の流れを考えると、次のような別証も考えられる。

(別証) nCk は、 (1+x)n を展開したときの xk の係数で、nCk=nCn-k である。

 よって、 (1+x)n=nC0+nC1x+nC2x2+・・・+nCn-1xn-1+nCnxn であり、

 (1+x)n=nCn+nCn-1x+nCn-2x2+・・・+nC1xn-1+nC0xn

 このとき、nC02+nC12+nC22+・・・+nCn2 は、

(nC0+nC1x+・・・+nCn-1xn-1+nCnxn)(nCn+nCn-1x+・・・+nC1xn-1+nC0xn)

すなわち、(1+x)n(1+x)n=(1+x)2n を展開したときの xn の係数に等しい。

 したがって、 2nCn である。  (別証終)

 この別証の考え方はとても大切なので、読者の方のために練習問題を置いておこう。

練習問題  次の等式が成り立つことを示せ。

 nCr+3・nCr-1+3・nCr-2+nCr-3=n+3Cr

(解) (1+x)n+3=(1+x)n(1+x)3 において、

(1+x)n+3 を展開したときの xr の係数が、n+3Cr

一方、(1+x)n を展開したときの xr の係数が、nCr で、(1+x)3 を展開したときの 1 の
   係数が、1

同様に、(1+x)n を展開したときの xr-1 の係数が、nCr-1 で、(1+x)3 を展開したときの
    x の係数が、3C1=3

(1+x)n を展開したときの xr-2 の係数が、nCr-2 で、(1+x)3 を展開したときの x2 の
係数が、3C2=3

(1+x)n を展開したときの xr-3 の係数が、nCr-3 で、(1+x)3 を展開したときの x3 の
係数が、3C3=1

なので、(1+x)n(1+x)3 を展開したときの xr の係数は、

 nCr+3・nCr-1+3・nCr-2+nCr-3

したがって、 nCr+3・nCr-1+3・nCr-2+nCr-3=n+3Cr が成り立つ。  (終)


#もちろん、nCr の定義式を用いて、地道に計算しても証明できる。


(15) nC02−nC12+nC22−・・・+(−1)nnCn2 の値は、k を整数として、

  n=2k のとき、 (−1)k2kCk 、n=2k+1 のとき、 0

(証明)  nCk は、 (1+x)n を展開したときの xk の係数で、nCk=nCn-k である。

 よって、 (1−x)n=nC0−nC1x+nC2x2−・・・+(−1)nnCnxn であり、

      (1+x)n=nCn+nCn-1x+nCn-2x2+・・・+nC1xn-1+nC0xn 

 このとき、nC02−nC12+nC22−・・・+(−1)nnCn2 は、

  (nC0−nC1x+・・・+(−1)nnCnxn)(nCn+nCn-1x+・・・+nC0xn)

すなわち、(1−x)n(1+x)n=(1−x2)n を展開したときの xn の係数に等しい。

 n=2k+1 のときは、明らかに、xn の係数は 0

 n=2k のとき、xn の係数は (−1)k2nCk である。  (証終)


(16) ヴァンデルモンドのたたみ込み

 nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0=n+mCk

(証明) nCk は、 (1+x)n を展開したときの xk の係数で、

 (1+x)n=nC0+nC1x+nC2x2+・・・+nCn-1xn-1+nCnxn

 (1+x)m=mC0+mC1x+mC2x2+・・・+mCm-1xm-1+mCmxm

このとき、 nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0 は、

 (1+x)n(1+x)m=(1+x)n+m を展開したときの xk の係数に等しい。

すなわち、 n+mCk である。  (証終)   (→ 組合せ論的証明) (→ 別証)


(17) 2n+1Cn+1+2n+1Cn+2+2n+1Cn+3+・・・+2n+1C2n+1=22n

(証明) 2項定理より、

 (1+x)2n+1=2n+1C0+2n+1C1x+2n+1C2x2+・・・+2n+1C2nx2n+2n+1C2n+1x2n+1

ここで、 x=1 とおくと、

 22n+1=2n+1C0+2n+1C1+2n+1C2+・・・+2n+1C2n+2n+1C2n+1

 また、(1)より、 2n+1C0=2n+1C2n+1 、2n+1C1=2n+1C2n 、・・・ なので、

22n+1=2n+1C2n+1+2n+1C2n+・・・+2n+1Cn+1+2n+1Cn+1+・・・+2n+1C2n+2n+1C2n+1

 =2(2n+1Cn+1+2n+1Cn+2+・・・+2n+1C2n+2n+1C2n+1)

より、 2n+1Cn+1+2n+1Cn+2+・・・+2n+1C2n+2n+1C2n+1=22n  (証終)


(18) nC0+3nC1+5nC2+・・・+(2n+1)nCn=(n+1)・2n

(証明) (1) nCr=nCn-r より、

 nC0=nCn
 3nC1=3nCn-1
 5nC2=5nCn-2
  ・・・・・・・・・
 (2n+1)nCn=(2n+1)nC0

よって、 S=nC0+3nC1+5nC2+・・・+(2n+1)nCn とおくと、

 S=(2n+1)nC0+(2n−1)nC1+(2n−3)nC2+・・・+3nCn-1+nCn

なので、

2S=2(n+1)(nC0+nC1+nC2+・・・+nCn-2+nCn-1+nCn)=2(n+1)・2n

よって、 nC0+3nC1+5nC2+・・・+(2n+1)nCn=(n+1)・2n  (証終)


 (6)の(イ)(ロ)の考え方を応用すれば、次の性質も容易だろう。


(19) nC0−nC2+nC4−nC6+・・・=2n/2cos(nπ/4)

(証明) (1+i)n=nC0+nC1i−nC2−nC3i+nC4+nC5i+・・・ において、

 nC0−nC2+nC4−nC6+・・・ は、(1+i)n の実部に等しい。

 ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

 (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

よって、 nC0−nC2+nC4−nC6+・・・=2n/2cos(nπ/4)  (証終)


(20) nC1−nC3+nC5−nC7+・・・=2n/2sin(nπ/4)

(証明) (1+i)n=nC0+nC1i−nC2−nC3i+nC4+nC5i+・・・ において、

 nC1−nC3+nC5−nC7+・・・ は、(1+i)n の虚部に等しい。

 ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

 (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

よって、 nC1−nC3+nC5−nC7+・・・=2n/2sin(nπ/4)  (証終)


(21) nC1+nC5+nC9+・・・=2n-2+2(n-2)/2・sin(nπ/4)

(証明) (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

(5)より、 −nC0+nC1−nC2+nC3−nC4+・・・−(−1)nnCn=0

また、−nC0i+nC1+nC2i−nC3−nC4i+nC5+・・・=−i・(1+i)n

  nC0i+nC1−nC2i−nC3+nC4i+nC5−・・・=i・(1−i)n

これらの4式を辺々加えて、

 4(nC1+nC5+nC9+・・・)=2n−i・(1+i)n+i・(1−i)n

ここで、ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

 (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

同様にして、 (1−i)n =2n/2(cos(nπ/4)−i・sin(nπ/4)) なので、

 4(nC1+nC5+nC9+・・・)=2n+2・2n/2sin(nπ/4) より、

 nC1+nC5+nC9+・・・=2n-2+2(n-2)/2sin(nπ/4)  (証終)


(22) nC2+nC6+nC10+・・・=2n-2−2(n-2)/2・cos(nπ/4)

(証明) (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

 (5)より、 nC0−nC1+nC2−nC3+nC4−・・・+(−1)nnCn=0

また、−nC0−nC1i+nC2+nC3i−nC4−nC5i+・・・=−(1+i)n

 −nC0+nC1i+nC2−nC3i−nC4+nC5i+・・・=−(1−i)n

これらの4式を辺々加えて、

 4(nC2+nC6+nC10+・・・)=2n−(1+i)n−(1−i)n

ここで、ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

 (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

同様にして、 (1−i)n =2n/2(cos(nπ/4)−i・sin(nπ/4)) なので、

 4(nC2+nC6+nC10+・・・)=2n−2・2n/2・cos(nπ/4)

より、 nC2+nC6+nC10+・・・=2n-2−2(n-2)/2・cos(nπ/4)  (証終)


(23) nC3+nC7+nC11+・・・=2n-2−2(n-2)/2・sin(nπ/4)

(証明) (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

 (5)より、 −nC0+nC1−nC2+nC3−nC4+・・・−(−1)nnCn=0

また、 nC0i−nC1−nC2i+nC3+nC4i−nC5−・・・=i・(1+i)n

  −nC0i−nC1+nC2i+nC3−nC4i−nC5+・・・=−i・(1−i)n

これらの4式を辺々加えて、

  4(nC3+nC7+nC11+・・・)=2n+i・(1+i)n−i・(1−i)n

ここで、ド・モアブルの定理より、 1+i =(cos(π/4)+i・sin(π/4)) なので、

  (1+i)n =2n/2(cos(nπ/4)+i・sin(nπ/4))

同様にして、 (1−i)n =2n/2(cos(nπ/4)−i・sin(nπ/4)) なので、

  4(nC3+nC7+nC11+・・・)=2n−2・2n/2sin(nπ/4)

より、 nC3+nC7+nC11+・・・=2n-2−2(n-2)/2sin(nπ/4)  (証終)


 (6)の(イ)の考え方を応用すれば、次の性質も容易だろう。


(24) nC0+nC3+nC6+・・・={2n+2cos(nπ/3)}/3 ((6)の(イ)再掲)

(証明) ω を1の虚数立方根とすると、ω=cos(2π/3)+i・sin(2π/3)  (i は虚数単位)

で、 1+ω+ω2=0 、ω3=1 である。このとき、

 nC0+nC1ω+nC2ω2+nC3+nC4ω+nC5ω2+・・・=(1+ω)n

 nC0+nC1ω2+nC2ω+nC3+nC4ω2+nC5ω+・・・=(1+ω2)n

また、 (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

 これらの3式を辺々加えて、 3(nC0+nC3+nC6+・・・)=2n+(1+ω)n+(1+ω2)n

ここで、

 1+ω=−ω2=−{cos(4π/3)+i・sin(4π/3)}=cos(π/3)+i・sin(π/3)
 1+ω2=−ω=−{cos(2π/3)+i・sin(2π/3)}=cos(π/3)−i・sin(π/3)

なので、  3(nC0+nC3+nC6+・・・)=2n+2cos(nπ/3)

 したがって、 nC0+nC3+nC6+・・・={2n+2cos(nπ/3)}/3  (証終)


(25) nC1+nC4+nC7+・・・={2n+2cos((n+4)π/3)}/3

(証明) ω を1の虚数立方根とすると、ω=cos(2π/3)+i・sin(2π/3)  (i は虚数単位)

で、 1+ω+ω2=0 、ω3=1 である。このとき、

 nC0ω2+nC1+nC2ω+nC3ω2+nC4+nC5ω+・・・=ω2(1+ω)n

 nC0ω+nC1+nC2ω2+nC3ω+nC4+nC5ω2+・・・=ω(1+ω2)n

 また、 (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

 これらの3式を辺々加えて、

 3(nC1+nC4+nC7+・・・)=2n+ω2(1+ω)n+ω(1+ω2)n

ここで、

 1+ω=−ω2=−{cos(4π/3)+i・sin(4π/3)}=cos(π/3)+i・sin(π/3)

より、

ω2(1+ω)n
=(cos(4π/3)+i・sin(4π/3))(cos(nπ/3)+i・sin(nπ/3))
=cos((n+4)π/3)+i・sin((n+4)nπ/3)

1+ω2=−ω=−{cos(2π/3)+i・sin(2π/3)}=cos(π/3)−i・sin(π/3)

より、

ω(1+ω2)n
=(cos(2π/3)+i・sin(2π/3))(cos(nπ/3)−i・sin(nπ/3))
=(cos(4π/3)−i・sin(4π/3))(cos(nπ/3)−i・sin(nπ/3))
=cos((n+4)π/3)−i・sin((n+4)nπ/3)

なので、 3(nC1+nC4+nC7+・・・)=2n+2cos((n+4)π/3)

 したがって、 nC1+nC4+nC7+・・・={2n+2cos((n+4)π/3)}/3  (証終)


(26) nC2+nC5+nC8+・・・={2n+2cos((n+2)π/3)}/3

(証明) ω を1の虚数立方根とすると、ω=cos(2π/3)+i・sin(2π/3)  (i は虚数単位)

で、 1+ω+ω2=0 、ω3=1 である。このとき、

 nC0ω+nC1ω2+nC2+nC3ω+nC4ω2+nC5+・・・=ω(1+ω)n

 nC0ω2+nC1ω+nC2+nC3ω2+nC4ω+nC5+・・・=ω2(1+ω2)n

 また、 (4)より、 nC0+nC1+nC2+nC3+nC4+・・・+nCn=2n

これらの3式を辺々加えて、

 3(nC2+nC5+nC8+・・・)=2n+ω(1+ω)n+ω2(1+ω2)n

ここで、 1+ω=−ω2=−{cos(4π/3)+i・sin(4π/3)}=cos(π/3)+i・sin(π/3)

より、

ω(1+ω)n
=(cos(2π/3)+i・sin(2π/3))(cos(nπ/3)+i・sin(nπ/3))
=cos((n+2)π/3)+i・sin((n+2)nπ/3)

1+ω2=−ω=−{cos(2π/3)+i・sin(2π/3)}=cos(π/3)−i・sin(π/3)

より、

ω2(1+ω2)n
=(cos(4π/3)+i・sin(4π/3))(cos(nπ/3)−i・sin(nπ/3))
=(cos(2π/3)−i・sin(2π/3))(cos(nπ/3)−i・sin(nπ/3))
=cos((n+2)π/3)−i・sin((n+2)nπ/3)

なので、 3(nC2+nC5+nC8+・・・)=2n+2cos((n+2)π/3)

したがって、 nC2+nC5+nC8+・・・={2n+2cos((n+2)π/3)}/3  (証終)


 FNさんが、上記の性質の組合せ論的な証明や解釈に取り組まれた。
                                      (平成23年3月25日付け)

 上記の性質の中で、組合せ論的な証明が可能な場合も多く、これもなかなか面白い。組
合せ論的な別証明を与えることを考えたい。組合せ論的な証明とは、場合の数を2通りで
考えることにより等式を導くことを意味するとしておく。

 (5)から(16)のうち、既に組合せ論的な証明が与えられている(14)以外について、組合せ
論的な証明を可能な範囲で与えることを目標としたい。

 2項係数 nCr において、r>n のとき、nCr=0 とする。

 また、1から n までの自然数全体の集合を、[n] で表す。1から n までの名前がついた n
人も同じ記号で表すものとする。

(5) nC0−nC1+nC2−nC3+・・・+(−1)rnCr+・・・+(−1)nnCn=0

(6) nC0+nC2+nC4+・・・=2n-1

をまとめると、

  nC0+nC2+・・・=nC1+nC3+・・・=2n-1

(組合せ論的解釈)

 [n] の中から何人かからなる班を作る。そのうちで、班の人数が偶数であるのが第1辺、
奇数であるのが第2辺。第3辺は、 n 人のうち、n−1人は入れるか入れないかを任意に
できる。これが、2n-1通り。最後の1人は、班の人数が偶数か奇数かで入れる入れないが
ただ1通りに定まる。

(7) nC1+2nC2+3nC3+・・・+rnCr+・・・+nnCn=n・2n-1

(組合せ論的証明)

 [n] の中から何人か(0人ではない)からなる班を作り、かつ、その班長を選ぶ場合の数を考
える。左辺は、1人、2人、3人、・・・ からなる班を作り班長を選ぶとして数えたもので、右辺
は、まず班長を選び、残った人をその班に入れるか入れないかを数えたものである。(証終)

(7) nC1+2nC2+3nC3+・・・+rnCr+・・・+nnCn=n・2n-1

(8) nC1−2nC2+3nC3−・・・+r(−1)r-1nCr+・・・+n(−1)n-1nCn=0

をまとめると、

  nC1+3nC3+5nC5+・・・=2nC2+4nC4+6nC6+・・・=n・2n-2

(組合せ論的解釈)

 [n] の中から何人か(0人ではない)からなる班を作り、かつ、その班長を選ぶ。そのうちで、
班の人数が奇数であるのが第1辺、偶数であるのが第2辺。第3辺は、まず、班長を選ん
で、残りの n−1人のうち n−2人は入れるか入れないかを任意にできる。これが、2n-2通
り。最後の1人は班の人数が偶数か奇数かで入れる入れないがただ1通りに定まる。
よって、n・2n-2通り。

(9) nC0+(1/2)nC1+(1/3)nC2+(1/4)nC3+・・・+(1/(n+1))nCn

  =(2n+1−1)/(n+1)


(組合せ論的証明)

 両辺に、n+1 をかけて、
 (n+1)nC0+(n+1)nC1/2+・・・+(n+1)nCn/(n+1)=2n+1−1
を示す。[n+1] の中から何人か(0人ではない)からなる班を作る場合の数を数えて、
2n+1−1 で、これが右辺である。また、左辺は、班長を選んで、そこに 0人、1人、2人、・・・
の班員をつけると考えた上で、実際には班長が誰かは問題にしないから、班長が違うだけの
班分けを同じとみなした場合である。  (証終)

(11) nCk+n+1Ck+n+2Ck+・・・+n+mCk=n+m+1Ck+1−nCk+1

(組合せ論的証明)

 nCk+1 を移項した形
 nCk+n+1Ck+n+2Ck+・・・+n+mCk+nCk+1=n+m+1Ck+1
で証明する。赤玉1、2、3、・・・、m+1と白玉n個からk+1個を取り出す場合の数は、
n+m+1Ck+1通りで、これが右辺である。左辺は、特別な赤玉に着目して場合分けを行う。
赤玉1を含み2以上は含まないとき、nCk
赤玉2を含み3以上は含まないとき、赤玉1と n個の白玉の計 n+1個から k個とるので、
n+1Ck
 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
赤玉mを含みm+1は含まないとき、n+m-1Ck
赤玉m+1を含むとき、n+mCk
赤玉を含まないとき、nCk+1
これらの合計が左辺となる。  (証終)

(13) 2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn=22n

 少し一般化して、次の形

(13A) nCk+2・n-1Ck-1+4・n-2Ck-2+・・・+2k・n-kC0

   =n+1C0+n+1C1+n+1C2+・・・+n+1Ck


にしたものを示す。(平成23年3月29日付け)

 ここで、(13A)において、n を 2n、k を n とすると、
左辺=2nCn+2・2n-1Cn-1+4・2n-2Cn-2+・・・+2n・nC0
 =2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn
より、(13)の左辺に等しくなり、また、
右辺=2n+1C0+2n+1C1+2n+1C2+・・・+2n+1Cn
 =2n+1C2n+1+2n+1C2n+2n+1C2n-1+・・・+2n+1Cn+1
で、
(2n+1C0+2n+1C1・・・+2n+1Cn)+(2n+1C2n+1+2n+1C2n+・・・+2n+1Cn+1)=22n+1
より、 右辺=22n となり、(13)の右辺に等しくなる。

(13Aの証明) Aを、[n+1] の部分集合で要素の個数が k 以下であるものとする。
 右辺は、そのような部分集合の個数である。
今、[n+1] の部分集合で次のものを考える。
 A[1] : 1 を含まないで、2以上の要素の個数が k 個であるもの
 A[2] : 2 を含まないで、3以上の要素の個数が k−1 個であるもの
 A[3] : 3 を含まないで、4以上の要素の個数が k−2 個であるもの
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 A[r] : r を含まないで、r+1以上の要素の個数が k−r+1 個であるもの
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 A[k] : k を含まないで、k+1以上の要素の個数が 1 個であるもの
 A[k+1] : k+1 を含まないで、k+2以上の要素の個数が 0 個であるもの
このとき、
 A[1]に含まれる部分集合の個数は、nCk
 A[2]に含まれる部分集合の個数は、
  まず、2 を含まないで、3以上の要素の個数が k−1 個であるものは、n-1Ck-1個ある
 が、その1通りに対して、要素1を付加する場合と付加しない場合の2通りがあるので、
 2・n-1Ck-1 となる。
 A[3]に含まれる部分集合の個数は、
  まず、3 を含まないで、4以上の要素の個数が k−2 個であるものは、n-2Ck-2個ある
 が、その1通りに対して、要素1、要素2を付加する場合と付加しない場合が、それぞれ
 22=4通りがあるので、 4・n-2Ck-2 となる。
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 このことから、左辺は、A[1]、A[2]、・・・、A[k+1]に含まれる部分集合の個数の総和
に等しい。

 このとき、集合Aが、A[1]、A[2]、・・・、A[k+1]の直和になることを示せば、証明は
完了するが、それは、それほど明らかではない...。こんなに無理をしないで、ごく自然
にやるのなら数学的帰納法だろう。nCr=n-1Cr+n-1Cr-1 だけで簡単にできる!


 (13A)が、n、kで成り立つとして、n+1、k+1のときを考える。
 n+2C0+n+2C1+n+2C2+・・・+n+2Ck+1
=n+1C0+(n+1C1+n+1C0)+(n+1C2+n+1C1)+・・・+(n+1Ck+1+n+1Ck)
=2(n+1C0+n+1C1+n+1C2+・・・+n+1Ck)+n+1Ck+1
=2(nCk+2・n-1Ck-1+4・n-2Ck-2+・・・+2k・n-kC0)+n+1Ck+1
=n+1Ck+1+2・nCk+4・n-1Ck-1+8・n-2Ck-2+・・・+2k+1・n-kC0
となり、数学的帰納法は成立する。  (証終)

(16) nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0=n+mCk

(組合せ論的証明)

 赤玉n個、白玉m個からk個を取り出す場合の数は、n+mCk 通りで、これが右辺である。
左辺は、赤玉・白玉の個数に着目して場合分けを行う。
赤が0個で白がk個のとき、nC0・mCk
赤が1個で白がk−1個のとき、nC1・mCk-1
 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
赤がk個で白が0個のとき、nCk・mC0
これらの合計が左辺となる。  (証終)

(補足) 平成23年5月1日付け

 上記の(16)の組合せ論的証明として、次のように示してもよい。

 まず、次の補題を示す。

補題  nCm+n-1Cm-1+n-2Cm-2+・・・+n-mC0=n+1Cm

(証明) 性質(11):nCk+n+1Ck+n+2Ck+・・・+n+mCk=n+m+1Ck+1−nCk+1

を用いる。ここで、性質(1):nCr=nCn-r から、

 nCm+n-1Cm-1+n-2Cm-2+・・・+n-mC0=n+1Cm

を示すためには、 nCn-m+n-1Cn-m+n-2Cn-m+・・・+n-mCn-m=n+1Cm

すなわち、逆順に加えて、

 n-mCn-m+n-m+1Cn-m+・・・+n-m+(m-1)Cn-m+n-m+mCn-m=n+1Cm

を示せばよい。これは、性質(11)から、

 左辺=(n-m)+m+1C(n-m)+1=n+1Cn-m+1=n+1Cm=右辺

となり示された。 (証終)

 (組合せ論的証明)として、次のように示してもよい。

(別証明) 縦の道の本数が、n−m+2本、横の道の本数が、m+1本の市街路を考える。

 

 A → B の最短経路は、 n+1Cm 通り
ところで、 A → P → B の最短経路は、 nCm 通り
 A → Q’ → Q → B の最短経路は、 n-1Cm-1 通り
 A → R’ → R → B の最短経路は、 n-2Cm-2 通り
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 A → S’ → S → B の最短経路は、 n-mC0 通り
なので、 nCm+n-1Cm-1+n-2Cm-2+・・・+n-mC0=n+1Cm  (別証終)


 また、次のような別証も考えられる。

(別証明) r=0、1、2、・・・、m において、n-rCm-r は、 xr(1+x)n-r を展開したときの
  xm の係数である。ここで、

(1+x)n+x(1+x)n-1+x2(1+x)n-2+・・・+xm(1+x)n-m
=(1+x)n{1−xm+1/(1+x)m+1}/{1−x/(1+x)}
=(1+x)n+1{1−xm+1/(1+x)m+1}
=(1+x)n+1−xm+1(1+x)n-m
なので、xm の係数は、n+1Cm に等しい。
 よって、 nCm+n-1Cm-1+n-2Cm-2+・・・+n-mC0=n+1Cm  (別証終)

 上記の補題を一般化して、次の定理を得る。

定理  nCm・kC0+n-1Cm-1・k+1C1+・・・+n-mC0・k+mCm=n+k+1Cm

(証明) 縦の道の本数が、n−m+k+2本、横の道の本数が、m+1本の市街路を考える。



A → B の最短経路は、 n+k+1Cm 通り
ところで、 A → P → B の最短経路は、 kC0・nCm 通り
 A → Q → B の最短経路は、 k+1C1・n-1Cm-1 通り
 A → R → B の最短経路は、 k+2C2・n-2Cm-2 通り
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 A → S → B の最短経路は、 k+mCm・n-mC0 通り
なので、
 nCm・kC0+n-1Cm-1・k+1C1+・・・+n-mC0・k+mCm=n+k+1Cm  (証終)

 この定理の証明と同様にして、次の性質(16):

 nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0=n+mCk

の別証が考えられる。

(別証明) 縦の道の本数が、n+m−k+1本、横の道の本数が、k+1本の市街路を考える。

 

A → B の最短経路は、 n+mCk 通り
ところで、 A → P → B の最短経路は、 mC0・nCk 通り
 A → Q → B の最短経路は、 mC1・nCk-1 通り
 A → R → B の最短経路は、 mC2・nCk-2 通り
   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
 A → S → B の最短経路は、 mCk・nC0 通り
なので、
 nC0・mCk+nC1・mCk-1+・・・+nCk・mC0=n+mCk  (別証終)

(コメント) FNさんの赤玉・白玉の個数に着目した場合分けと同趣旨ですが、目先を少し
      変えたということで...f(^_^;)。


 残ったのは、(10)(12)(15)(17)(18)(19)(20)(21)(22)(23)(24)(25)(26)です。

 これらについて、組合せ論的な証明は可能でしょうか。


 自然数 n の階乗 n!は、 n!=n(n−1)(n−2)・・・3・2・1 で求められる。

これは、異なる n 個のものの順列の数に等しい。この考え方を一般化して、

 異なる n 個のものから異なる r 個をとる順列の数 nPr は、

 nPr=n(n−1)(n−2)・・・(n−r+1)

で求められる。そこで、整数 a、h に対して、上記のアナロジーを考える。

 n 個の因数 a 、a−h 、a−2h 、a−3h 、・・・ 、a−(n−1)h の積を、a(n) と表す
ことにする。

すなわち、 a(n) =a(a−h)(a−2h)(a−3h)・・・(a−(n−1)h)

例 h=0 のとき、 a(n) =a・a・・・・・a=an で、a の n 乗に等しい。
  h=1 のとき、 a(n) =a(a−1)(a−2)・・・(a−n+1)=aPn である。
    特に、 n(n) =n! である。
 また、 n=0 のとき、 a(0) =1 で、 n=1 のとき、 a(1) =a である。

  よって、n=0、1 については、a(n) は、an と同じ感覚でいいということになる。

例 (a+b)(1) =a+b
  (a+b)(2) =(a+b)(a+b−h)=(a+b)2−(a+b)h=a2+2ab+b2−ah−bh
 =a(a−h)+2ab+b(b−h)=a(2)+2a(1)b(1)+b(2)
すなわち、 (a+b)(2) =a(2)+2a(1)b(1)+b(2) となり、何となく平方の公式
 (a+b)2=a2+2ab+b2
に似ている。同様に、
  (a+b)(3) =(a+b)(a+b−h)(a+b−2h)
 =(a+b)3−3(a+b)2h+2(a+b)h2
 =a3+3a2b+3ab2+b3−3a2h−6abh−3b2h+2ah2+2bh2
 =a3−3a2h+2ah2+3a2b−6abh+3ab2+b3−3b2h+2bh2
 =a(a−h)(a−2h)+3a(a−h)b+3ab(b−h)+a(a−h)(a−2h)
 =a(3)+3a(2)b(1)+3a(1)b(2)+b(3)
すなわち、 (a+b)(3) =a(3)+3a(2)b(1)+3a(1)b(2)+b(3) が成り立つ。


(コメント) a(n) について、2項定理と同様の式が成り立つようで面白いですね!

 上式は、 (a+b)(3) =(a+b)(2)(a+b−2h)=(a(2)+2a(1)b(1)+b(2))(a+b−2h)
      =a(2)(a+b−2h)+2a(1)b(1)(a+b−2h)+b(2)(a+b−2h)
      =a(3)+a(2)b+2a(1)b(1)(a−h)+2a(1)b(1)(b−h)+ab(2)+b(3)
      =a(3)+3a(2)b(1)+3a(1)b(2)+b(3)
としても求められる。上記を一般化して、

階乗2項定理

 (a+b)(n)=nC0a(n)+nC1a(n-1)b(1)+nC2a(n-2)b(2)+・・・+nCnb(n)

が成り立つことを数学的帰納法により示しておこう。

(証明) n=1 のとき、 (a+b)(1) =a+b=1C0a(1)+1C1b(1) より成り立つ。
 n=k(k≧1)のとき、成り立つと仮定する。すなわち、
  (a+b)(k)=kC0a(k)+kC1a(k-1)b(1)+kC2a(k-2)b(2)+・・・+kCkb(k)
このとき、
(a+b)(k+1)
= (a+b)(k)(a+b−kh)
=(kC0a(k)+kC1a(k-1)b(1)+kC2a(k-2)b(2)+・・・+kCkb(k))(a+b−kh)
=kC0a(k)(a+b−kh)+kC1a(k-1)b(1)(a+b−kh)+kC2a(k-2)b(2)(a+b−kh)+
                                       ・・・+kCkb(k)(a+b−kh)
=k+1C0a(k+1)+kC0a(k)b+kC1a(k-1)b(1)(a−(k−1)h+b−h)
                                     +・・・+kCkb(k)(a+b−kh)
=k+1C0a(k+1)+kC0a(k)b(1)+kC1a(k)b(1)+kC1a(k-1)b(2)+
                                     +・・・+kCkb(k)(a+b−kh)
=k+1C0a(k+1)+k+1C1a(k)b(1)+k+1C2a(k-1)b(2)+・・・+k+1Ck+1b(k+1)
となり、n=k+1 のときも成り立つ。
 したがって、すべての自然数 n について、
   (a+b)(n)=nC0a(n)+nC1a(n-1)b(1)+nC2a(n-2)b(2)+・・・+nCnb(n)
が成り立つ。  (証終)

 この階乗2項定理を用いると、

(16) nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0=n+mCk

は次のようにも示すことが出来る。

(別証) nCr=n(n−1)・・・(n−(r−1))/r!=n(r)/r! (← h=1)
 同様に、 mCk−r=m(m−1)・・・(m−(k−r−1))/(k−r)!=m(k−r)/(k−r)!
 よって、 nCr・mCk−r=n(r)/r!・m(k−r)/(k−r)!
               =kCrn(r)m(k−r)/k!  (r=0、1、2、・・・、k)
 ここで、 kCrn(r)m(k−r) は、(n+m)(k) の第 r+1 項なので、その総和は、
  (n+m)(k) /k!=(n+m)(n+m−1)・・・(n+m−k+1)/k!=n+mCk
 に等しい。  (別証終)

 階乗2項定理を用いて、次の性質も示される。

(27) nC0・mCk−n+1C1・mCk-1+・・・+(−1)kn+kCk・mC0=m-n-1Ck

(証明) (−1)rn+rCr=(−1)r(n+r)(n+r−1)・・・(n+1)/r!
             =(−n−1)(−n−2)・・・(−n−r)/r!
             =(−n−1)(r)/r! (← h=1)
 同様に、 mCk−r=m(m−1)・・・(m−(k−r−1))/(k−r)!=m(k−r)/(k−r)!
 よって、(−1)rn+rCr・mCk−r=(−n−1)(r)/r!・m(k−r)/(k−r)!
                   =kCr(−n−1)(r)m(k−r)/k!  (r=0、1、2、・・・、k)
 ここで、kCr(−n−1)(r)m(k−r) は、(m−n−1)(k) の第 r+1 項なので、
その総和は、 (m−n−1)(k) /k!=m-n-1Ck  に等しい。  (証終)

 上記のいろいろな性質の証明で、展開公式:

Newtonの2項定理

 (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCrxr+・・・+nCnxn

の有用性が確かめられた。同様の議論を、(1+x+x2)n においても行いたい。

 具体的な場合については、「パスカルの三角形」で調べられている。そこでは「井上の三角
形
」というものが活躍した。

 いま、(1+x+x2)n を展開して、

  (1+x+x2)n=nB0+nB1x+nB2x2+nB3x3+・・・+nB2nx2n

と、各項の係数を定める。

例 n=0 のとき、 (1+x+x2)0=1 より、 0B0=1
  n=1 のとき、 (1+x+x2)1=1+x+x2 より、 1B0=1 、1B1=1 、1B2=1
  n=2 のとき、 (1+x+x2)2=1+2x+3x2+2x3+x4 より、
      2B0=1 、2B1=2 、2B2=3 、2B3=2 、2B4=1
 nB0 、nB1 、nB2 、・・・ 、nB2n について、次の性質が成り立つ。

(B1) nBk=nB2n-k

(証明) (1+x+x2)n=nB0+nB1x+・・・+nBkxk+・・・+nB2nx2n の x に、1/x を代
    入して、
 (1+1/x+1/x2)n=nB0+nB1/x+・・・+nBk/xk+・・・+nB2n/x2n
両辺に、x2n を掛けて、
 (1+x+x2)n=nB0x2n+nB1x2n-1+・・・+nBkx2n-k+・・・+nB2n
=nB2n+nB2n-1x+・・・+nB2n-kxk+・・・+nB1x2n-1+nB0x2n
よって、xk の係数を比較して、 nBk=nB2n-k が成り立つ。  (証終)

(B2) n+1Bk=nBk-2+nBk-1+nBk

 (ただし、k<0 または k>2n のとき、nBk=0 とする。)

(証明) n+1Bk は、(1+x+x2)n+1 を展開したときの xk の係数である。一方、
 (1+x+x2)n+1=(1+x+x2)n・(1+x+x2)
=(nB0+・・・+nBk-2xk-2+nBk-1xk-1+nBkxk+・・・+nB2nx2n)・(1+x+x2)
を展開したときの xk の係数は、 nBk-2+nBk-1+nBk
よって、 n+1Bk=nBk-2+nBk-1+nBk が成り立つ。  (証終)

(B3) nB0+nB1+nB2+・・・+nB2n=3n

(証明) (1+x+x2)n=nB0+nB1x+nB2x2+・・・+nB2nx2n において、
  x=1 とおくと、 nB0+nB1+nB2x2+・・・+nB2n=3n  (証終)

(B4) nB0−nB1+nB2−・・・+nB2n=1

(証明) (1+x+x2)n=nB0+nB1x+nB2x2+・・・+nB2nx2n において、
  x=−1 とおくと、 nB0−nB1+nB2−・・・+nB2n=1  (証終)

(B5) nB02+nB12+nB22+・・・+nB2n2=2nB2n

(証明) (1+x+x2)n=nB0+nB1x+nB2x2+・・・+nB2nx2n において、
 nBk=nB2n-k より、
 (1+x+x2)n=nB2n+nB2n-1x+nB2n-2x2+・・・+nB0x2n
このとき、 nB02+nB12+nB22+・・・+nB2n2 は、
 (1+x+x2)n(1+x+x2)n=(1+x+x2)2n
を展開したときの x2n の係数に等しい。しかるに、それは、 2nB2n
よって、 nB02+nB12+nB22+・・・+nB2n2=2nB2n  (証終)

 (8)を一般化して、次の性質を得る。

(28) 1knC1−2knC2+3knC3−・・・+(−1)n-1nknCn=0 (k<n)

   1nnC1−2nnC2+3nnC3−・・・+(−1)n-1nnnCn=(−1)n-1n!

  k=1 のときは、 k・nCk=n・n-1Ck-1 という公式が有効であったが、k>2 につ
 いては別な方策が必要である。

 そこで、次の問題を考える。

 箱1、箱2、・・・、箱n が1列に番号順に置かれている。この n 個の箱に、異なる
k 個の球を任意に入れていく。
 このとき、それぞれの箱に少なくとも1個の球が入っている場合の数を求めよ。


(解) 異なる k 個の球を、n 個の箱に入れる場合の数は、nk 通りある。この中には、何
  れかの箱が空になっている場合も含まれる。この場合の数は、
   nC1・(n−1)k−nC2・(n−2)k+・・・−(−1)n-1nCn-1・1k
  よって、それぞれの箱に少なくとも1個の球が入っている場合の数は、包除原理により、
   nk−nC1・(n−1)k+nC2・(n−2)k−・・・+(−1)n-1nCn-1・1k  (終)

 上式を用いて、(28)は、次のように示される。

((28)の証明) nCr=nCn-r より、上式は、
   nCnnk−nCn-1・(n−1)k+nCn-2・(n−2)k−・・・+(−1)n-1nC1・1k
 とも書き直せる。 k<n のとき、この場合の数は、明らかに 0 である。
  すなわち、
   nCnnk−nCn-1・(n−1)k+nCn-2・(n−2)k−・・・+(−1)n-1nC1・1k=0
 両辺に、(−1)n-1 を掛けて、
      (−1)n-1nCnnk+・・・+nC3・3k−nC2・2k+nC1・1k=0
 すなわち、 1knC1−2knC2+3knC3−・・・+(−1)n-1nknCn=0 が成り立つ。
 k=n のとき、この場合の数は、明らかに n! である。
  すなわち、
   nCnnn−nCn-1・(n−1)n+nCn-2・(n−2)n−・・・+(−1)n-1nC1・1n=n!
 両辺に、(−1)n-1 を掛けて、
      (−1)n-1nCnnn+・・・+nC3・3n−nC2・2n+nC1・1n=(−1)n-1n!
 すなわち、
  1nnC1−2nnC2+3nnC3−・・・+(−1)n-1nnnCn=(−1)n-1n!
 が成り立つ。  (証終)

(29) p を素数とする。このとき、次の等式が成り立つ。

(イ) p-1Ck≡(−1)k (mod p)  ただし、 0≦k≦p−1

(ロ) p+1Ck≡0 (mod p)  ただし、 2≦k≦p−1

(ハ) paCpb≡aCb (mod p)  ただし、 a≧b≧0

(ニ) 2pCp≡2 (mod p)


 上記の性質を、FNさんが示された。(平成23年5月19日付け)

 2項係数の p を法としての値については、

 pCk≡0 (mod p)  ただし、0<k<p

が基本的です。

実際に、 pCk=p(p−1)・・・(p−k+1)/k! は整数で、p(p−1)・・・(p−k+1)は
 k!で割り切れるが、p は素数なので、(p−1)(p−2)・・・(p−k+1)が k!で割り切れ
る。よって、pCk は、p で割り切れる。

 これから、 (1+x)p≡1+xp (mod p) が成り立つ。

 これを使えば証明できます。(ハ)以外は使わないでも証明できますが、(ハ)は今のところ
使わない証明はわかりません。

(イ)の証明:  (1+x)p-1≡(1+xp)/(1+x)=1−x+x2−x3+・・・+xp-1 より明らか。

(ロ)の証明:  (1+x)p+1≡(1+xp)(1+x)=1+x+xp+xp+1 より明らか。

(ハ)の証明:  (1+x)pa≡(1+xp)a より明らか。

(ニ)の証明:  (ハ)で、a=2、b=1 とおけばよい。

 (別証)    (1+x)2p≡(1+xp)2=1+2xp+x2p より明らか。


 (1+x)p≡1+xp (mod p) を使わない証明も考えてみました。

(イ)の別証: 分母は、k!、分子は≡(−1)k・k! (mod p) より明らか。

(ロ)の別証:  分子は素因数 p を含み分母は含まないから。

(ニ)の別証: 「 (14) nC02+nC12+nC22+・・・+nCn2=2nCn 」で、n=p とする。

 pC02+pC12+pC22+・・・+pCp2=2pCp より、成り立つ。


(追記) 当HP読者のHN「ezofuji_z」さんが、(29)の拡張について考察された。
                                       (平成25年8月18日付け)

(29)’ p を素数とする。このとき、次の等式が成り立つ。

(イ)’ pe-1Ck≡(−1)k (mod p)  ただし、 0≦k≦pe−1

(ロ)’ pe+hCk≡0 (mod p)  ただし、 0≦h≦p−1、h<k<pe

 このように、(29)は「pe バージョン」に拡張されます。

※ 特に、h=0のときは、 pCk≡0 (mod p) の拡張となってます。

※ また、e=1のときも、 1<h<k<pの範囲で、ささやかですが拡張されています。

(ハ)’ 0≦h、k≦p−1 のとき、

  h≧k ならば、pa+hCpb+k≡aCb・hCk (mod p)

  h<kならば、pa+hCpb+k≡0 (mod p)  ただし、 pa+h≧pb+k≧0

 証明は、(1+x)pa+h≡(1+xp)a・(1+x)h (mod p) を使えばよいです。

(ハ)’を繰り返し使うと(帰納法により)、次のことが示されます。 

 n≧k をp進表示したpmの位の数を各々 hm、km(0≦hm、km≦p−1)として、

  n=he・pe + he-1・pe-1 + … + h1・p + h0 (he>0)、

  k=ke・pe + ke-1・pe-1 + … + k1・p + k0 (he≧ke)

と表わすとき、

・ hm≧km (0≦∀m≦e) ならば、 nCk ≡ Πm= 0〜e hmCkm ≠0 (mod p)

・ 0≦∃m<e に対して、 hm<km  ならば、 nCk ≡0 (mod p)

 最初に述べた(イ)、(ロ)の拡張バージョン(イ)’、(ロ)’は、この結果の特別な場合として示
すことができます。
(もちろん合同多項式を使ったり、組合せ論的な直接証明も可能と思います。)


 さらに、FNさんは、「岩波の数学公式�U」に載っている2項係数の公式で、このページにな
いものとして、3つあげられた。(平成23年5月19日付け)

(30) 12nC1+22nC2+32nC3+・・・+n2nCn=n(n+1)・2n-2

(31) nC0−(1/2)nC1+(1/3)nC2−・・・+(−1)n(1/(n+1))nCn=1/(n+1)

(32) nC12+2・nC22+3・nC32+・・・+n・nCn2=n・2n-1Cn

 証明を考えてみてください。


 このFNさんの問いかけに対し、at さんが証明された。(平成23年5月21日付け)

(30) 12nC1+22nC2+32nC3+・・・+n2nCn=n(n+1)・2n-2

(証明) (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCnxn において、
 両辺を x で微分して、さらに両辺に x を掛けて、
 nx(1+x)n-1=nC1x+2nC2x2+3nC3x3+・・・+nnCnxn
 さらに、両辺を x で微分して、さらに両辺に x を掛けて、
nx(1+x)n-1+n(n−1)x2(1+x)n-2=nC1x+22nC2x2+32nC3x3+・・・+n2nCnxn
 この等式において、x=1 を代入して、
 n・2n-1+n(n−1)・2n-2=nC1+22nC2+32nC3+・・・+n2nCn
すなわち、 12nC1+22nC2+32nC3+・・・+n2nCn=n(n+1)・2n-2  (証終)

(31) nC0−(1/2)nC1+(1/3)nC2−・・・+(−1)n(1/(n+1))nCn=1/(n+1)

(証明) (1−x)n=nC0−nC1x+nC2x2−nC3x3+・・・+(−1)nnCnxn の両辺を、
 x=0 から x=t まで定積分し、さらに両辺を t でわって、
{1−(1−t)n+1}/{t(n+1)}=nC0−nC1t/2+nC2t2/3−・・・+(−1)nnCntn/(n+1)
 この等式において、t=1 を代入して、
 1/(n+1)=nC0−nC1(1/2)+nC2(1/3)−・・・+(−1)nnCn(1/(n+1))
すなわち、
 nC0−(1/2)nC1+(1/3)nC2−・・・+(−1)n(1/(n+1))nCn=1/(n+1)  (証終)

(32) nC12+2・nC22+3・nC32+・・・+n・nCn2=n・2n-1Cn

(証明) nx(1+x)n-1=nC1x+2nC2x2+3nC3x3+・・・+nnCnxn ・・・(イ)
 (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCnxn  において、
nCk=nCn-k より、
 (1+x)n=nCn+nCn-1x+nCn-2x2+nCn-3x3+・・・+nC0xn ・・・(ロ)
よって、(イ)と(ロ)を辺々掛けて、
 nx(1+x)2n-1
=(nC1x+2nC2x2+・・・+nnCnxn)(nCn+nCn-1x+nCn-2x2+・・・+nC0xn)
において、両辺の xn の係数を比較して、
 左辺=n・2n-1Cn-1=n・2n-1Cn
 右辺=nC12+2・nC22+3・nC32+・・・+n・nCn2
よって、 nC12+2・nC22+3・nC32+・・・+n・nCn2=n・2n-1Cn  (証終)


(コメント) at さんに感謝します。


 FNさんからのコメントです。(平成23年5月21日付け)

 やはり2項定理を使った証明が普通ですよね。私は組合せ論的な証明が好きなのでそれ
にこだわってしまいます。

(30) 12nC1+22nC2+32nC3+・・・+n2nCn=n(n+1)・2n-2

(証明) n 人から何人かを選び、かつ、班長と副班長を選ぶ。ただし、班長が副班長を兼任
 してもよい。この場合の数を2通りの方法で考える。
 r 人を選ぶ場合の数は、nCr 通り。この中から、班長と副班長を選ぶ場合の数は、
r(r−1) 通りで、班長が副班長を兼任する場合は、r 通り。
 よって、 r(r−1)+r=r2 から、r2・nCr となり、左辺が求められる。
 一方、班長と副班長を選び、残りの n−2人を適当に選ぶ場合の数は、
  n(n−1)・2n-2 通り
 班長=副班長を選び、残りの n−1人を適当に選ぶ場合の数は、 n・2n-1 通り
したがって、n(n−1)・2n-2+n・2n-1=n(n+1)・2n-2 より、左辺となる。 (証終)

 上記の証明で、班長が副班長を兼任してもよいのは不自然で、自然なのは次の式で
しょう。

 1・0・nC1+2・1・nC2+3・2・nC3+・・・+n(n-1)・nCn=n(n−1)・2n-2

そこで、(7) nC1+2nC2+3nC3+・・・+rnCr+・・・+nnCn=n・2n-1 より、

 nC1+2・nC2+3・nC3+・・・+nnCn=2n・2n-2

を辺々加えて、 r(r−1)+r=r2 から、与式の成り立つことが分かる。

(31) nC0−(1/2)nC1+(1/3)nC2−・・・+(−1)n(1/(n+1))nCn=1/(n+1)

(証明) 両辺に、n+1 をかけると、左辺の項は、nCr・(n+1)/(r+1)=n+1Cr+1 で、分母
 を払えば、 (n+1)・nCr=n+1Cr+1・(r+1) で、n+1人からr+1人を選び、かつ、
 班長を選ぶ場合の数であることがわかる。このとき、
 左辺×(n+1)=n+1C1−n+1C2+n+1C3−・・・+(−1)nn+1Cn+1
 (5) nC0−nC1+nC2−nC3+・・・+(−1)nnCn=0
 より、 n+1C0−n+1C1+n+1C2−n+1C3+・・・−(−1)nn+1Cn+1=0 なので、
 n+1C1−n+1C2+n+1C3−・・・+(−1)nn+1Cn+1=n+1C0=1=右辺×(n+1)
よって、 左辺=右辺 が成り立つ。  (証終)

(32) nC12+2・nC22+3・nC32+・・・+n・nCn2=n・2n-1Cn

(証明) 男子 n 人、女子 n 人合わせて 2n 人から n 人を選び、かつ、班長を選ぶ。
 ただし、班長は女子とする。この場合の数を、2通りの方法で数える。
 女子が r 人の場合、女子の選び方は、nCr 通りで、男子の選び方は、nCn-r=nCr通り。
 その1通りに対して、班長の選び方は、r 通り。
よって、 nCr・nCn-r・r=r・nCr2 となり、左辺が求められる。
一方、まず、班長を選ぶ場合の数が、n 通り。残った 2n−1人から n−1人を選ぶので、
 n・2n-1Cn-1=n・2n-1Cn となり、右辺となる。  (証終)

(33) 1・2・nC2+2・3・nC3+・・・+(n−1)・n・nCn=(n−1)n・2n-2

(証明)  (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCnxn において、
 両辺を2回微分して、
 n(1+x)n-1=nC1+2nC2x+3nC3x2+・・・+nnCnxn-1
 (n−1)n(1+x)n-2=1・2・nC2+2・3・nC3x+・・・+(n−1)・n・nCnxn-2
 x=1 とおくと、
 1・2・nC2+2・3・nC3+・・・+(n−1)・n・nCn=(n−1)n・2n-2  (証終)

(34)
    

(証明)
    


(コメント) 2項係数の性質を使い切っていないかな?上記のように計算するんだったら最
      初から

 

として計算した方がいいかも...。

 上記では、組合せの数を数に置き換えて計算してしまったが、もう少し我慢して計算を続
けると規則性が見えてくる。

 これだと一般の場合も数学的帰納法で証明出来そうな...そんな雰囲気。


               
               

 当HPの読者のHN「らい」さんより、

(14) nC02+nC12+nC22+・・・+nCn2=2nCn

の一般化として、次の性質

(35) nC0・nCm+nC1・nCm+1+・・・+nCn-m・nCn=2nCn-m (0≦m≦n)

が成り立つ旨、ご教示いただいた。らいさんに感謝します。(平成23年11月6日付け)

(証明) nCk は、 (1+x)n を展開したときの xk の係数で、nCk=nCn-k である。
 よって、 (1+x)n=nC0+nC1x+nC2x2+・・・+nCn-1xn-1+nCnxn であり、
  (1+x)n=nCn+nCn-1x+nCn-2x2+・・・+nC1xn-1+nC0xn 
 このとき、 nC0・nCm+nC1・nCm+1+・・・+nCn-m・nCn
  =nC0・nCn-m+nC1・nCn-m-1+・・・+nCn-m・nC0 は、
 (nC0+nC1x+・・・+nCn-1xn-1+nCnxn)(nCn+nCn-1x+・・・+nC1xn-1+nC0xn)
すなわち、(1+x)n(1+x)n=(1+x)2n を展開したときの xn-m の係数に等しい。
したがって、 2nCn-m である。  (証終)


 らいさんからの続報です。(平成23年11月7日付け)

 上記の性質:Σk=0〜n-m nCk・nCk+m = 2nCn-m から、さらに一般化を進めてみました。
ただ、一般化に重きを置いたため文字が増え、場合分けが必要になり、美しさが損なわれて
しまったようです…。

 0≦m≦l≦n のとき、 Σk=0〜n-l n+lCl-m+k・n-lCk = 2nCn-m ・・・(A)

 0≦l≦m≦n のとき、 Σk=0〜n-m n+lCk・n-lCm-l+k = 2nCn-m ・・・(B)

ここで、式(A)は、 Σk=l-m〜n-m n+lCk・n-lCm-l+k = 2nCn-m ・・・(C)

 式(B)は、 Σk=m-l〜n-l n+lCl-m+k・n-lCk = 2nCn-m ・・・(D)

とそれぞれ変形することができ、こうすると、(A)と(D)、(B)と(C)がそれぞれ似ていること
を確認できます。

 1番上の式は、式(B)について、「 l = 0 」とすると得られます。冒頭の
明治大学の問題は
式(C)について、「 n = 50  m = 0  l = 10 」とすることで解を得られます。美しさはあまりない
ですが、左辺に出てくる「l」の値が右辺に影響しないことが個人的に面白いと思いました。
うまくすると面白い問題が作れそうな気がします。

 ちなみに、先ほどの公式の組み合わせ論的な解釈は、

 n+l個の異なる赤球と、n-l個の異なる白球がある。この異なる 2n個のものから、異なる

n-m個のものをとる組合せの数 2nCn-m は、赤球の個数で場合分けして、赤球n-m-k個

と白球k個をとる組合せの数の積 n+lCn-m-k・n-lCk = n+lCl-m+k・n-lCk の和に等しい。


となります。


 FNさんからのコメントです。(平成23年11月7日付け)

(35) nC0・nCm+nC1・nCm+1+・・・+nCn-m・nCn=2nCn-m (0≦m≦n)

は、(14)の一般化でありますが、(16)の特殊化でもあります。(35)を少し書き直すと、

  nC0・nCn-m+nC1・nCn-m-1+・・・+nCn-m・nC0=2nCn-m (0≦m≦n)

これは、

(16) nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0=n+mCk

において、mをnに、kをn-mに変えたものです。

(14)は、男n人、女n人の計2n人からn人を選ぶ選び方を、2通りで考えて得られる。

(35)は、男n人、女n人の計2n人からn-m人を選ぶ選び方を、2通りで考えて得られる。

(16)は、男n人、女m人の計n+m人からk人を選ぶ選び方を、2通りで考えて得られる。

 (35)のn-mをkに変えても成り立ちますが、k>n のとき、nCk=0 とかの約束が必要にな
ります。

 らいさんが書かれた上記の式(A)(B)も、(16)の特殊化だと思います。

 4通りの場合分けが必要になったのは、2項係数が定義できることを気にしたからで、
k>n、k<0 のときは、nCk=0 としておけば必要なくなると思います。

 4通りの式で、多分(16)のn+mが偶数の場合に相当すると思います。きちんとチェックし
たわけではありませんから間違ってるかもしれません。


 らいさんからのコメントです。(平成23年11月7日付け)

 なるほど、そういわれてみればその通りです。(16)の式はもっと簡潔に書いてあったの
ですね!研究したのはだいぶ前で、どういう経緯でその式にたどり着いたのか覚えてない
のですが、後の式をすぐ求められるのですね...。いろいろとありがとうございました。


 当HPの読者のHN「らい」さんより、随分前に、友達が発見し証明できなかった等式を、
昔のメモから発掘されたということで、次の公式をご教示頂いた。
                                    (平成23年11月19日付け)

(36) Σk=0〜n nCk(n+1-k)n(-1)k = n!

 n=0〜3 まで試して、どうやら合っているようです。数学的帰納法で上手くいくかと思った
のですが、上手くいきません。あと一歩だと思ったのですが...。証明していただけると嬉
しいです。

 FNさんが証明されました。(平成23年11月19日付け)

(証明) 1、2、・・・、n から n 個とる順列を2通りで考える。普通に数えて、n!個

 0、1、2、・・・・、n から重複を許して n 個とる順列を考えると、その個数は、(n+1)n

 このうちで、1、2、・・・・、n から n 個とる順列でないものを引いていく。

 まず、1を含まないものの個数は、nn、2を含まないもの、・・・、n を含まないものも同じだ

 から、1、2、・・・・、n のうちのどれかを含まないものは、n・nn個

 (n+1)nからn・nnをひく。しかし、もちろん、これは重複して数えているので引き過ぎ。

 1も2も含まないものは、1を含まないものとして数え、2を含まないものとして数えている。

 1も2も含まないものは、(n-1)n個。1も3も等々も同じで、その選び方は、nC2通り。

 引きすぎた分を足して、(n+1)n-n・nn+nC2(n-1)n だが、今度は足し過ぎ。

 1も2も3も含まないもの等々を引いて、(n+1)n-n・nn+nC2(n-1)n+nC3(n-2)n

 これをどんどん繰り返していく。1、2、・・・、n から n 個とる順列はどれにも該当しないか

 ら足されることも引かれることもない。それ以外のものはちょうど1回引かれる。

  従って、成り立つ。  (証終)

 らいさんからのコメントです。(平成23年11月19日付け)

 なるほど!包除原理ですか。そんな考え方もできるのですね!参考になりました。
 ところで、上記の階乗の等式は、同様の考えかたを用いると、

 Σk=0〜n-1 nCk(n-k)n(-1)k = n!

のようにいろいろな形の式を作ることができるのですね。ただ、この式だと n=0 に対応して
いないというのが違う点ですね。まあ、そんなに気になる違いでもありませんが...。


 攻略法さんからのコメントです。(平成23年11月23日付け)

 n≧1 のとき、 Σk=0〜n {nCkkn(-1)n±k} = n!

          Σk=0〜n {nCn-k(n-k)n(-1)k} = n! と同値。

 nCk=nCn-k より、 Σk=0〜n {nCk(n-k)n(-1)k} = n! と同値。


 at さんからのコメントです。(平成23年11月24日付け)

 なるほど。この証明法は興味深いですね。同様に考えて、次の等式が成り立つことがわか
りますね。

 任意の正の整数 n、m に対して、 Σk=0〜n (-1)knCk(n+m-k)n = n!

 次の等式も成り立ちます。証明は同じ考え方でできます。

 任意の正の整数 n、m に対して、

  Σa=0〜nΣb=0〜n-a (-1)a+bnCa・n-aCb・2nCb b!(n+m-a-b)2n-b = (2n)!/2n


 らいさんからのコメントです。(平成23年11月26日付け)

 上記の公式

 任意の正の整数 n、m に対して、 Σk=0〜n (-1)knCk(n+m-k)n = n!

は、mが負数でも成り立ちます。すなわち、

 任意の正の整数 n、m に対して、 Σk=0〜n (-1)knCk(n±m-k)n = n!

 ところで、m は実数全体に対して成り立ちそうです。n=3、m=πでやってみましたが、見事
にπが消えてくれました。また、

 任意の正の整数 n、m に対して、

  Σa=0〜nΣb=0〜n-a (-1)a+bnCa・n-aCb・2nCb b!(n+m-a-b)2n-b = (2n)!/2n

についても、おそらく、同じことが言えるのではないでしょうか?

 ところで、 Σk=0〜n (-1)knCk(n-k)n = n! の両辺をn!で割ると、

 Σk=0〜n (-1)k(n-k)n/{k!(n-k)!} = 1

 さらに特殊化すると、 Σj+k=n (-k)j・kk/{k!j!} = 1 という式が得られる。


 at さんからのコメントです。(平成23年11月26日付け)

 そうですね。確かに、mは実数全体に対して成り立ちそうですね。整理して書くと、次のこ
とが言えるようです。

 任意の実数 x に対して、Σk=0〜n (-1)knCk(x-k)n = n!

 あとは、この等式が本当に正しいことを証明できればいいですね。


 FNさんからのコメントです。(平成23年11月26日付け)

 今までの議論が正しいとすると、無限個のx(x=n+1、n+2、・・・)に対して成り立つ。

 左辺は、xについてn次以下の式だから、恒等式でない限り、n個より多い解をもつことは
ない。従って、恒等式である。すなわち、すべてのxについて成り立つ。でも、直接上の式を
証明しないといけませんね。


 at さんからのコメントです。(平成23年11月26日付け)

 なるほど!こういう証明法がありましたか。恒等的に0でないようなn次以下の多項式が、
n個より多くの根をもつことはあり得ないという性質を利用したのですね。これ以外の証明
もあるのでしょうか?難しそうです。


 らいさんからのコメントです。(平成23年11月26日付け)

 確かにそれで証明はできているようですね。直接証明するために、まず補題を用意します。

補 題 自然数 n、非負整数 m (m<n) に対して、Σk=0〜n (-1)knCkkm = 0

(証明) (1+x)n = Σk=0〜n nCkxk の両辺を微分し、さらに、x をかけると、

 nx(1+x)n-1 = Σk=0〜n knCkxk

これを、m回繰り返し、x=-1 を代入すると得られる。  (証終)

これを用いて、 Σk=0〜n (-1)knCk(x-k)n = n! を証明する。

(証明) (x-k)n を2項定理で展開し、x について降べきの順に並べる。

 m=0、1、2、・・・、n-1 について、(x-k)n の展開式における xn-m の係数は、nCm(-k)m

なので、(-1)mnCmxn-m の係数は、Σk=0〜n (-1)knCkkm すなわち、0 になる。

 定数項は、Σk=0〜n (-1)knCk(-k)n で、これは、

 Σk=0〜n (-1)knCk(n+m-k)n = n! (mは整数)

について、m=-n としたものである。 よって、(定数項)=n! なので、

 Σk=0〜n (-1)knCk(x-k)n = n!

が示された。  (証終)

点検お願いします。(→ 一部修正させていただきました。証明は正しいものです。)


 FNさんからのコメントです。(平成23年11月26日付け)

 Σk=0〜n (-1)knCk(n+m-k)n = n! (mは整数) を使うのであれば、私の解答でもいい
ことになってしまわないでしょうか。実質的に使ってるのは、Σk=0〜n (-1)knCk(-k)n=n!
だけだから、同じということにはならないでしょうが...。


 らいさんからのコメントです。(平成23年11月26日付け)

 あ、そうでしたね!うっかりしました。では、定数項 Σk=0〜n (-1)knCk(-k)n を同値な式
Σk=0〜n (-1)knCk(n-k)n (∵ (-1)knCk(-k)n = nCn-kkn・(-1)n+k で、n-kをkに置き
換える)に変形すれば、前述の包除原理を用いた証明に帰着できるでしょう。

 先ほど用いた補題について一般化を考えてみました。一般化の前に、先ほどの証明に
出てきた定数項Σk=0〜n (-1)knCk(-k)n=n!は、補題の延長として証明できることがわ
かりました。

 2項定理 (1+x)n = Σk=0〜n nCkxk の両辺を微分し、さらに、x をかけると、

 nx(1+x)n-1 = Σk=0〜n knCkxk

これを、m回繰り返す。補題の証明では、「m<n」としましたが、ここで、「m=n」のとき、

 n!xn +・・・= Σk=0〜n knnCkxk すなわち、n!+・・・ = Σk=0〜n knnCkxk-n

ここで、x=-1 とすれば、Σk=0〜n (-1)k-nnCkkn = n!となるので、包除原理を用いずに、

 Σk=0〜n (-1)knCk(-k)n = Σk=0〜n (-1)k+nnCkkn = Σk=0〜n (-1)k-nnCkkn = n!

と導けました。さて、一般化ですが、

補題2  自然数 n、非負整数 m (m<n) に対して、

 Σk=0〜n {(-1)knCkΠj=1〜m(aj+k)}= 0

ただし、a1、a2、・・・、am は、任意の実数

 補題は、a1=a2=・・・=am=0 の場合です。

 余談ですが、この話題の発端となった等式 Σk=0〜n (-1)knCk(n+1-k)n = n!は、中3の
とき友人が見つけたのですが、そのとき彼は、ただなんとなく平方数、立方数およびn乗数の
差分を繰りかえしとっていただけらしいのです。それで、最後には階乗にたどり着くということ
を発見し、この式を見出したようなのですが、まさかn乗数の差分と、このような組み合わせ
に関する多くの等式がつながっているとは…。やはり、数学は奥が深く、どこでつながってい
るかわからないものですね。

 FNさんからのコメントです。(平成23年11月26日付け)

 この一般化はあまり意味がないですね。Πj=1〜m(aj+k)は、kのm次式で、kl (l≦m)に
ついて、Σk=0〜n (-1)knCkkl = 0 が証明できてるので、当然成り立ちます。

それより、補題と、m=n のときの式の証明がいいですね!

 Σk=0〜n (-1)knCkkm = 0

 Σk=0〜n (-1)knCk(-k)n = Σk=0〜n (-1)k-nnCkkn= n!

 2項係数の性質の(28)のようですが、そこの証明は包除原理を使っているようです。2項
定理に微分をm回使って証明できるのが面白いです。


 らいさんからのコメントです。(平成23年11月26日付け)

 なるほど、確かに…。ということは、Σk=0〜n (-1)knCkkl = 0 さえあれば、2項係数の係
数がきれいな法則にのっとるような和で、右辺が0になるようなものがいくらでもつくれてしま
うのですね。

 (n-1)!nC0 - (n!/1!)nC1 + ((n+1)!/2!)nC2 -・・・+ (-1)n((2n-1)!/n!)nCn = 0

とか…。逆にこういった式の証明も簡単にできてしまうのですね。

 公式自体は既出だったのですね。でも、新しい証明法を与えられて光栄です。僕は何か
発見すると、すぐに先走ってしまうようで、ここで出した式が何かの特殊化であることが多
いようです^^;


 at さんからのコメントです。(平成23年11月26日付け)

 らいさんの主張:補題2は正しいです。さらに一般に、次の等式が成り立つことが知られて
います。

 nを0以上の任意の整数、b0、b1、b2、・・・、bn を任意の実数とするとき、

  (-1)nΣk=0〜n (-1)knCk(-1)n-k(b0+b1k+b2k2+・・・+bnkn) = n!bn

#上式は、GAI さんのご指摘で修正されています。(赤字部分)(令和5年5月10日付け)

 らいさんの補題2は、この式において、bn=0 としたものです。


 らいさんからのコメントです。(平成23年11月26日付け)

 なるほど。Πを展開した時、mは、n-1までの値をとりえるので、bn=0 のときと一致するわ
けですね!FNさんの言うように、b0+b1k+b2k2+・・・+bn-1kn-1 の部分はΣを分けた時にそ
れぞれ0になるので、b0、b1、b2、・・・、bn-1 の値が影響しないんですね。先ほど示した

 Σk=0〜n (-1)knCkkm = 0 (m<n)

 Σk=0〜n (-1)k-nnCkkn= n!

をそれぞれ定数倍してまとめると、at さんの式になるということですね。とても納得いきました。


 らいさんからのコメントです。(平成23年11月29日付け)

 先日、 Σk=0〜n (-1)knCkkm = 0 (m<n) 、Σk=0〜n (-1)k-nnCkkn= n! の証明に
使った、「2項展開式の両辺を微分し、x をかける。これをm回繰り返す。」という作業があり
ました。これを、m>nに対して拡張できないかと考えました。

 f0(x) = (1+x)n 、fm+1(x) = xfm’(x) とし、fn(x) を求めます。

fm(x) の n(n-1)…(n-k+1)xn-k(1+x)k の係数を a[m,k] とすると、

  a[m,1] = 1 、a[m,k] = k・a[m-1,k] + a[m-1,k-1]

が成り立つので、ここから、a[m,k] を求められれば一番いいのですが、m、kで直接は表せ
ないようです...。しかし、漸化式から、a[n+k,n] を求められれば、fn+k(x) と2項定理の
関係から、

   Σj=0〜n (-1)n-jnCjjn+k = a[n+k,n]・n!

となります。n+k=m として、 Σj=0〜n (-1)n-jnCjjm = a[m,n]・n!

としてしまうほうがわかりやすいでしょうか。ともかく

 a[n,n] = 1 、a[n+1,n] = n(n+1)/2 、a[n+2,n] = n(n+1)(n+2)(3n+1)/4!

 a[n+3,n] = {n(n+1)}2(n+2)(n+4)/(4!・2)

ということまではわかりましたが、なかなか一般項にたどり着けません...。

a[n+k,n] は求められるでしょうか?


 攻略法さんからのコメントです。(平成23年11月29日付け)

 「私の備忘録」−「ベル数」 で、第2種スターリング数の表があります。

 a[n,m]・m!=Σk=0〜m (-1)kmCk(m-k)n

として、表を眺める。

n\m 1 2 3 4 5 6 7 8 9   B(n)
1 1 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・   1
2 1 1 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・   2
3 1 3 1 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・   5
4 1 7 6 1 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・   15
5 1 15 25 10 1 ・・・・・・・・・・・・・・・・・・・・・・   52
6 1 31 90 65 15 1 ・・・・・・・・・・・・・・・・   203
7 1 63 301 350 140 21 1 ・・・・・・・・・・   877
8 1 127 966 1701 1050 266 28 1 ・・・・   4140
9 1 255 3025 7770 6951 2646 462 36 1   21147

右端の斜め 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,… から、a[n,n] =1

右端から2番目の斜め 1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,… から、

a[n+1,n]=(1/2)n(n+1)

右端から3番目の斜め 1,7,25,65,140,266,462,750,1155,1705,2431,3367,4550,6020,7820,…

 a[n+2,n]=(1/24)n(n+1)(n+2)(3n+1)

右端から4番目の斜め
 1,15,90,350,1050,2646,5880,11880,22275,39325,66066,106470,165620,249900,367200,…

 a[n+3,n]=(1/48)n2(n+1)2(n+2)(n+3)

右端から5番目の斜め
 1,31,301,1701,6951,22827,63987,159027,359502,752752,1479478,2757118,4910178,8408778,13916778,…

 a[n+4,n]=(1/5760)n(n+1)(n+2)(n+3)(n+4)(15n3+30n2+5n-2)

右端から6番目の斜め
 1,63,966,7770,42525,179487,627396,1899612,5135130,12662650,28936908,62022324,125854638,243577530,452329200,…

 a[n+5,n]=(1/11520)n2(n+1)2(n+2)(n+3)(n+4)(n+5)(3n2+7n-2)

n≧2 のとき、a[n,2]=2n-1-1 2列目


 らいさんからのコメントです。(平成23年11月30日付け)

 そちらに書いてありましたか。教えていただいてありがとうございます。6番目の一般項まで
出し、以前にそのペ−ジを見たことがあるにもかかわらず、つながりを見出せませんでした。

 見た限り、やはり一般の場合の式は少なくとも簡潔には出ないようですね。2項係数の和
の等式として、使ってみてきれいなのも大目に見て3番目くらいまでですかね…


 HN「りらひい」さんから、興味ある関係式をご教示いただきました。
                                      (平成24年6月23日付け)

 私の脳に強く焼き付いている式を一つ・・・。

  Σi=0〜mΣj=0〜n (-1)i+j・i+jCi・mCi・nCj=δ[m,n]

   (ただし、δ[m,n] はクロネッカーのデルタ)


例 いくつか実験してみた。 m=1、n=1のとき、

 Σi=0〜1Σj=0〜1 (-1)i+j・i+jCi・1Ci・1Cj

 =0C0・1C0・1C0+(-1)・1C0・1C0・1C1+(-1)・1C1・1C1・1C0+2C1・1C1・1C1

 =1+(-1)+(-1)+2=1

 m=1、n=2のとき、

 Σi=0〜1Σj=0〜2 (-1)i+j・i+jCi・mCi・nCj

 =0C0・1C0・2C0+(-1)・1C0・1C0・2C1+2C0・1C0・2C2
                    +(-1)・1C1・1C1・2C0+2C1・1C1・2C1+(-1)・3C1・1C1・2C2

 =1+(-2)+1+(-1)+4+(-3) = 0


(コメント) 一瞬、本当かな?と頭を過ぎりましたが、成り立ちそうですね!


 at さんが考察されました。(平成24年7月16日付け)

 上記の等式の証明を考えてみました。証明には、Chu-Vandermonde identity と、

 nCk=(-1)k・k-n-1Ck

という等式を使いました。

(証明) n≦mの場合:

 左辺=Σi=0〜mΣj=0〜n (-1)i+j・i+jCi・mCi・nCj

=Σi=0〜mΣj=0〜n (-1)i+j・(-1)i・-j-1Ci・mCm-i・nCj

=Σi=0〜mΣj=0〜n (-1)j・-j-1Ci・mCm-i・nCj

=Σj=0〜n (-1)j・nCjΣi=0〜m(-j-1Ci・mCm-i)

=Σj=0〜n (-1)j・nCj・m-j-1Cm

=Σj=0〜n (-1)j・nCj・(-1)m・jCm

=Σj=0〜n (-1)j+m・nCj・jCm

=δ[m,n].

n>mの場合: 左辺を変形していくと、左辺=Σi=0〜m (-1)i+n・mCi・iCn=0


 りらひいさんからのコメントです。(平成24年7月19日付け)

 証明してくださってありがとうございます。わたしには証明が思いつかなかったため、式だ
けが頭に残っていたのでした。これで少しすっきりしました。参考までに、私がこの関係式を
得た方法を書いておきます。

 「ラゲール多項式の直交関係を表す式に展開式を代入して展開し、項ごとに積分を実行
 したもの」


 当HPがいつもお世話になっているHN「K.S.」さんより、新たな2項係数の性質をご教示
いただいた。(平成25年7月16日付け)

 組合せ公式は、奥が深いようです。

(37) 2n-1C1+2n-3C1+・・・+1C1=2・nC2+1・nC1+0・nC0  (n≧2)

(38) 2n-2C2+2n-4C2+・・・+2C2=4・nC3+1・nC2+0・nC1  (n≧2)

(39) 2n-1C3+2n-3C3+・・・+3C3=8・nC4+8・nC3+1・nC2  (n≧3)

(40) 2n-2C4+2n-4C4+・・・+4C4=16nC5+12・nC4+1・nC3  (n≧3)


 K.S.さんからいただいた性質の証明を考えてみた。

(37)の(証明)

 (左辺)=(2n−1)+(2n−3)+・・・+1=n(2n−1+1)/2=n2

 (右辺)=n(n−1)+n=n2  なので、 (左辺)=(右辺)  (証終)

(38)の(証明)

(左辺)=(n−1)(2n−3)+(n−2)(2n−5)+・・・+1

=Σk=1〜n-1 k(2k−1)

=n(n−1)(2n−1)/3−n(n−1)/2

=n(n−1)(4n−2−3)/6=n(n−1)(4n−5)/6

(右辺)=2n(n−1)(n−2)/3+n(n−1)/2

 =n(n−1)(4n−8+3)/6=n(n−1)(4n−5)/6

なので、 (左辺)=(右辺)  (証終)

......と一応計算すれば、残りの(39)、(40)も証明出来るのだろう。
 しかし、等式をもっと別な視点で明らかにすることは出来るのだろうか?


 空舟さんが、(37)式〜(40)式について考察されました。(平成25年7月26日付け)

 偶奇両方を補って書いてみます。

(**) Σk=1〜n 2k-1C0=Σ k=1〜n 2k-2C0=n=nC1

 (37) Σ k=1〜n 2k-1C1=2・nC2+1・nC1+0・nC0 (n≧2)に対して、

(37)’  Σk=1〜n 2k-1C1=n2=2・nC2+nC1
(37)”  Σ k=1〜n 2k-2C1=n2−n=2・nC2

 (38) Σ k=1〜n 2k-2C2=4・nC3+1・nC2+0・nC1 (n≧2)に対して、

(38)’  Σk=1〜n 2k-1C2=4・nC3+3・nC2
(38)”  Σk=1〜n 2k-2C2=4・nC3+1・nC2

 (39) Σ k=1〜n 2k-1C3=8・nC4+8・nC3+1・nC2 (n≧2)に対して、

(39)’  Σk=1〜n 2k-1C3=8・nC4+8・nC3+1・nC2
(39)”  Σk=1〜n 2k-2C3=8・nC4+4・nC3

 (40) Σ k=1〜n 2k-2C4=16nC5+12・nC4+1・nC3 (n≧2)に対して、

(40)’  Σk=1〜n 2k-1C4=16nC5+20・nC4+5・nC3
(40)”  Σk=1〜n 2k-2C4=16nC5+12・nC4+1・nC3

(注意)  0≦a<b のときは、2項係数 aCb=0 と扱っています。そういうわけで、例えば、
    上記の(40)”式では、k=3からnまでと同じです。

 ここで、例えば、次のような3式間の関係が成り立っています。

(40)’式= (38)’式に(39)’式の2倍を足して、aCb のbの値に+1したもの

(40)”式= (38)”式に(39)”式の2倍を足して、aCb のbの値に+1したもの

(**,37,38)の間、(37,38,39)の間についても同様に成り立ちます。

実際、次のようにして、この関係を確認することができます。

Σk=1〜n 2k-1Cm= Fm(n) とおく。

2k+1Cm−2k-1Cm= 2・2k-1Cm-1+ 2k-1Cm-2 ・・・ (※)

kについて、1からn−1まで両辺の和をとることで、

2n-1Cm= 2・Fm-1(n-1) + Fm-2(n-1)

nをkとおいて、1からnまで両辺の和をとることで、

 Fm(n) = 2Σk=1〜n Fm-1(k-1) + Σk=1〜n Fm-2(k-1)

であることから上記の性質を得る。

※ 2k+1個からm個選ぶ方法は;
・(2k−1個からm個選ぶ方法)×(2個から0個選ぶ方法)
・(2k−1個からm−1個選ぶ方法)×(2個から1個選ぶ方法)
・(2k−1個からm−2個選ぶ方法)×(2個から2個選ぶ方法)
の合計に一致することから。

※ (40)’  Σ k=1〜n 2k-1C4=16nC5+20・nC4+5・nC3 という式の係数は最近どこかで
 見たことがあるような気がしますね!

 5倍角の公式 と見比べて、F(x)=16x^5-20x^3+5x としてグラフを・・・

何か関連付ける説明はあるのでしょうか・・


 らすかるさんからのコメントです。(平成25年7月26日付け)

(37)’(38)’(39)’(40)’の右辺の係数は、

 cos(2θ)=2(cos2θ)-1
 cos(3θ)=4(cos3θ)-3(cosθ)
 cos(4θ)=8(cos4θ)-8(cos2θ)+1
 cos(5θ)=16(cos5θ)-20(cos3θ)+5(cosθ)

の右辺の係数を正にしたものと一致しますが、(37)”(38)”(39)”(40)”'の右辺の係数は

 sin(2θ)/(sinθ)=2cosθ
 sin(3θ)/(sinθ)=4(cos2θ)-1
 sin(4θ)/(sinθ)=8(cos3θ)-4(cosθ)
 sin(5θ)/(sinθ)=16(cos4θ)-12(cos2θ)+1

の右辺の係数を正にしたものと一致しますね。


(コメント) 何となく奥が深いような...雰囲気!


 K.S.さんからのコメントです。(平成25年7月31日付け)

(40) 2n-2C4+2n-4C4+・・・+4C4=16nC5+12・nC4+1・nC3  (n≧3)

について、

入試問題  2n−5個の白玉と5個の赤玉を左から右へ一列に並べる方法を考える。
       このうちで、最も右側にある赤玉が奇数番目にある並べ方は何通りあるか。


の解答になります。

 左辺の式の考え方は、2n個を2組ずつ並べて考えるとき、先ず、一番右側の組に赤玉

をおくとき、残り4個の入れ場所は、2n-2C4通りある。次に、右から最も右側にある赤玉が

右から二組めにあるとき、残り4個の入れ場所は、2n-4C4通りある。以下同様にして、4C4

までの全て和を求める。

 右辺の式の考え方は、2n個を、2組づつ並べて考えるとき、5個の赤玉が5組に1個づつ

入る場合、nC5通りあり、左の4個については右左どちらでもよいので、24=16通りありま

す。次に5個の赤玉が4組に入る場合、必然的に赤赤と入る組が一組あり、3組のうち一つ

なので、3通り、最も右側は赤白となる。2組は右左どちらでもよいので、4通り、よって、

3×4=12通りあります。最後に5個の赤玉が3組に入る場合、nC3通りあります。全ての

和が右辺になります。同様の考え方で、

 3n個の玉の中、赤玉5個と残り白玉を左から右へ一列に並べる方法を考える。このうち
で、最も右側にある赤玉が3で割りと1余る番目ある並べ方は何通りあるか。


については、

 3n-3C4+3n-6C4+・・・+6C4=81・nC5+81・nC4+15・nC3

が得られました。


(コメント) なるほど〜、考え方がよく分かりました。K.S.さんに感謝します。

(37) 2n-1C1+2n-3C1+・・・+1C1=2・nC2+1・nC1+0・nC0  (n≧2)

については、次のように考えればいいわけですね。

 2n−2個の白玉と2個の赤玉を左から右へ一列に並べる方法を考える。このうちで、最も
右側にある赤玉が偶数番目にある並べ方は何通りあるか。


 左辺の式の考え方は、2n個を2組ずつ並べて考えるとき、先ず、一番右側の組に赤玉

をおくとき、残り1個の入れ場所は、2n-1C1通りある。次に、右から最も右側にある赤玉が

右から二組めにあるとき、残り1個の入れ場所は、2n-3C1通りある。以下同様にして、1C1

までの全て和を求める。

 右辺の式の考え方は、2n個を、2組づつ並べて考えるとき、2個の赤玉が2組に1個づつ

入る場合、nC2通りあり、左の1個については右左どちらでもよいので、2通りあります。次

に2個の赤玉が1組に入る場合、1通りあります。3項目の「0・nC0」は他とのバランスを考

えて形式的に入れておきます。全ての和が右辺になります。

 同様に、

(38) 2n-2C2+2n-4C2+・・・+2C2=4・nC3+1・nC2+0・nC1  (n≧2)

については、

 2n−3個の白玉と3個の赤玉を左から右へ一列に並べる方法を考える。このうちで、最も
右側にある赤玉が奇数番目にある並べ方は何通りあるか。


(39) 2n-1C3+2n-3C3+・・・+3C3=8・nC4+8・nC3+1・nC2  (n≧3)

については、

 2n−4個の白玉と4個の赤玉を左から右へ一列に並べる方法を考える。このうちで、最も
右側にある赤玉が偶数番目にある並べ方は何通りあるか。


という問題の解答としてとらえればいいわけですね。


 横浜市立大学医学部(2013)の入試問題に次の等式の値を求める問題が出題された。

(41) (1/2)2nC1+(1/4)2nC3+(1/6)2nC5+・・・+(1/(2n))2nC2n-1

  =(22n−1)/(2n+1)


  (証明) 展開公式 2nC0+2nC1t+2nC2t2+・・・+2nC2nt2n=(1+t)2n の両辺を、

 t=0 から t=x まで定積分すると、

 2nC0x+(1/2)2nC1x2+(1/3)2nC2x3+・・・+(1/(2n+1))2nC2nx2n+1={(1+x)2n+1−1}/(2n+1)

 x=1 を代入して、

 2nC0+(1/2)2nC1+(1/3)2nC2+・・・+(1/(2n+1))2nC2n={22n+1−1}/(2n+1)

 x=−1 を代入して、

 −2nC0+(1/2)2nC1−(1/3)2nC2+・・・−(1/(2n+1))2nC2n=−1/(2n+1)

 この2式を辺々加えて、両辺を2で割ると、

   (1/2)2nC1+(1/4)2nC3+・・・+(1/(2n))2nC2n-1={22n−1}/(2n+1)  (証終)


(追記) 二項係数の新たな性質ということで、K.S.さんよりメールを頂いた。
                                      (平成25年10月9日付け)

 等差型 1,2,3,4 や2,4,6 のタイプはあるのですが、等比型 1,2,4,8 のタイ
プと言えると思います。

(42) nC0+2・nC2+4・nC4+8・nC6+・・・={(1+)n+(1−)n}/2

  (証明) (1+x)n=nC0+nC1x+nC2x2+・・・+nCnxn において、

      x=± とおけばよい。  (証終)


 りらひいさんから次の等式の投稿がありました。(平成27年2月8日付け)

(43) k=0、1、2、…、n−1 のとき、

  Σi=0〜k (2nCi・2(n-i)・2n-k-iCk-i/(2n-k-i))=22k・nCk


 左辺と右辺に至った道のりを逆にたどれば示すことができるのですが、迂遠な感じです。
もっと直接説明できないかなと考えていたけれど、いいアイディアが浮かびませんでした。

(コメント) k=2として、等式の意味を考えてみた。

2nC0・2n・ 2n-2C2/(2n-2)+2nC1・2(n-1)・ 2n-3C1/(2n-3)+2nC2・2(n-2)・2n-4C0/(2n-4)

=24・nC2

(左辺)=2n・(2n-3)/2+2n・2(n-1)・1+n(2n-1)・2(n-2)/(2n-4)
    =2n2-3n+4n2-4n+2n2-n=8n2-8n ・・・ 修正済み りらひいさんに感謝!

(右辺)=24・nC2=16・n(n-1)/2=8n2-8n


(追記) 「これって有名ですか?」と題して、HN「鱒」さんからの投稿です。
                                      (平成27年10月3日付け)

(44) ��k=1〜n (nCk−2k+1)/k=0

 今日見つけたんですけども……、これって有名ですか?


 DD++さんからのコメントです。(平成27年10月4日付け)

 有名という意味にもよりますね。これピンポイントで意識的に知っている人はまずいないで
しょうけれど、いつでもこの等式を書ける人はかなりいるでしょう。導出も3行あれば十分です
し...。


 鱒さんからのコメントです。(平成27年10月4日付け)

 なるほど。見つけるまでは知らなかったので、そこそこやっている方の間には知れ渡って
いるのかなあと、ちょっと疑問に思い投稿した次第です。でもなんとなく仰る通り書ける方は
多そうですね。二項定理の式を少しいじって、その後積分して見つけました。一応、数学的
帰納法でも証明しておきました。


 DD++さんからのコメントです。(平成27年10月4日付け)

 まあ登場機会がそんなにある式には見えませんしね。一部特定の問題には絶大な威力を
発揮するんでしょうけれど。


(コメント) DD++さんの「導出も3行あれば十分」という言葉に惹かれて考えてみました。

 ニュートンの2項定理より、 

 (1+x)n=nC0+nC1x+nC2x2+nC3x3+・・・+nCrxr+・・・+nCnxn

 よって、 nC1+nC2x+nC3x2+・・・+nCrxr-1+・・・+nCnxn-1

 ={(1+x)n−1}/x={(1+x)n−1}/{(1+x)−1}

 =1+(1+x)+(1+x)2+・・・+(1+x)n-1

このとき、両辺を0から1まで定積分すると、

 nC1+nC2/2+nC3/3+・・・+nCr/r+・・・+nCn/n

=(2−1)+(22−1)/2+(23−1)/3+・・・+(2n−1)/n

となるので、 ��k=1〜n (nCk−2k+1)/k=0 が成り立つ。

#式を横長に書けば、ほぼ3行くらいかな?


 DD++さんからのコメントです。(平成27年10月5日付け)

 以下で、3行のつもりでした。やってることは寸分違わず同じですが、等比数列側から出発
した方がスムーズです。

 Σ[k=1..n] (1+x)k-1 = {(1+x)n-1}/x = Σ[k=1..n] nCk xk-1

 よって、Σ[k=1..n] { nCk xk-1 - (1+x)k-1 } = 0

 両辺を 0 から 1 まで積分して、 Σ[k=1..n] (nCk-2k+1)/k = 0


(コメント) なるほど、等比数列側からの方がスッキリしていますね。私の方は、ニュートンの
      2項定理から「1/k」を作るための下準備をして、そのときに出来た分母の「x」を
      「(1+x)−1」ととらえることに気がつき、上記の解答に至りました。


 2項係数の性質として、次のp進展開との関係はかなり有名で有用らしい。

(45) 素数 p に対して、a、b(a>b)のp進展開を

   a=a0+a1p+a2p2+・・・+akpk 、b=b0+b1p+b2p2+・・・+bkpk

  としたとき、 aCb≡a0Cb0・a1Cb1・・・akCbk (mod p) が成り立つ。



(例) a=19、b=7、p=5 とする。このとき、a、b を5進展開して、

  a=4+3・5 、b=2+1・5

ここで、 19C7=3・4・13・17・19=50388 、4C2=6 、3C1=3 なので、

 19C7−4C2・3C1=50370≡0 (mod 5) より、 19C7≡4C2・3C1 (mod 5)

が成り立つ。


(追記) 性質(45)を示すには、いくつか準備が必要だ。(平成29年5月7日付け)

 2項係数 aCb=a!/{b!(a−b)!} について、a<b の場合は、aCb=0 と定める。

補題1 p を素数とする。このとき、1≦k≦p−1 を満たす自然数 k に対して、pCkは p
    で割り切れる。


(証明) {k!(p−k)!}pCk=p! より、左辺は p の倍数。1≦k≦p−1 で、

  k!(p−k)!は、素数 p と互いに素だから、pCk はpで割り切れる。  (証終)


 また、整数係数の多項式 f(x) と g(x) を、

 f(x)=a(n)xn+a(n-1)xn-1+・・・+a(1)x+a(0)
 g(x)=b(n)xn+b(n-1)xn-1+・・・+b(1)x+b(0)

とおく。(適宜、a(n)=0 や b(n)=0 などとして、f(x) と g(x) の次数を揃える)

このとき、多項式が合同 f(x)≡g(x) (mod p) であることを、次が成り立つときと定義する。

  a(0)≡b(0) 、a(1)≡b(1) 、・・・、a(n)≡b(n) (mod p)


補題2 自然数 n と素数 p に対して、 (x+1)pn≡xpn+1 (mod p) が成り立つ。

(証明) n=1のとき、補題1より、1≦k≦p−1 に対して、pCk≡0  (mod p) なので、

 (x+1)p=xp+pC1xp-1+pC2xp-2+・・・+pCp-1x+1≡xp+1 (mod p)

 よって、n=1のとき成り立つ。

 n=k(k≧1)のとき、成り立つと仮定する。すなわち、 (x+1)pk≡xpk+1 (mod p)

 n=k+1のとき、帰納法の仮定より、 (x+1)pk+1≡(xpk+1)p≡xpk+1+1 (mod p)

 よって、n=k+1の場合も、命題は成り立つ。

 したがって、任意の自然数nに対して、命題は成り立つ。  (証終)


補題3 自然数 n と素数 p に対して、a、b を、a≧b>0 をみたす自然数とする。このとき、

   pn・aCpn・b≡aCb (mod p)

(証明) 補題2より、 (x+1)pn≡xpn+1 (mod p) が成り立つので、

  (x+1)pn・a≡((x+1)pn)a≡(xpn+1)a (mod p)

 上式の両辺を展開して、pn・b次の項を比較すると、pn・aCpn・b≡aCb (mod p) が成り
立つことがわかる。  (証終)

 ここで、a<b の場合も、pn・aCpn・b=aCb=0 となるので、a<b の場合も補題3が成り
立つとしてよい。

 すなわち、自然数 n と素数 p に対して、 pn・aCpn・b≡aCb (mod p) が成り立つ。
                                                   (証終)

 以上で、性質(45)を示す準備が出来た。性質(45)を書き直して、次の定理を示す。


定理 素数 p に対して、自然数 a、b (a≧b)を p 進法で表すことを考える。すなわち、

 ph≦a<ph+1 を満たす整数 h をとると、

  a=a(h)・ph+a(h−1)・ph-1+…+a(0) 、b=b(h)・ph+b(h−1)・ph-1+…+b(0)

 と書ける。

このとき、 aCb≡a(h)Cb(h)・a(h-1)Cb(h-1)・・・・・a(0)Cb(0) (mod p) が成り立つ。

(証明) (x+1)a=(x+1)a(h)・ph・(x+1)a(h−1)・ph-1・・・・・(x+1)a(0) において、

 (x+1)a(h)・ph の b(h)・ph 次の係数は、a(h)・phCb(h)・ph で、補題3より、

  ph・a(h)Cph・b(h)≡a(h)Cb(h) (mod p)

 (x+1)a(h-1)・ph-1 の b(h-1)・ph-1 次の係数は、a(h-1)・ph-1Cb(h-1)・ph-1 で、補題3より、

  ph-1・a(h-1)Cph-1・b(h-1)≡a(h-1)Cb(h-1) (mod p)

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

 (x+1)a(1)・p の b(1)・p 次の係数は、a(1)・pCb(1)・p で、補題3より、

  p・a(1)Cp・b(1)≡a(1)Cb(1) (mod p)

よって、(x+1)a=(x+1)a(h)・ph・(x+1)a(h−1)・ph-1・・・・・(x+1)a(0) のb次の項の係数は、

 a(h)Cb(h)・a(h-1)Cb(h-1)・・・・・a(1)Cb(1)・a(0)Cb(0) (mod p)

に等しい。

 以上から、 aCb≡a(h)Cb(h)・a(h-1)Cb(h-1)・・・・・a(0)Cb(0) (mod p)  (証終)


例 40C10 を7で割った余りを求めよ。

 性質(45)によれば、 40=5・7+5 、10=1・7+3 なので、

  40C10≡5C1・5C3=50≡1 (mod 7)  であることが分かる。

 実際に、40C10=847660528 において、103≡−1 (mod 7) より、

 847660528≡847−660+528=715≡1 (mod 7)

 よって、40C10 を7で割ると余りは確かに 1 である。


(コメント) 比較的大きい a、b の値に対して、aCb を手計算で求めることは大変ですが、
      剰余の値を計算するだけだったら結構、手計算でもいけちゃいますね!


(追記) なつさんから「コンビネーションの和」と題してご投稿いただきました。
                                     (平成28年12月29日付け)

 この前、とある問題を解いていて偶然コンビネーションに関する恒等式を見つけました。

  Σ k=t〜n kCt = n+1Ct+1

 どうもこれが成り立ちそうなのです。どのように証明すればよいのでしょうか……。あと、こ
のような2項係数の和に関する恒等式は他に存在するのでしょうか。


 HN「ますた〜」さんからのコメントです。(平成28年12月29日付け)

 このページの(11)の k=n の場合で、

  nCn+n+1Cn+n+2Cn+・・・+n+mCn=n+m+1Cn+1

が似てるような...。


 DD++さんからのコメントです。(平成28年12月29日付け)

 私の知っている証明を4つ挙げておきます。お好きなものをどうぞ。

[1] 順列の理論から

 t+1 個の赤玉と n-t 個の白玉(合計 n+1 個)を横一列に並べます。その並べ方は、赤玉

の位置を考えて、n+1Ct+1 通り。それを最も右の赤玉がどこにあるかで分類すると、

 最も右の赤が t+1 番目のものが、tCt 通り

 最も右の赤が t+2 番目のものが、t+1Ct 通り

 最も右の赤が t+3 番目のものが、t+2Ct 通り

  ……

 最も右の赤が n+1 番目のものが、nCt 通り

となることから等式が成立します。

[2] 階差数列の理論から

 a+1Cb+1=aCb + aCb+1 より、a+1Cb+1−aCb+1=aCb

つまり、第 k 項が kCt+1 で表される数列の階差数列は、kCt です。したがって、左辺の和を

第 t 項である tCt+1(=0) に加えれば、第 n+1 項である n+1Ct+1 になります。

[3] パスカルの三角形から

 kCt を t≦k≦n としてパスカルの三角形で探すと、斜め一列に並んでいます。この合計が

左辺ということになります。ここから tCt を引いて、t+1Ct+1 を足します。(1を引いて1を足した
ので値としては変わっていません)

 ところで、パスカルの三角形は横に並んだ二つの数の和はその二つの間の下にある数に

なりますので、足すべき数の並び方から、合計が右辺の値になることがわかります。
(実際に手を動かしてみるとわかりやすいと思います)

[4] 級数関数の係数から

 恒等式 x + x(1+x) + x(1+x)2 + …… + x(1+x)n = (1+x)n+1 - 1 の xt+1 の係数を比較して
おしまい。


 なつさんからのコメントです。(平成28年12月30日付け)

 ますた〜さん、ありがとうございますm(_ _)m。まさに(11)の式でしたね^^;。
4通りも……!!DD++さん、ありがとうございますm(_ _)m。組み合わせ論でもいけるんです
ね...。


(46) 自然数 n に対して、 nC2+n+1C2=n2 が成り立つ。

 証明は易しい。これは正にパスカルの三角形の中に潜む式で、初見の式である。多分、
多くの方がそうだろうと思う。

(証明) nC2+n+1C2=n(n−1)/2+n(n+1)/2=n2  (終)

 縦n個、横n個の格子から1つを選ぶ選び方は、n2通り

 ところで、nC2+n+1C2=2nC2+nC1=n・n-1C1+nC1 なので、

第1行から1つ選び、その1通りに対して第2行〜第n行から1つ選ぶ

または、 第1行から1つ選ぶ と考えれば、n2通りが導かれる。


(追記) toru さんからのご投稿です。(平成31年4月17日付け)

 「二項係数の性質」で、以下が成りたつと思うのですが証明ができずにおります。

 B(n,k)=nCk=n!/{k!(n−k)!} 、0<x<1 として以下の2つは等しい(?)

 Σk=0n B(n,k)B(n,n-k)xk=Σk=0n B(n,k)B(n+k,n)xk(1−x)n-k

 例えば、n=2 のとき、両式とも 1+4x+x2、n=3 のとき、両式とも 1+9x+9x2+x3 が得られ
て一致します。

 お知恵を拝借できれば大変ありがたく存じます。


 DD++さんからのコメントです。(平成31年4月18日付け)

 3つの非負整数 a、b、c (ただし a≧c、b≧c)に対し、「P = (Y+1)a (Y+X)b を展開したとき
の Yc の係数は何か」という問題を考えてみます。

[1] a乗をそのまま二項展開します。 P = Σ[k=0..a] B(a,k) Y^k (Y+X)^b

 そして、b乗も二項展開します。

P = Σ[k=0..a] B(a,k) Y^k Σ[m=0..b] B(b,m) Y^m X^(b-m)
   = Σ[k=0..a] Σ[m=0..b] B(a,k) B(b,m) X^(b-m) Y^(k+m)

 このうち、 Y^c となる項は、m=c-k であるときです。これは k≦c の範囲でのみ存在しま
す。すなわち、Y^c の係数は、

  Σ[k=0..c] B(a,k) B(b,c-k) X^(b-c+k)

となります。

[2] a乗を少し変形してから二項展開します。

P = {(Y+X)+(1-X)}^a (Y+X)^b
   = Σ[k=0..a] B(a,k) (Y+X)^k (1-X)^(a-k) (Y+X)^b
   = Σ[k=0..a] B(a,k) (1-X)^(a-k) (Y+X)^(b+k)

 そして、(b+k)乗を二項展開します。

P = Σ[k=0..a] B(a,k) (1-X)^(a-k) Σ[m=0..(b+k)] B(b+k,m) Y^m X^(b+k-m)
   = Σ[k=0..a] Σ[m=0..(b+k)] B(a,k) B(b+k,m) X^(b+k-m) (1-X)^(a-k) Y^m

 このうち、Y^c となる項は m=c であるときです。すなわち、Y^c の係数は、

  Σ[k=0..a] B(a,k) B(b+k,c) X^(b-c+k) (1-X)^(a-k)

となります。[1] と [2] は同じ問題について議論したものなので、答えは同じはず。

 よって、

Σ[k=0..c] B(a,k) B(b,c-k) X^(b-c+k) = Σ[k=0..a] B(a,k) B(b+k,c) X^(b-c+k) (1-X)^(a-k)

です。この等式の特殊な場合として、a=b=c=n とすれば、

Σ[k=0..n] B(n,k) B(n,n-k) X^k = Σ[k=0..n] B(n,k) B(n+k,n) X^k (1-X)^(n-k)

が示されます。

#何か組合せ論での証明があれば面白そうですが、そちらは私は思いつけませんでした。


 りらひいさんからのコメントです。(平成31年4月18日付け)

> 「k=0からk=nまで,B(n,k) B(n+k,n) X^k(1-X)^{n-k} の総和」

=Σ[k=0〜n]B(n,k)*B(n+k,n)*X^k*(1-X)^(n-k)
=Σ[k=0〜n]B(n,k)*B(n+k,n)*X^k*{Σ[i=0〜n-k]B(n-k,i)*(-1)^i*X^i}
=Σ[k=0〜n]Σ[i=0〜n-k]B(n,k)*B(n+k,n)*B(n-k,i)*(-1)^i*X^(k+i)

 ここで、h=k+iとおくと、

=Σ[k=0〜n]Σ[h=k〜n]B(n,k)*B(n+k,n)*B(n-k,h-k)*(-1)^(h-k)*X^h

 和の取り方を変えると、

=Σ[h=0〜n]Σ[k=0〜h]B(n,k)*B(n+k,n)*B(n-k,h-k)*(-1)^(h-k)*X^h
=Σ[h=0〜n]Σ[k=0〜h]{n!/k!/(n-k)!}*B(n+k,n)*{(n-k)!/(h-k)!/(n-h)!}*(-1)^(h-k)*X^h
=Σ[h=0〜n]Σ[k=0〜h]B(n+k,n)*{n!/k!/(h-k)!/(n-h)!}*(-1)^(h-k)*X^h
=Σ[h=0〜n]Σ[k=0〜h]B(n+k,n)*{n!/h!/(n-h)!}*{h!/k!/(h-k)!}*(-1)^(h-k)*X^h
=Σ[h=0〜n]Σ[k=0〜h]B(n+k,n)*B(n,h)*B(h,k)*(-1)^(h-k)*X^h
=Σ[h=0〜n]B(n,h)*(-1)^h*X^h*{Σ[k=0〜h]B(n+k,n)*B(h,k)*(-1)^(-k)}

 ここで、「二項係数の性質」の(27)の式を利用すると、

Σ[k=0〜h]B(n+k,n)*B(h,k)*(-1)^(-k)
=Σ[k=0〜h]B(n+k,k)*B(h,h-k)*(-1)^k
=B(h-n-1,h)
=(-1)^h*B(n,h)

が成り立つので、

=Σ[h=0〜n]B(n,h)*(-1)^h*X^h*{(-1)^h*B(n,h)}
=Σ[h=0〜n]B(n,h)*B(n,h)*X^h

 hをkと書き換えれば、

=Σ[k=0〜n]B(n,k)*B(n,k)*X^k
=Σ[k=0〜n]B(n,k)*B(n,n-k)*X^k

> 「k=0からk=nまで,B(n,k) B(n,n-k) X^k の総和」


#とりあえずたどり着いたけど、わたしはまだ「二項係数の性質」(27)を理解していないから、
 証明できたとは言えないな…。


 toruさんからのコメントです。(平成31年4月20日付け)

 DD++さん、素早い解答に驚いています。ありがとうございました。参考にさせて頂きます。

 りらひいさん、(27)の式を使うとは思いもしませんでした。ありがとうございました。


 GAI さんからのコメントです。(平成31年4月20日付け)

 toruさんの記事を見て、

 �納k=0,n]B(n,k)*B(n+k,n)*X^k*(1-X)^(n-k)=�納k=0,n]B(n,k)^2*X^k

が成立することを意味するが、ここに、1^n=(X+1-X)^n=�納k=0,n]B(n,k)*X^k*(1-X)^(n-k)

であることと類して、

 (2x)^n=(X+1+X-1)^n=�納k=0,n]B(n,k)*(X+1)^k*(X-1)^(n-k)

故に、 2^n*x^n=�納k=0,n]B(n,k)*(X+1)^k*(X-1)^(n^k)

従って、 x^n=�納k=0,n]B(n,k)*(X+1)^k*(X-1)^(n-k)/2^n

そこで、 L(n)=�納k=0,n]B(n,k)^2*(X+1)^k*(X-1)^(n-k)/2^n なる関数を定義してやると、

L(0)=1
L(1)=X
L(2)=3/2*X^2-1/2
L(3)=5/2*X^3-3/2*X
L(4)=35/8*X^4-15/4*X^2+3/8
L(5)=63/8*X^5-35/4*X^3+15/8*X
・・・・・

となり、legendre function と呼ばれる関数を構成してくれる構造に類しているように見える。

 さらに、このL(n)同志を組み合わせると、Che(n)=�納k=0,n]L(k)*L(n-k) から、

Che(0)=1
Che(1)=2*X
Che(2)=4*X^2-1
Che(3)=8*X^3-4*X
Che(4)=16*X^4-12*X^2+1
Che(5)=32*X^5-32*X^3+6*X
・・・・・

となり、second chebychev function と呼ばれる関数に繋がる。


(追記) 令和元年11月15日付け

(47) n+1C1+2n+2C2+3n+3C3+・・・+rn+rCr=(n+1)n+r+1Cn+2


(証明) k・n+kCk=k・(n+k)!/(k!n!)=(n+k)!/((k−1)!n!)

=(n+1)・(n+k)!/((k−1)!(n+1)!)=(n+1)・n+kCn+1

よって、

左辺=(n+1)・n+1Cn+1+(n+1)・n+2Cn+1+(n+1)・n+3Cn+1+・・・+(n+1)・n+rCn+1

=(n+1)(n+1Cn+1+n+2Cn+1+n+3Cn+1+・・・+n+rCn+1)

 上記の(11)より、 nCn+n+1Cn+n+2Cn+・・・+n+mCn=n+m+1Cn+1 なので、

  n+1Cn+1+n+2Cn+1+n+3Cn+1+・・・+n+1+(r-1)Cn+1=n+r+1Cn+2

よって、 n+1C1+2n+2C2+3n+3C3+・・・+rn+rCr=(n+1)n+r+1Cn+2  (証終)


(追記) 令和2年7月31日付け

 最近、次のような超絶難問があることを知った。

(48) Σk=0n 2kCk・2n-2kCn-k=4n が成り立つことを証明せよ。


 問題を理解するために、n=1、2、3の場合について書き下してみた。

 n=1 のとき、0C0・2C1+2C1・0C0=4

 n=2 のとき、0C0・4C2+2C1・2C1+4C2・0C0=42=16

 n=3 のとき、0C0・6C3+2C1・4C2+4C2・2C1+6C3・0C0=43=64

 書き下してはみたものの問題の意味がよくわかりませんね!


(解) (1−4x)^(-1/2)のxnの係数は、(2n)!/(n!)2=2nCn なので、

   (1−4x)^(-1/2)=Σn=0∞ 2nCn xk ・・・ (*)

 ここで、 (1−4x)^(-1)=1+4x+42x2+43x3+・・・・

 (*)の右辺の平方のxnの係数は、 Σk=0n 2kCk・2n-2kCn-k

 よって、 Σk=0n 2kCk・2n-2kCn-k=4n が成り立つ。  (終)


 GAI さんからのコメントです。(令和2年8月1日付け)

 上記の、二項係数で4^nが作られていたのを見て、では、3^nはどうしたら作れるか色々挑
戦していたら、偶然、

 ��k=0n 2^k*nCk=3^n

さらに、

 ��k=0n 3^k*nCk=4^n

 ��k=0n 4^k*nCk=5^n

 ��k=0n 5^k*nCk=6^n

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

となるではないか!今までこんな表現を見たことがなかったので(せいぜい��k=0n nCk=2^n)
ビックリしました。

 この現象は当然なんですかね?2項係数の性質としてはとても面白いと思いますので、是
非明示しておいてもらいたい。

(追伸) 後から考えたら、 (1+X)^n=��k=0n nCk*X^k なので、X=1,2,3,4,・・・ とおけば、こ
    れは当然でした!


(コメント) 組合せの「C」だけを用いて表されるところに感動しました。


 りらひいさんからのコメントです。(令和5年8月14日付け)

 私が過去に計算したものをまとめてみました。ここで、nCk を C[n,k] と書くことにします。


(49) C[M+N,M] =Σk=0M C[n+k-1,k]*C[M+N-n-k,M-k]

 =Σk=0N C[m+k-1,k]*C[M+N-m-k,N-k]

 =Σk=0m-1 C[n+k-1,k]*C[M+N-n-k,M-k]+Σk=0n-1 C[m+k-1,k]*C[M+N-m-k,N-k]

 =Σk=mM C[n+k-1,k]*C[M+N-n-k,M-k]+Σk=nN C[m+k-1,k]*C[M+N-m-k,N-k]


 ただし、 1≦m≦M 、1≦n≦N


(証明)は、「数学感動秘話」の「確率」を参照。文字の置き換えをして式を整理していますが、
「確率」のページで、私が示した関係式と考え方は同じです。次のように対応します。

M=「確率」の m+m'+1 、N=「確率」の n+n'+1 、m=「確率」の m+1 、n=「確率」の n+1


(50) (a+b)^n/a=Σk=0n C[n,k]*(a+k)^(k-1)*(b−k)^(n-k)  ただし、 a≠0


(証明)は、「数学感動秘話」の「まち針の木」を参照。


 GAI さんからのコメントです。(令和6年7月6日付け)

 組合せ関数 nCr で成立する代表的なものとして、

  nC0+nC1+nC2+nC3+・・・+nCr+・・・+nCn=2n

がある。その他、色々と例を上げてみますので、挑戦して見て下さい。

#nCk が含まれると、私は直感ではなかなか気が付けません。

(A) nが偶数のとき、 nC0+nC2+nC4+・・・+nCn

(B) nが奇数のとき、 nC0+nC2+nC4+・・・+nCn-1

(C) kの方を固定する。 nCk+n+1Ck+n+2Ck+・・・+n+mCk

(D) n、kを同時に変化させる。 nCk+n-1Ck-1+n-2Ck-2+・・・+n-kC0

(E) n、k、符号を同時に変化させる。2nC0−2n-1C1+2n-2C2+・・・+(−1)nnCn

(F) 2つのC関数の積を組合わす。

 nC0・mCk+nC1・mCk-1+nC2・mCk-2+・・・+nCk・mC0

(G) 2つのC関数の積を符号を交互に組合わす。

 nC0・nCk−nC1・n-1Ck-1+nC2・n-2Ck-2+・・・+(−1)knCk・n-kC0

(H) Cに係数を付随させる。 2nCn+2・2n-1Cn+22・2n-2Cn+・・・+2n・nCn


 らすかるさんからのコメントです。(令和6年7月6日付け)

 (A)と(B)は、上記の(6)、(C)は、上記の(11)、(F)は、上記の(16)に相当しますね。


 りらひいさんからのコメントです。(令和6年7月6日付け)

 (E)は、上記の(12)、(H)は、上記の(13)に相当しますね。

(D)は、上記の(11)の説明文のなかの

 (11)で、k=n のときは、nCr=nCn-r より、次の形にも変形できる。

      nC0+n+1C1+n+2C2+・・・+n+mCm=n+m+1Cm

 この公式は、「総和の公式」とも言われる。


において、n に n-k を代入して m に k を代入すると、

 左辺=n-kC0+n-k+1C1+n-k+2C2+・・・+nCk

すなわち、 左辺=nCk+n-1Ck-1+n-2Ck-2+・・・+n-kC0 となるので、答えは、n+1Ck

(G)は、上記の(27):

 nC0・mCk−n+1C1・mCk-1+・・・+(−1)kn+kCk・mC0=m-n-1Ck

において、両辺に (-1)k をかけて、n に n-k を代入して、m に n を代入したものなので、

答えは、(-1)k・k-1Ck=0


(コメント) らすかるさん、りらひいさん、探索していただいてありがとうございます。


 GAI さんからのコメントです。(令和6年7月8日付け)

 ここにないものを作ってみました。

(I) aCb・cC0+a+1Cb・cC1+a+2Cb・cC2+・・・+a+cCb・cCc (ただし、a≧b≧c≧0)

(J) aC0・sCa−aC1・s-tCa+・・・+(-1)kaCk・s-ktCa+・・・+(-1)aaCa・s-atCa
 (ただし、a、s、t>0 の整数)


(追記) 令和7年5月28日付け

 次の東北大学 前期理系(1994)の問題は、2項係数の新たな等式を示している。

問題  Nを2以上の整数とする。AチームとBチームがある試合をくり返して行い、先にN勝
  したチームを優勝とする。各試合において引き分けはないものとし、それぞれの勝つ確率
  は1/2とする。X回目の試合で優勝チームが決まったものとして、次に答えよ。
(1) P(X≦N+1) を求めよ。
(2) P(X=N+j) (j=0、1、・・・、N−1)を求めよ。
(3) an=Σj=0n n+jCj(1/2)j (n=1、2、・・・) を求めよ。

(解)(1) P(X≦N+1)=2・(1/2)N+2・NC1(1/2)N・(1/2)=(N+2)/2N

(2) P(X=N+j)=2・N+j-1Cj(1/2)N+j-1・(1/2)=N+j-1Cj(1/2)N+j-1

(3) Σj=0N-1 N+j-1Cj(1/2)N+j-1=1 なので、Σj=0N-1 N+j-1Cj(1/2)j=2N-1

ここで、 N−1=n とおくと、 an=Σj=0n n+jCj(1/2)j=2n  (終)


(コメント) 上記の結果から、次の等式が成り立つことが分かる。

 nC0+n+1C1(1/2)+n+2C2(1/2)2+・・・+2nCn(1/2)n=2n

 この等式は、nC0=nCn、n+1C1=n+1Cn、n+2C2=n+2Cn、・・・ とし、両辺を2n倍して

(13) 2nCn+2・2n-1Cn+4・2n-2Cn+・・・+2n・nCn=22n

と変形され、直接示すことも可能である。(→ (13)の証明)


(追記) 令和7年12月1日付け

 次の東北大学 後期理系(2003)の問題は、2項係数の新たな等式を示している。

問題   (1) 正の整数nに対して、F(x)=(ex−e-x)n とする。F’(0)を求めよ。
(2) Σk=0n nCk(−1)k(n−2k) を簡単にせよ。

(解)(1) n=1 のとき、 F(x)=ex−e-x より、F’(x)=ex+e-x から、F’(0)=2

 n≧2 のとき、 F(x)=(ex−e-x)n より、 F’(x)=n(ex−e-x)n-1・(ex+e-x) から、

 F’(0)=0

(2) F(x)=(ex−e-x)n について、2項定理より、

 F(x)=Σk=0n nCk(ex)n-k(−e-x)k=Σk=0n nCk(−1)k(ex)n-2k

よって、 F’(x)=Σk=0n nCk(−1)k(n−2k)(ex)n-2k から、

 Σk=0n nCk(−1)k(n−2k)=F’(0)

が成り立つ。したがって、(1)より、

 n=1 のとき、 Σk=0n nCk(−1)k(n−2k)=2

 n≧2 のとき、 Σk=0n nCk(−1)k(n−2k)=0  (終)

 したがって、次の公式を得る。

(51) Σk=0n nCk(−1)k(n−2k)=0  ただし、 n≧2

 ただし、n=1のときは、上記の値は、2 となる。



   以下工事中