집합(3) 부분집합의 개수

부분집합의 개수

number of subsets

"그냥 부분집합이라고 하면 자기자신도 포함이 되요"

" A proper subset of a set B is a subset of B that is not equal to B "

진부분집합은 부분집합들 중에서 자기자신을 제외한 부분집합을 말합니다. 따라서 일반적으로 부분집합이라고 말하면 자기자신을 포함하게 되지요.

부분집합의 개수를 구하는 유형은, 각각의 원소들이 포함되느냐 배제되느냐 하는 논리를 기초로 하기 때문에, 고등수학 과정에서 [경우의 수] 등의 응용문제로 다양하게 출제되고 있습니다.

여기에서는 기본원리 위주로 핵심개념만 설명합니다. 심화과정이 아니라면, 중학생은 생략해도 됩니다.

♧   ♧   ♧   ♧   ♧   ♧

예를 들어, 집합 A = {4, 5} 의 부분집합은 원소가 1개인 {4}, {5} 그리고 자기자신 {4, 5} 와 원소가 하나도 없는 공집합 Ø 의 4개가 있습니다. 공집합 Ø 는 { }로도 표시합니다.

위 예의 집합 A 에서 자기자신 {4, 5}를 제외한 공집합 Ø 과 {4}, {5} 를 집합 A 의 진부분집합이라고 따로 명시합니다.

그러면, 집합 A 의 부분집합의 개수는 어떻게 계산되는 것일까요?

	4  ∉	4 ∈
5  ∉	Ø	{4}
5 ∈	{5}	{4, 5}

즉, 특정원소 하나가 [포함(∈)되거나 또는 배제(∉)되거나] 에 따르는 경우의 수를 구하는 것과 같지요.

따라서, 만일 원소의 개수가 4개라면, 각각의 원소마다 [포함(∈)되거나 또는 배제(∉)되거나]의 2가지 경우의 수를 가지므로, 2 Χ 2 Χ 2 Χ 2 = 16개가 됩니다.

위에서 설명한 원리를 가지고, 문자로 일반화시킨 공식을 만들어 볼까요?

───────────────────────────────────────── 

원소가 n 개인 집합의 부분집합의 개수는

[포함 또는 배제]라는 2가지 경우의 수로 n 번 곱해지는 것이니까,

2ⁿ 개

───────────────────────────────────────── 

이제 약간 응용된 예를 한번 볼까요?

───────────────────────────── 

 집합 X 가 {3, 4, 5, 6, 7}의 부분집합이고

 {2, 3, 4, 5} ∩ X = {3, 4}를 만족할 때

 서로 다른 집합 X 의 개수를 구하여라.

───────────────────────────── 

(1) {3, 4, 5, 6, 7}의 부분집합이면서 원소 3, 4는 포함하고

     원소 5 는 포함하지 않는다는 얘기구나…

(2) 그러면 [포함(∈)되거나 또는 배제(∉)되거나] 의 경우의 수에서

     원소 3, 4, 5는 한가지 경우만 가능하고,

     원소 6, 7은 둘 다 가능하다는 얘기네…

(3) 따라서, 부분집합 X 의 개수는 2^{(5 - 3)} =  2² = 4 개

다음은 조금 어렵지만, 상위의 심화수학으로 갈수록 복층식 개념구조를 익혀 둘 필요가 있다는 점에서, 멱집합(power set)을 알아 보도록 하지요.

예를 들어, 집합 A = {4, 5} 에 대하여, 집합 A 의 멱집합은 A 의 부분집합들을 원소로 갖는 집합으로, P(A) 또는 2^A 으로 표시합니다.

즉, P(A) = {Ø, {4}, {5}, {4, 5}} 또는 {{ }, {4}, {5}, {4, 5}} 라고 나타낼 수 있지요.

따라서, 집합 A 의 멱집합의 부분집합의 개수는 2⁴ = 16 개가 됩니다.

일반화시켜서, 원소가 n 개인 집합의 멱집합의 부분집합의 개수를 알아 볼까요?

───────────────────────────────────────── 

 (1) 원소가 n 개인 집합 { b₁, b₂, b₃, … ,b_n } 의 부분집합의 개수는 2ⁿ 개.

 (2) 즉, 멱집합의 원소의 개수가 2ⁿ 이니까, 멱집합의 부분집합의 개수는

        2^(2ⁿ) 개가 됩니다.

 (3) 이해가 조금 힘들면, 2ⁿ = K 라고 치환하면 이해하기가 쉬워집니다.

       치환을 능숙하게 이용하면, 수학실력도 크게 늘고, 계산능력도 아주 좋아지지요.

 (4) 이제, 멱집합의 원소의 개수 = 2ⁿ = K 라 놓으면, 멱집합의 부분집합의 개수는

         2^k  즉, 2^(2ⁿ) 개가 되지요.

─────────────────────────────────────────

이제, 확인문제를 하나 풀어 볼까요?

───────────────────────────── 

 집합 A = {4, 5} 의 멱집합의 부분집합을

 순서대로 모두 나열하여라.

─────────────────────────────