📂レンマ

n個の要素を持つ有限集合の部分集合の数

公式

二項係数の和の公式 ¹

二項係数の和は次のようになる。 $$ 2^{n} = \sum_{k=0}^{n} \binom{n}{k} $$

補題: 冪集合の濃度

有限集合 $S$ の濃度が $n = |S|$ であれば、その冪集合 $2^{S}$ の濃度は $2^{n}$ である。

導出

二項定理: $$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$

$x = y = 1$ を代入すると $2^{n} = \sum_{k=0}^{n} \binom{n}{k} 1^{k} 1^{n-k}$ を得る。

■