집합(4) 부분집합의 개수: 공식과 예시를 통한 이해

원소가 n개인 집합의 부분집합의 개수를 알아보자!

원소가 n개인 집합의 부분집합은 각 원소가 포함되거나 배제될 수 있는 두 가지 경우를 가지고 있어요. 즉, 각 원소에 대해 두 가지 선택지를 가지게 되는 거죠. 예를 들어, {a, b, c}라는 집합을 생각해 봅시다.

* a는 포함되거나 배제될 수 있습니다.
* b는 포함되거나 배제될 수 있습니다.
* c는 포함되거나 배제될 수 있습니다.

이렇게 각 원소에 대해 두 가지 선택지를 가지기 때문에, 전체 부분집합의 수는 2를 n번 곱한 값, 즉 2^n이 됩니다.

좀 더 자세히 설명해 볼게요. 원소가 n개인 집합의 부분집합을 만들 때, 각 원소는 ‘포함’ 또는 ‘배제’라는 두 가지 선택지를 가지고 있습니다. 예를 들어 원소가 3개인 집합 {a, b, c}의 부분집합을 만들려면, a, b, c 각각에 대해 ‘포함’ 또는 ‘배제’를 선택해야 합니다. 이러한 선택은 각 원소마다 독립적으로 이루어지기 때문에, 가능한 부분집합의 수는 각 원소에 대한 선택지 수를 모두 곱한 값이 됩니다.

따라서 원소가 n개인 집합의 부분집합은 2^n개가 됩니다.

예를 들어, 원소가 3개인 집합 {a, b, c}의 부분집합은 다음과 같이 2^3 = 8개가 있습니다.

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

이처럼 부분집합의 개수는 집합의 원소 수가 늘어날수록 기하급수적으로 증가합니다.