Σ(-1)^k(nCk)kを求めるkilling involution
自然数 について,以下の和を組合せ論的手法で求める.
まず,和をの冪集合についての和に書き換える.とかくと
さらに,この和を集合についての和に変えることができて,
となる.
のとき,からへの対合で,とすると,
が成立するものを構成することができる.対合とは二回当てると元に戻る写像 ()のことである.
そのような対合が存在するので,集合にはが偶数のものと奇数のものが同数存在することが分かり,総和がになるのである.
このような論法はkilling involutionと呼ばれる.
以下,対合を構成する.
とする.
自然数をと定める.
ならば,とする.
ならば,とする.
するとこれは対合であって,は当てる前後で変化している.
(証明終わり.)