二項係数の和,二乗和,三乗和
二項係数の総和,二乗和,三乗和に関する美しい公式を解説します。
は 以上の任意の整数とします。
二項係数の和
二項係数の二乗和
二項係数の三乗和
二項係数の和
例えば のとき,
となっています。
証明は二項定理を使うだけで簡単にできます。
二項定理より
後半の式も同様。
「部分集合の個数」を数えることでも証明できます。
「集合 の部分集合の個数 」を2通りの方法で数える。
-
全ての要素について「含める」or「含めない」の2通りなので,
-
要素数が である部分集合の個数は である。これを から まで足し上げると,
また,後半の式も似たように考えることができる。
の部分集合のうち要素数が奇数のものを全て集めた集合を ,要素数が偶数のものを全て集めた集合を とする。
を証明すればよい。これは,特定の要素を「交換」するという一対一対応を構成できることからわかる。
具体的には, の集合に対して を「交換」(あれば除く,なければ追加)することで の集合が対応する。これは一対一対応になる。
※証明2の後半部分は「松坂和夫先生の集合・位相入門」という本を参考にしました。
二項係数の二乗和
例えば のとき, ,
となり一致しています。2通りの証明を紹介します。
図のような格子状の道において, から までの最短経路の数を2通りの方法で数える。
-
個の「右」と 個の「上」を並べる場合の数に等しいので, 通り。
-
途中で を必ず1つだけ通る。そして, を通る最短経路の数は, である。( まで行く方法が 通り,そこから まで行く方法も 通り)
よって,目標の式は示された。
二項係数の三乗和
例えば のとき,
となり一致しています。
証明は難しいようです。
追記:せきゅーん氏が証明を教えて下さいました: ディクソンの恒等式 - インテジャーズ
シンプルで非自明な恒等式が大好きです。