数学の命題示しました

主に組合せ論について,読んだ本で出てきたことや,考えたことを書きます.

Σ(-1)^k(nCk)kを求めるkilling involution

自然数  nについて,以下の和を組合せ論的手法で求める.
 \displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}k= \left\{ \begin{array}{}-1 & n=1\\0& n>1\end{array} \right.




まず,和を \{1,\ldots,n\}の冪集合についての和に書き換える. [n]\triangleq\{1,\ldots,n\}とかくと
 \displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}k= \sum_{A\subseteq[n]}(-1)^{|A|}|A|

さらに,この和を集合 \mathcal{R}\triangleq\{(A,i)\mid i\in A\subseteq[n]\}についての和に変えることができて,

\displaystyle = \sum_{(A,i)\in\mathcal{R}}(-1)^{|A|}
となる.


 n>1のとき, \mathcal{R}から \mathcal{R}への対合 \varphiで, (B,j)=\varphi(A,i)とすると,
 |B|=|A|\pm 1
が成立するものを構成することができる.対合とは二回当てると元に戻る写像 ( \varphi\circ\varphi={\rm id})のことである.
そのような対合 \varphiが存在するので,集合 \mathcal{R}には |A|が偶数のものと奇数のものが同数存在することが分かり,総和が 0になるのである.
このような論法はkilling involutionと呼ばれる.

以下,対合 \varphiを構成する.


 (A,i)\in\mathcal{R}とする.
自然数 r r\triangleq \min([n]\setminus\{i\})と定める.
 r\in Aならば, \varphi(A,i)\triangleq (A\setminus\{r\},i)とする.
 r\notin Aならば, \varphi(A,i)\triangleq (A\cup\{r\},i)とする.
するとこれは対合であって, |A|は当てる前後で \pm 1変化している.

(証明終わり.)