부분집합 구하기, 부분집합의 개수 구하기 핵심 정리 및 목차
- 부분집합을 구할 때는 원소의 개수를 0부터 하나씩 늘려가면서 찾는다.
- n(A) = n일 때, 집합 A의 부분집합의 개수 = 2n
부분집합 구하기, 부분집합의 개수 구하기 설명 및 예제
부분집합 구하기
부분집합을 구할 때 가장 쉬운 방법은 원소의 개수를 0개부터 하나씩 늘려가며 구하는 거예요.
A = {1, 2, 3, 4}의 부분집합을 구해보죠.
- 원소의 개수가 하나도 없는 부분집합, 즉 공집합 ∅
- 원소의 개수가 하나인 부분집합: {1}, {2}, {3}, {4}
- 원소의 개수가 두 개인 부분집합: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
- 원소의 개수가 세 개인 부분집합: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
- 원소의 개수가 네 개인 부분집합: {1, 2, 3, 4}
원소의 개수가 다섯 개인 부분집합은 없겠죠.
이렇게 원소의 개수를 하나씩 늘려서 찾다 보니 총 16개의 부분집합을 구했네요.
부분집합의 개수 구하기
부분집합의 개수는 위처럼 직접 부분집합을 구해서 그 개수를 셀 수도 있겠지만 너무 비효율적이에요. 그래서 공식으로 알아두면 좋아요. 공식은 경우의 수를 이용하면 쉽게 구할 수 있어요.
A = {1, 2, 3, 4}의 부분집합에는 1을 포함하는 부분집합이 있을 수 있어요. 반대로 1을 포함하지 않는 부분집합도 있겠지요. 그러니까 부분집합에 1이 있거나 없거나 두 가지 경우가 생기죠.
또, A의 부분집합 중에는 2를 포함하는 부분집합과 2를 포함하지 않는 부분집합이 있을 거예요. 역시 두 가지 경우네요. 3, 4도 마찬가지로 포함하거나 포함하지 않거나 각각 두 가지 경우가 생기죠.
각 원소 1, 2, 3, 4에서 두 가지씩 경우의 수가 생기는데 이는 동시에 발생하는 사건으로 곱의 법칙을 사용해야 하죠?
원소별로 경우의 수가 2이므로 이를 모두 곱하면 부분집합의 개수를 구할 수 있어요.
A = {1, 2, 3, 4}에서 원소의 개수는 네 개죠. 그래서 2를 네 번 곱해주는데, 24 = 16이네요.
직접 구해본 부분집합의 수를 세어봤더니 역시 16개였죠. 어때요? 개수만 구하려고 할 때는 그냥 위 공식을 이용하는 것이 좋겠죠?
부분집합을 직접 구해야 하는 문제가 나올 수도 있어요. 이럴 때 공식을 이용해서 부분집합의 개수를 먼저 구한 다음에 그 개수에 맞게 부분집합을 찾는 것도 좋은 방법입니다.