部分集合の部分集合の数の和

サイズNの集合の部分集合の部分集合の数の和は$3^N$

• サイズkの集合の部分集合の数は$2^k$
• サイズNの集合に、サイズkの部分集合はいくつあるか→N個からk個選ぶ組み合わせ
• 二項定理を逆に使う
  • $\sum_{k=0}^N \binom{N}{k} 2^k = \sum_{k=0}^N \binom{N}{k} 2^k 1^{N-k} = (2 + 1)^N= 3^N$