(집합) 부분 집합의 개수 공식: 쉽고 빠르게 이해하기

집합의 부분 집합 개수를 구하는 공식은 매우 간단합니다. n개의 원소를 가진 집합의 부분 집합은 총 2ⁿ개가 있습니다.

이 공식은 왜 이렇게 나오는 걸까요? 각 원소는 부분 집합에 포함될 수도 있고, 포함되지 않을 수도 있습니다. 즉, 각 원소는 두 가지 선택지를 가지고 있습니다.

예를 들어, 원소가 3개인 집합 {a, b, c}를 생각해 봅시다.

a는 부분 집합에 포함될 수도 있고, 포함되지 않을 수도 있습니다 (2가지 선택).
b도 마찬가지로 부분 집합에 포함될 수도 있고, 포함되지 않을 수도 있습니다 (2가지 선택).
c 또한 부분 집합에 포함될 수도 있고, 포함되지 않을 수도 있습니다 (2가지 선택).

따라서 총 가능한 경우의 수는 2 * 2 * 2 = 2³ = 8가지가 됩니다. 실제로 {a, b, c} 집합의 부분 집합은 다음과 같이 8개가 있습니다.

* {} (공집합)
* {a}
* {b}
* {c}
* {a, b}
* {a, c}
* {b, c}
* {a, b, c}

이처럼 원소의 개수가 n개라면, 각 원소는 2가지 선택지를 가지므로, 총 가능한 부분 집합의 개수는 2ⁿ개가 됩니다.