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

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

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