부분집합의 개수
number of subsets
"각 원소마다 포함 또는 배제의 경우로 나누어 생각하면 아주 쉬워요"
" count the outcomes whether each element is
included or excluded "
부분집합의 개수를 구하는 유형은, 고 1 에서의 [집합] 단원 뿐만 아니라, 중고등 수학 전반에서 [경우의 수] 등의 응용문제로 다양하게 출제되고 있습니다.
따라서, 기본적인 개념과 '포함과 배제의 원리' 는 철저하게 이해해 두는 것이 필요합니다.
여기에서는 기본원리 위주로 핵심개념만 설명합니다. 선행이나 심화과정이 아니라면, 중학생은 생략해도 됩니다.
♧ ♧ ♧ ♧ ♧ ♧
예를 들어, 집합 A = {4, 5} 의 부분집합은 한 개의 원소를 갖는 {4}, {5} 그리고 자기자신 {4, 5} 그리고 추가로 원소가 하나도 없는 공집합 Ø 도 부분집합으로 정의하는 경우, 총 4 개의 부분집합을 갖게 됩니다. 공집합 Ø 는 { } 로도 표시하지요.
위 예의 집합 A = {4, 5} 에서 자기자신 {4, 5} 를 제외하고, {4}, {5} 와 공집합 Ø 을 집합A 의 진부분집합이라고 따로 명시합니다.
그러면, 집합 A 의 부분집합의 개수는 어떻게 계산되는 것일까요?
4 ∉
|
4 ∈
| |
5 ∉
|
Ø
|
{4}
|
5 ∈
|
{5}
|
{4, 5}
|
위의 표에서 보는 것과 같이, 특정 원소 하나가 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 를 구분하는 데에 따르는, 경우의 수를 구하는 방법과 같습니다.
따라서, 만일 원소의 개수가 4 개 라면, 각각의 원소마다 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 의 2 가지 경우의 수를 가지므로, 2 x 2 x 2 x 2 = 24 = 16 개가 됩니다.
위에서 설명한 원리를 가지고, 문자로 일반화시킨 공식을 만들어 볼까요?
원소가n 개인 집합의 부분집합의 개수는, 각각의 원소마다 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 의 2 가지 경우를 갖게 된다. 따라서, 2 가 n 번 곱해지는 것과 같으니까, 2n 개.
이제 약간 응용된 예를 한번 볼까요?
집합 X 가 {3, 4, 5, 6, 7} 의 부분집합이고 {2, 3, 4, 5} ∩ X = {3, 4} 를 만족할 때, 서로 다른 집합 X 의 개수를 구하여라.
(1) 우선, 집합 기호로 주어진 문제의 조건을 잘 이해해야 합니다. 집합 X 가 {3, 4, 5, 6, 7} 의 부분집합이면서, 원소 3, 4 는 포함하고, 원소 5 는 포함하지 않는다는 뜻이지요?
(2) 이제, 각각의 원소마다 경우의 수를 따져보면, 원소 6, 7 은 각각 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 의 경우의 선택이 가능하지만
(3) 원소 3, 4 는 포함되는 경우만 가능하므로 이미 한가지 경우로만 정해져 버렸다는 뜻이 되는 것이고
(4) 원소 5 도 포함하지 않는 경우만 가능하므로 이미 한가지 경우로만 정해져 버렸다는 뜻이 됩니다.
(5) 즉, 원소 6, 7 은 각각 2가지 선택이 가능하지만, 원소 3, 4, 5 의 경우는 이미 한가지 경우로만 정해져 버렸으므로, 부분집합 X 의 개수는 25-3 = 22 = 4 개
다음은 조금 어려운 개념이지만, 상위의 심화수학으로 갈수록 복층식 개념구조를 익혀 둘 필요가 있다는 점에서, 멱집합 (power set) 을 알아 보도록 하지요.
예를 들어, 집합 A = {4, 5} 에 대하여, 집합 A 의 멱집합은 A 의 부분집합들을 원소로 갖는 집합으로, P(A) 또는 2A 으로 표시합니다. 즉, P(A) = {Ø, {4}, {5}, {4, 5}} 또는 {{ }, {4}, {5}, {4, 5}} 라고 나타낼 수 있지요.
위의 집합 A 의 멱집합의 부분집합의 개수는 24 = 16 개가 됩니다. 연습 삼아서, 모두 순서대로 나열해 보도록 할까요? 조금 어렵게 느껴진다면, 멱집합의 원소가 되는 {4, 5} = b 와 같이 치환하면 쉬워집니다.
Ø = { }
{Ø}, {{4}}, {{5}}, {{4, 5}}
{Ø, {4}}, {Ø, {5}}, {Ø, {4, 5}}, {{4}, {5}},
{{4}, {4, 5}}, {{5}, {4, 5}}
{Ø, {4}, {5}}, {Ø, {4}, {4, 5}}, {Ø, {5}, {4, 5}}, {{4}, {5}, {4, 5}}
{{Ø, {4}, {5}, {4, 5}}}
일반화시켜서, 원소가 n 개인 집합의 멱집합의 부분집합의 개수를 알아 볼까요?
원소가 n 개인 집합 B = { b1,
b2, … bn} 의 부분집합의 개수는 2n 개 이니까, 멱집합의 원소의 개수도 2n 개 이겠지요?
여기서, 더 쉽게 이해할 수 있도록 2n = k 라고 치환하도록 할까요?
이제, 멱집합의 원소의 개수가 k 개 이니까, 위에서 배웠던 대로, 멱집합의 부분집합의 개수는 2k 개가 됩니다.
따라서, 멱집합의 부분집합의 개수는 2k = (2)^(2n) 개가 됩니다.
