組合せに関する等式の解釈

質問

まず前ふり。

Σ(i=0,n)nCi=2^n

と言う等式を考えます。
nCiはn個のものの中からi個のものを選ぶ選び方の数、
いわゆるコンビネーションだと思ってください。

この式の解釈として

「左辺はn個のものから0個を選ぶ、1個を選ぶ、2個を選ぶ、、、n個を選ぶ
と言う風に全ての個数について選び方が何通りあるか数えている。それはn個
の中から自由に選ぶ場合の選び方を数えているのと同じだ。自由に選べるとす
れば個々の要素について選ぶ、選ばないの2択があるわけだから2^n通りの選
び方がある。よって左辺と右辺は等しい。」

というのが考えられます。解釈があれば複雑な式もふむなるほどと納得できる
物です。

さて、本題。

1、要素数nの集合A、Bがあるとき、AとBから同じ数だけ物を選ぶ選び方。
2、2n個の中からn個の物を選ぶ選び方。

この2つがどうやら同じになりそうなんです。式で書くと

Σ(i=0,n)(nCi)^2=2nCn

となります。なりそう、というのはちゃんと証明したわけではないのですが
計算機でnが小さいときの値を計算したら一致したのでおそらく成り立つ
だろう、と思うわけです。

で、この式が成り立つとして、どう解釈したら良いのでしょう。
どなたかウマイ解釈をお願いします。

ついでに式の証明もお願いします。

回答No.2

funi2 · ベストアンサー

以下の証明, 解釈は組み合わせ数学入門1 C.L.リウ著 伊里正夫, 伊里由美共訳(共立出版)からです。大きい図書館に行けば見つかると思います。
まずは証明から。ちょっと遠回りに見えますが, 全体を眺めてください。
証明) 式(1+x)^n(1+x^(-1))^n...(*)の定数項を考えます。この式の定数項は
(nC0)^2+(nC1)^2+...+(nCn)^2
で与えられます。さて, 式(1+x)^n(1+x^(-1))^nを変形すると,
(1+x)^n(1+x)^nx^(-n)
= (1+x)^(2n)x^(-n)...(#)
となります。この式の定数項を考えると,
2nCn
で与えられることがわかります。
式(*)と(#)は等しいですから等しい定数項を持ちます。従って,
(nC0)^2+(nC1)^2+...+(nCn)^2 = Σ(i=0,n)(nCi)^2 = 2nCn
が成り立ちます。 (証明終わり)

さて, 解釈ですが, Aからi個選んだとき, Bからもi個選ぶわけですが, これは同時にBからn-i個を選ぶ作業に等しいわけです。そこでAからi個選んだとき, Bからn-i個選ぶ作業methodを考えます。
ここで, 2n個のものからn個の物を選ぶことも同時に考えましょう。このとき選ぶ方法として, 2n個のものをn個の2つの集合に分け, 片方からi個選び, もう片方からn-i個選ぶとします。
これはmethodに等しい選び方です。従って,
2nCn = Σ(i=0,n)(nCi)(nC(n-i)) = Σ(i=0,n)(nCi)^2
となります。

なんか解釈の順番がおかしいので, 気持ち悪いのですが, これで許してください。

お礼

回答ありがとうございます。
やはり多項式の係数と結びつけるというのが有効な手段ということですか。
勉強になりました。
解釈の方ですが、これこれ、これが欲しかったんですよ。
言われてみればなるほど納得です。
ありがとうございました。

回答No.1

ayucat

現役高校生なので、ちょっと。

> Σ(i=0,n)nCi=2^n

　この証明ですが、一般的に、二項定理を用いて、
証明する気がします。

nC0 + nC1 + nC2 + ... + nCr
= (1+1)^n
= 2^n

としてます。

お礼

回答ありがとうございます。
確かに証明できていますね。

ところでayucatさんは二項定理がなぜ成り立つか知っていますか。
二項定理の言わんとしていることを知らずに、定理なんだ黙って納得しろ、
というのではちとさみしいと僕なんかは思うわけです。
だからこそ僕は式の解釈なんてものを欲しがるわけです。

そっちの式は前ふりなので本題の方もお願いします。