4. number of subsets

부분집합의 개수

number of subsets

"각 원소의 포함과 배제의 경우로

생각하면 아주 쉬워요"

" count the outcomes whether each element is

included or excluded "

부분집합의 개수를 구하는 유형은, 고 1 에서의 [집합] 단원 뿐만 아니라, 중고등 수학 전반에서 [경우의 수] 등의 응용문제로 다양하게 출제되고 있습니다.

따라서, 기본적인 개념과 '포함과 배제의 원리' 는 철저하게 이해해 두는 것이 필요합니다.

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

♧   ♧   ♧   ♧   ♧   ♧

스마트폰에서 수학 수식을 보시려면, 왼쪽 버튼을 누른 후

[데스크톱 보기] 를 설정하세요.

You can read math equations,

by selecting [desktop view] on the mobile.

♧   ♧   ♧   ♧   ♧   ♧

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

Subsets of A = {4, 5} are (a) the empty set Ø with zero elements, (b) the sets {4} and {5} with one element, and (c) the whole set, i.e., A = {4, 5} itself.

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

Proper subsets should be smaller than the original set. Therefore, the number of proper subsets is always one less than the number of subsets because we have to exclude the original set itself.

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

Then, how can we figure out the number of subsets of, for instance, A?

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

위의 표에서 보는 것과 같이, 특정 원소 하나가 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 를 구분하는 데에 따르는, 경우의 수를 구하는 것과 같습니다.

The logic behind how to find the number of subsets is to count the outcomes of whether each element will be included or not, as you see on the table above.

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

For example, if a set has 4 elements, then the number of subsets will be 2⁴ = 16 because each element can be included or excluded.

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

Let's make a formula, by summarizing what we have learned on the above.

---

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

If a set has n elements, then the number of subsets is 2ⁿ, because each element has two options that it can be included or not.

---

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

Let's try to solve a little bit twisted example.

---

집합 X 가 {3, 4, 5, 6, 7} 의 부분집합이고 {2, 3, 4, 5} ∩ X = {3, 4} 를 만족할 때, 서로 다른 집합 X 의 개수를 구하여라.

Let X be a subset of {3, 4, 5, 6, 7}. How many different X's are there if X satisfies the condition, {2, 3, 4, 5} ∩ X = {3, 4} ?

---

(1) 집합 X 가 {3, 4, 5, 6, 7} 의 부분집합이면서, 원소 3, 4 는 포함하고, 원소 5 는 포함하지 않는다는 뜻이지요?

The condition {2, 3, 4, 5} ∩ X = {3, 4} means that the subset X has elements 3 and 4, but doesn't have 5.

(2) 즉, 원소 6, 7 은 '포함(∈) 되거나' 또는 '배제(∉) 되거나' 의 경우의 선택이 가능하지만, 원소 3, 4, 5 의 경우는 이미 한가지 경우로만 정해져 버렸다는 뜻이 됩니다. 따라서, 부분집합 X 의 개수는 2^5-3 = 2² = 4 개

In other words, elements 6 and 7 have the option to be included or not, whereas 3, 4 and 5 doesn't have. Therefore, the number of different set X's is 2^5-3 = 2² = 4.

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

Next, we're going to study more complex concept - [power set], which has a kind of multiplex or fractal dimension structure.

예를 들어, 집합 A = {4, 5} 에 대하여, 집합 A 의 멱집합은 A 의 부분집합들을 원소로 갖는 집합으로, P(A) 또는 2^A 으로 표시합니다. 즉, P(A) = {Ø, {4}, {5}, {4, 5}} 또는 {{ }, {4}, {5}, {4, 5}} 라고 나타낼 수 있지요.

A power set is a set of all subsets. For example, the power set of  A = {4, 5} is {Ø, {4}, {5}, {4, 5}}, which is denoted by P(A) or 2^A.

예를 들면, 위의 집합 A 의 멱집합의 부분집합의 개수는 2⁴ = 16 개가 됩니다. 연습 삼아서, 모두 순서대로 나열해 보도록 할까요? 조금 어렵게 느껴진다면, 멱집합의 원소가 되는 {4, 5} = b 와 같이 치환하면 쉬워집니다.

The number of subsets of the power set of A = {4, 5} will be 2⁴ = 16 because the power set has 4 elements. As an example, the subsets of 2^A can be listed in ascending order as follows :

Ø = {  }

{Ø},   {{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 개인 집합의 멱집합의 부분집합의 개수를 알아 볼까요?

What will be the number of subsets of the power set of a set B which has n elements?

원소가 n 개인 집합 B = \(\{ {b_1},{\rm{ }}{b_2},{\rm{ }}{b_3}, \cdots ,{\rm{ }}{b_n}\} \) 의 부분집합의 개수는 2ⁿ 개 이니까, 멱집합의 원소의 개수도 2ⁿ 개 이겠지요?

The number of subsets of a set B is equal to the number of elements in the power set of B, and therefore, the number equals 2ⁿ.

여기서, 더 쉽게 이해할 수 있도록 2ⁿ = k 라고 치환하도록 할까요? 이제, 멱집합의 원소의 개수가 k 개 이니까, 위에서 배웠던 대로, 멱집합의 부분집합의 개수는 2^k 개가 됩니다. 따라서, 멱집합의 부분집합의 개수는 \({2^{{2^n}}}\) 개가 됩니다.

To make it easier to understand, let's substitute 2ⁿ = k. Then, the number of elements of the power set 2^B is equal to 2^k. Accordingly, the number of subsets of the power set will be \({2^{{2^n}}}\).