二項係数の関係式と考え方(2014/7/15)
この知恵ノートは一番最後に紹介される質問がきっかけとなった。
二項係数の関係式は多くありまとめるのは畏れ多いとも思ったけど、
そのうちいくつかをまとめてみるのはそれなりに意義があると思った。

二項係数の関係式で組み合わせ的に説明できるものを
組み合わせを持ちださずに説明する際に有用な定理、
という目的をひそかに背景にしつつ定理の形で紹介する。
従って組み合わせ解釈を使わない説明を常に言及し、
組み合わせ解釈もできる限り言及するようにした。
アルファベットがつくものは定理から得られる系という意図である。

====================
シグマを使わない関係式

[0] C(a,b)=C(a,a-b)
[1] C(a,b)=C(a-1,b-1)+C(a-1,b)
[2] C(a,b)*b = a*C(a-1,b-1)
[3] C(a,b)*C(b,c) = C(a,c)*C(a-c,b-c)
[3a] C(a,b)*C(b,c) = C(a,b-c)*C(a-b+c,c)
[3b] C(a,b)*C(a-b,c) = C(a,c)*C(a-c,b)
[3c] C(a,b)*C(a-b,c) = C(a,b+c)*C(b+c,b)

[説明]
いずれも定義 C(a,b)=a!/{b!(a-b)!}で確認可能。
組み合わせ的解釈などを添えてみる。

[1] パスカルの三角形。
委員をb人選ぶときに自分を入れるかどうか。
[2] いわゆる委員長の定理。
委員全体を先に決めるか、委員長を先に決めるか。
[3] 委員長がc人に増えた場合である。

[3]でcの代わりにb-cとおくと[3a]
[3]でbの代わりにa-bとおくと[3b]
[3a]でbの代わりにa-bとおくと[3c]
をそれぞれ得られる関係。(適宜[0]を使う。)

====================
シグマを使う関係式

[4] Σ[k≦n] C(k,a) = C(n+1,a+1)
[5] (1+x)^a = Σ[k] {C(a,k)*x^k}
[6] Σ[k] {C(a,b+k)*C(c,d-k)} = C(a+c,b+d) 
[7] (1+x+x^2+x^3+...)^a = Σ[k] {H(a,k)*x^k}
[8] Σ[k] {H(a,b+k)*H(c,d-k)} = H(a+c,b+d)
(ただしH(x,y)=C(x+y-1,y)は重複組み合わせ)
[5a] Σ[k] {C(a,k)*C(k,b)} = C(a,b)*2^(a-b)
[6a] Σ[k] {C(a,b+k)*C(c,d+k)} = C(a+c,b+c-d) 
[8a] Σ[k] {C(a+k,b+k)*C(c-k,d-k)} = C(a+c+1,b+d)
[8b] Σ[k] {C(a+k,b)*C(c-k,d)} = C(a+c+1,b+d+1) 

ただし定義されないような二項係数は0と扱うことによって
範囲に制限が無い[k]は全整数をとると扱う。

[説明]
[4] "斜めに消えるパターン"として有名。C(k,a)=C(k+1,a+1)-C(k,a+1)
 順番が逆になるが、[8b]でa=0,b=A,c=n,d=0とおいても得られる。
[5] 二項定理。組み合わせ的解釈、さもなければ数学的帰納法で示せる
[6] (1+x)^a*(1+x)^c の x^(b+d)の係数の2通りの解釈。
 組み合わせ解釈は、a人の集合とc人の集合から合計b+d人選ぶ方法。
[7] あまり知られていない。組み合わせ解釈または数学的帰納法で示せる。
 等比級数を 1/(1-x) と扱って微分を使う手も考えられる。
[8] [7]に対して、[5]に対する[6]と同様。組み合わせ解釈も分かりやすい。
 すなわちa人の集合とc人の集合から重複ありで合計b+d人選ぶ方法。
[5a] [3]を使うか、あるいは[5]の両辺のb階微分を考えて示せる。
[6a] [6]に対して[0]を使って定数を置き換えてみたもの
[8a] [8]を二項係数で書きなおして定数を整理したもの
[8b] [8a]に対して[0]を使って定数を置き換えてみたもの

過去に私が見た質問での例:
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13107866993
この問題は[7]に帰着できる。(kyotochakuさんが既に指摘している)
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10114035985
この補足に書いた疑問は[8a]の式である。(私自身の成長の証)

======================
二項係数の関係式で組み合わせ的に説明できるものを
組み合わせを持ちださずに説明する試行の際の思考、
それは実は組み合わせ解釈を段階に分解する作業である。

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10131824805
左辺は先に悪の手下(委員長)を選出し、
残りの人からさらに打撃屋(副委員長)を選出する考えである。

[まず後半の選出課程を次のように変更する]
先に悪の手下(委員長)を選出し、
次に残りから打撃屋を選出し、最後に残りから魔法使いを選出する。

[次に前半の順番を次のように入れ替える]
悪の手下+打撃屋(右手にクリスタルを持つ人)を選出し、
その中から悪の手下を選出する。最後に残りから魔法使いを選出する。

[再度後半に注目する]
右手にクリスタルを持つ集合の中から悪の手下を選出し、
右手にクリスタルを持たない集合から魔法使いを選ぶ(合計が定数)
これは全員から左手にクリスタルを持つ人を選出するのと同等。

[まとめると]
右手の集合からクリスタルを持つ手を選出し、
左手の集合からクリスタルを持つ手を選出する(合計が定数)
これは手の集合全体からクリスタルを持つ手を選出するのと同等。

この4段階の変形が、私の回答の各段階で実現されている。
変数の意味としてはkは悪の手下の人数、jは打撃屋の人数、
従ってAは右手にクリスタルを持つ人の人数である。

戻る inserted by FC2 system