집합(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ⁿ) 개가 됩니다.