二項係数の和が 2 の n 乗になる理由

nC0 + nC1 + … + nCn を求めます。パスカルの三角形の第 n 行の和で、値はちょうど 2ⁿ になります（n 個のものからの部分集合の総数）。

解説

二項係数 $\binom{n}{k}$ （ $n$ 個から $k$ 個を選ぶ組み合わせの数）を、 $k = 0$ から $k = n$ まで足し合わせます。答えはいつもきれいに $2^n$ になります。パスカルの三角形でいえば、第 $n$ 行を横に足した値です。

\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n

$n$ — 0 以上の整数
和 — 二項係数をすべて足した値
$2^n$ — 比べるために並べて表示します。理論どおりなら 2 つは一致します

なぜ $2^n$ になるのかは、部分集合を 2 通りに数えると分かります。 $n$ 個のものから部分集合を作るとき、左辺は「ちょうど $k$ 個選ぶ場合の数」を $k$ ごとに数えて合計しています。一方の右辺は「各要素を入れるか入れないかの 2 択を $n$ 回繰り返す」と数えています。同じものを別のやり方で数えているので、値は一致します。

例

$n = 10$ とします。パスカルの三角形の第 10 行は

1,\ 10,\ 45,\ 120,\ 210,\ 252,\ 210,\ 120,\ 45,\ 10,\ 1

です。これを全部足すと 1024 になり、 $2^{10} = 1024$ と一致します。

注意

$n$ は 0 以上の整数です。 $n = 0$ のときの和は $\binom{0}{0} = 1$ で、 $2^0 = 1$ と一致します
この等式は、二項定理 $(1 + x)^n = \sum_k \binom{n}{k} x^k$ に $x = 1$ を代入したものです
各行は左右対称です。 $\binom{n}{k} = \binom{n}{n-k}$ が成り立つためで、上の並びも中央の 252 を軸に対称になっています
この電卓は $n \le 53$ までです。倍精度で整数を厳密に扱えるのは $2^{53}$ までで、それを超えると和と $2^n$ が別の数として表示されてしまうためです。もっと大きい $n$ の $2^n$ は、累乗の電卓で求められます