質問: 組合せに関する等式の解釈 まず前ふり。 σ(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が小さいときの値を計算したら一致したのでおそらく成り立つ だろう、と思うわけです。 で、この式が成り立つとして、どう解釈したら良いのでしょう。 どなたかウマイ解釈をお願いします。 ついでに式の証明もお願いします。
回答: 以下の証明, 解釈は組み合わせ数学入門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 となります。 なんか解釈の順番がおかしいので, 気持ち悪いのですが, これで許してください。