021部分集合の個数

問題メタで紹介した部分集合を例に説明します。$A=\{1,2\}$ の部分集合は、次のように考えることができます。

• $\{1\}$：1を使う、2を使わない
• $\{2\}$：1を使わない、2を使う
• $\{1,2\}$：1を使う、2を使う
• $\varnothing$：1を使わない、2を使わない

「使う」を○、「使わない」を×とすれば、1と2のそれぞれについて○か×を選ぶことになります。つまり、2人がそれぞれ○か×を選ぶ重複順列と同じです。

各要素について「使う・使わない」の2通りがあるため、要素が2個なら $2^2$ 通り、要素が $n$ 個なら $2^n$ 通りとなります。部分集合の個数を求める問題では、このように各要素へ○×を付けると考えると分かりやすいです。