解答例 1

$n$ を $2$ 進展開して $$ n = 2^{\nu_1}+2^{\nu_2}+\cdots+2^{\nu_t},\quad \nu_i\in\mathbb{Z},\quad 0\leq \nu_1<\nu_2<\cdots<\nu_t $$ と表す. さらに, $\mu_i=2^{\nu_i}$ ($i=1$, $2$, $\ldots$, $t$) とおく.

$\mathbb{F}_2[X]$ において, \begin{align*} (1+X)^{n} &= (1+X)^{\mu_1}(1+X)^{\mu_2}\cdots (1+X)^{\mu_t} \\ &= (1+X^{\mu_1})(1+X^{\mu_2})\cdots (1+X^{\mu_t}) \\ &= \sum_{S\in\mathfrak{P}(I)} X^{\lambda(S)}. \end{align*} ここで, $I=\{1, 2, \ldots, t\}$ とし, $\mathfrak{P}(I)$ を $I$ の部分集合全体からなる集合族とする. また, $S\in\mathfrak{P}(I)$ に対して, $\chi_S: I \rightarrow \{0, 1\}$ を $I$ における $S$ の定義関数とする. すなわち, $\chi_S$ は $$ \chi_S(x) = \begin{cases} 1, & x\in S, \\ 0, & x\in I\setminus S \end{cases} $$ によって定まる写像である. さらに, 写像 $\lambda:\mathfrak{P}(I)\rightarrow\mathbb{N}$ を $$ \lambda(S) = \chi_S(1)\mu_1+\chi_S(2)\mu_2+\cdots+\chi_S(t)\mu_t $$ によって定める. $2$ 進展開による表示の一意性から, $\lambda$ は単射である.

また, 二項定理より, $$ (1+X)^{n} = \sum_{r=0}^{n}\binom{n}{r}X^r. $$ ゆえに, $$ \sum_{r=0}^{n}\binom{n}{r}X^r = \sum_{S\in\mathfrak{P}(I)} X^{\lambda(S)}. $$ $\displaystyle\binom{n}{r}$ ($0\leq r\leq n$) のうち奇数であるものの個数は, 右辺において係数が $0$ でない項の個数であり, それは集合 $\{ \lambda(S) \mid S\in\mathfrak{P}(I) \}$ の元の個数に一致する. $\lambda$ は単射だから, この集合の元の個数は $I$ の部分集合全体の個数 $2^t$ に等しい.

最終更新日：2011年11月02日