パスカルの三角形の偶数番目と奇数番目

問題

$a_1, a_2, .. a_n$はそれぞれ集合$\{1, -1\}$の元とする。

これらの積$a_1 a_2 .. a_n$が$1$に等しいとき、そのような$a_1, a_2, .. a_n$の組み合わせは何通りあるか？

解答1

$n-1$番目まで自由に決めると、条件$a_1 a_2 .. a_n = 1$から、$n$番目が$1$または$-1$に決まる。

結局、$a_1, a_2, .. a_{n-1}$ の自由な組み合わせの総数と等しく、$2^{n-1}$通り。

解答2

$a_1 a_2 .. a_n = 1$という条件から、$-1$は偶数個含まれる。$0, 2, … $それぞれ考えて、

$$ \sum^{n}_{k:偶数} \binom{n}{k} $$

とおりであるが、

2項定理から、

$$ (1-1)^n = \sum^{n}_{k=0} \binom{n}{k} (-1)^k = \sum_{k:偶数}^{n} \binom{n}{k} - \sum_{k:奇数}^{n} \binom{n}{k} = 0 $$

したがって、

$$ \sum_{k:偶数}^{n} \binom{n}{k} = \sum_{k:奇数}^{n} \binom{n}{k} $$

故に

$$ \sum_{k:偶数}^{n} \binom{n}{k} = \frac{\sum_{k=0}^{n} \binom{n}{k}}{2} $$

ふたたび2項定理から、

$$ \sum_{k=0}^{n} \binom{n}{k} = (1+1)^{n} = 2^n $$

だから、

$$ \sum_{k:偶数}^{n} \binom{n}{k} = \frac{2^n}{2} = 2^{n-1} $$

通り。

解答3

解答2と同じだが、

$$ \sum_{k:偶数}^{n} \binom{n}{k} $$

を別のやり方で求める。

$n$がもし奇数で$2m + 1$と表せるとすると、それは、

$$ \binom{2m+1}{0} + \binom{2m+1}{2} + \binom{2m+1}{4} + … + \binom{2m+1}{2m} $$

$$ \binom{n}{k} = \binom{n}{n-k} $$

を各項に適用すると、

$$ \binom{2m+1}{2m+1} + \binom{2m+1}{2m-1} + \binom{2m+1}{2m-3} + … + \binom{2m+1}{1} $$

これは、奇数番目を逆順に足し合わせたものと全く等しい。

したがって、

$$ \sum_{k:偶数}^{n} \binom{n}{k} = \sum_{k:奇数}^{n} \binom{n}{k} $$

が言える。

これはパスカルの三角形の奇数段目を見れば自明である。

$n$が偶数で$2m$と表される場合は、その一段上の奇数段目をみて、

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

を利用する。

$$ \binom{2m}{2} + \binom{2m}{4} + … + \binom{2m}{2m-2} = \binom{2m-1}{1} + \binom{2m-1}{2} + \binom{2m-1}{3} + \binom{2m-1}{4} … + \binom{2m-1}{2m-2} $$

さらに、

$$ \binom{2m}{0} = \binom{2m-1}{0} $$

$$ \binom{2m}{2m} = \binom{2m-1}{2m-1} $$

を両辺に付け加えれば、結局、

$$ \sum_{k:偶数}^{n} \binom{n}{k} = \sum_{k=0}^{n-1} \binom{n-1}{k} = 2^{n-1} $$

だから、偶数段目でもこの関係は成立するのである。

偶数段目の求め方と同じやりかたで、奇数段目についても証明できるのであるが、奇数段目はパスカルの三角形を見てみれば対称性から (全く同じものを足し合わせているので)自明であるいっぽう、 偶数段目については別の工夫する必要があるので、ここではそのようにした。