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

부분집합의 개수

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 = 2⁴ = 16 개가 됩니다.

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

---

원소가n 개인 집합의 부분집합의 개수는, 각각의 원소마다 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 의 2 가지 경우를 갖게 된다. 따라서, 2 가 n 번 곱해지는 것과 같으니까, 2ⁿ 개.

---

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

---

집합 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 의 개수는 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 개가 됩니다. 연습 삼아서, 모두 순서대로 나열해 보도록 할까요? 조금 어렵게 느껴진다면, 멱집합의 원소가 되는 {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 = { b₁, b₂, … b_n} 의 부분집합의 개수는 2ⁿ 개 이니까, 멱집합의 원소의 개수도 2ⁿ 개 이겠지요?

여기서, 더 쉽게 이해할 수 있도록 2ⁿ = k 라고 치환하도록 할까요?

이제, 멱집합의 원소의 개수가 k 개 이니까, 위에서 배웠던 대로, 멱집합의 부분집합의 개수는 2^k 개가 됩니다.

따라서, 멱집합의 부분집합의 개수는 2^k = (2)^(2ⁿ) 개가 됩니다.

집합(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} 의 멱집합의 부분집합을

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

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