(집합) 부분 집합의 개수 공식

(집합) 부분 집합의 개수 공식 유도

 

 

고등학교 1학년 수학의 첫 단원인 집합에는 부분집합의 개수에 관한 내용이 나옵니다.

원소가 n개인 집합의 부분집합의 총 개수는 2ⁿ개로 주어지는데요.

비록 간단한 공식이지만 어떻게해서 이와같은 공식이 얻어지는 지 궁금해할 학생이 있을 것 같아서 정리해보겠습니다.

 

i) 부분집합과 진부분집합

부분집합이란, 집합의 포함관계가 A⊂B일 때 집합 A를 집합 B의 부분집합이라 합니다. 즉 A의 모든 원소가 B에도 포함될 때 부분집합의 관계가 성립합니다. 이 때 B 자기 자신과 공집합 역시 집합 B의 부분집합의 범위에 포함되는데요. 진부분집합(眞部分集合)이란 부분집합은 부분집합이되 자기 자신이 아닌 부분집합을 이르는 용어입니다. 즉 진짜(眞) 부분집합으로 이해하시면 됩니다.

 

예를 들어 집합 B={1, 2, 3}의 부분집합은

{ }, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}으로 총 여덟 개,

진부분집합은 이 중 {1, 2, 3}을 제외한 총 일곱 개입니다.

 

i) 부분집합과 진부분집합의 개수

이제 집합B의 원소의 개수가 n일때, 부분집합의 개수는2ⁿ개로 주어지는 이유에 대해 알아봅시다.

임의로 B={a1, a2, a3, ... an}으로 둡시다. 우선 가능한 부분집합을 빈 공간 { }으로 보면, 여기에 각 원소를 넣을 것인 지, 넣지 않을 것인 지를 판단할 수 있습니다. 즉 n개의 모든 원소에 대해 부분집합을 꾸릴 수 있는 총 경우의 수는, 각 원소들을 포함 시킬것이냐, 제외시킬 것이냐 두 가지의 경우의 수를 각각 곱해줌으로써 구할 수 있습니다.

 

예를들어 저 빈 공간에 a1, a2, ... an이 모두 포함되지 않는다면 (모두 제외) 부분집합은 공집합이 될 것이고, 모두 포함시킨다면 부분집합은 n개의 원소가 모두 포함된 자기 자신으로 나올 것입니다. 한편, 한 원소 a1만 포함시키고 나머지 원소들은 포함시키지 않는 경우엔 부분집합이 {a1}으로 얻어집니다. 이런 식으로하면 가능한 모든 부분집합의 개수를 셀 수 있습니다.

 

따라서 a1에 대해 포함/불포함 2가지, a2에 대해 포함/불포함 2가지, ... an에 대해 포함/불포함 2가지를 모두 곱한 2ⁿ이 총 부분집합의 가지수가 되는 것입니다.

 

 

 

한편, 진부분집합의 개수는 위에서 구한 모든 부분집합의 개수에서 자기 자신 하나만 제외시키면 되므로 2ⁿ-1개가 됩니다.

 

iii) 특정 원소를 포함/불포함하는 부분집합의 개수

예를들어 B={1, 2, 3, 4, 5}에 대해 원소 1과 2를 항상 포함하는 부분집합의 개수를 묻는 문제가 있다고 합시다. 그것들을 나열해보면,

{1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 2, 3, 4, 5}

 

위와같이 총 여덟개의 부분집합을 생각할 수 있습니다. 위에 나열된 부분집합들은, 원소 1과 2가 기본적으로 포함된 주머니에다가 나머지 원소인 3, 4, 5를 포함시킬것인지 말것인지를 판단함으로써 얻을 수 있습니다. 즉 예로 든 문제는 결국 {3, 4, 5}의 부분집합의 개수를 구하는 것과 마찬가지 방식으로 풀 수 있습니다. (2³=8개)

 

특정 원소를 포함하는 부분집합의 개수를 묻는 문제는, 사실 부분집합의 개수를 세는 원리만 잘 이해하고 있으면 어렵지 않게 접근할 수 있습니다. 즉 앞의 설명처럼 초기조건(default)으로 빈 공간 대신 특정 원소를 배정한 후, 나머지 원소들을 가지고 포함/불포함을 따지면 가능한 모든 경우의 수를 구할 수 있습니다.

 

특정 원소를 포함하지 않는 부분집합의 개수도 마찬가지입니다. 원래의 부분집합의 개수를 세듯이 빈 괄호 { }를 생각하고, 특정원소를 제외한 나머지 원소들로 포함/불포함을 따지면 구할 수 있습니다. 이를테면 위의 예 B={1, 2, 3, 4, 5}에서 원소 1과 2를 포함하지 않는 부분집합의 개수는 빈 괄호 { }에 1과 2를 제외한 나머지 원소 3, 4, 5를 포함시킬것인지 시키지 않을것인지를 따지면 됩니다. (2x2x2=8개)

 

끝//