집합(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 elements in a set

"중복된 공통부분은 빼주어야지요"

" subtract common elements that were counted twice "

원소의 개수는 집합 단원에서 합집합과 교집합의 혼합된 개념을 잘 이해해야 하는 가장 기본적인 기초적인 개념입니다만,

중 2 와 고 2 의 [경우의 수와 확률] 단원 및 고 1 의 [집합과 명제] 단원을 연계해서 혼합된 현태의 응용문제가 자주 등장하는 개념이기도 합니다.

특히, 심화수준의 문제들에서는, 전체의 경우의 수에서 특정조건을 만족하지 않는 반대의 경우를 빼주는, 여집합의 개념과 함께 해결해야 하는 복잡한 유형도 출제됩니다.

기본개념과 공식 정도는 암기해 두어야, 빠른 시간 내에 쉽게 문제를 해결할 수 있습니다.

♧   ♧   ♧   ♧   ♧   ♧

앞에서, 집합A = {a, b, c} 의 원소의 개수를n (A) = 3 으로 표현한다고 했습니다. 그러면 집합 C = {b, c, e, f} 라 할 때, n (A∪C) 는 어떻게 계산할까요?

집합 사이의 관계를 시각적으로 아주 잘 보여 주는 벤 다이어그램 (Venn diagram) 을 이용해서 알아 보도록 하지요.

 

위 그림에서 보듯이, n(A∪C) 는 단순히 n (A) + n (C) 가 아니라, 중복해서 두 번 더해지는, 빨간색으로 표시된 A∩C = {b, c} 만큼을 다시 빼 주어야 합니다.

n (A∪C)

= n (A) + n (C) – n (A∩C)

= 3 + 4 – 2

= 5

이 원리는 집합의 개수를 늘려나가면 상당히 복잡합니다. 벤 다이어그램에서 집합을 3 개로 확장해서 아래와 같이 그려 보면 되겠죠? 고등수학 과정에서는 3 개의 수준까지는 외워 두어야 됩니다.

이번에도 위 그림에서 보듯이, n (A∪C∪D) 는 단순하게 n (A) + n (C) + n (D) 가 아니라,

(1) 중복해서 두 번 더해진, n (A∩C), n (C∩D) 와 n (D∩A) 를 각각 빼 주어야지요.

(2) 그런데, 이렇게 3 번을 빼주다 보면, A∩C∩D = {b, c} 는 3 번씩이나 빠졌으니까, 다시 한 번은 도로 더해 주어야 합니다.

n (A∪C∪D)

= n (A) + n (C) + n (D)

– n (A∩C) – n (C∩D) – n (D∩A)

+ n (A∩C∩D) 

= 5 + 6 + 5 – 3 – 3 – 3 + 2

= 9

그럼, 공부한 내용을 일반식으로 정리해 볼까요?

---

n (A∪C∪D)

= n (A) + n (C) + n (D)

– n (A∩C) – n (C∩D) – n (D∩A)

+ n (A∩C∩D) 

---

이 개념이 어떻게 활용되는지, 예를 한번 볼까요?

---

100 미만의 자연수 중에서 2 또는 3 또는 5 의 배수인 자연수의 개수를 구하여라.

---

(1) 위에서 정리했던 '합집합 원소의 개수' 의 개념을 확실하게 이해했다면, 그대로 공식을 대입하면 되겠지요?

(2) 교집합의 개념을 이용하면, 2 와 3 의 공배수는 6 의 배수이므로 n (2 ∩ 3) = n (6) 이고, 같은 방법으로 아래의 공배수들이 성립합니다.

n (2 ∩ 5)        =  n (10)

n (3 ∩ 5)        =  n (15)

n (2 ∩ 3 ∩ 5) =  n (30)

(3) 따라서, 이를 대입하여 정리하면,

n (2∪3∪5)

= n (2) + n (3) + n (5)
– n (6) – n (15) – n (10)
+ n (30)

= 49 + 33 +19 – 16 – 6 – 9 + 3

= 73

♧   ♧   ♧   ♧   ♧   ♧

영어번역을 함께 보시려면, 아래의 링크를 눌러주세요.

Please click the following link

to read English translation.

http://jaymathbee.blogspot.kr

♧   ♧   ♧   ♧   ♧   ♧