확률과 통계(17)

※본문에는 수식이 사용되었습니다. 모바일에서는 수식이 깨져 보이지 않을 수 있는 점 참고 바랍니다. 만일 수식이 깨져 보일 경우 데스크톱 모드를 사용하여 주시길 부탁드립니다.

---

 집합의 종류에는 부분집합과 진부분집합이라는 것이 있다. 본문에서 원소의 개수가 n인 집합에서 만들 수 있는 부분집합과 진부분집합의 개수에 대해 알아보자.

부분집합의 개수

 어떤 집합 A에 대한 부분집합의 개수는 그 집합 A에 속하는 각 원소가 부분집합을 구성하는 원소가 될 것인가의 여부로 결정할 수 있다. 예시를 통해 알아보자.

예시

\( \left\{ a \text{, } b \text{, } c \right\} \)

 위의 집합은 3개의 원소를 가지는 집합이다. 이 집합의 부분집합을 모두 구해보자.

\( \left\{ X \text{, } X \text{, } X \right\} \)	\( \left\{ X \text{, } X \text{, } O \right\} \)	\( \left\{ X \text{, } O \text{, } X \right\} \)	\( \left\{ X \text{, } O \text{, } O \right\} \)	\( \left\{ O \text{, } X \text{, } X \right\} \)	\( \left\{ O \text{, } X \text{, } O \right\} \)	\( \left\{ O \text{, } O \text{, } X \right\} \)	\( \left\{ O \text{, } O \text{, } O \right\} \)
\( \left\{ \text{  } \right\} \)	\( \left\{ c \right\} \)	\( \left\{ b \right\} \)	\( \left\{ b \text{, } c \right\} \)	\( \left\{ a \right\} \)	\( \left\{ a \text{, } c \right\} \)	\( \left\{ a \text{, } b \right\} \)	\( \left\{ a \text{, } b \text{, } c \right\} \)

이 표의 첫 행은 부분집합에 각 원소가 포함되는지의 여부를 알려주며, 두 번째 행은 그 첫 행의 내용에 따라 나타나는 부분집합을 원소나열법으로 나타낸 것이다. 이 표를 보면 알 수 있겠지만 각 원소의 부분집합 내 존재유무에 따라 나타나는 부분집합이 달라지므로 각 원소가 부분집합에 속할지를 조사하여 부분집합의 개수를 구할 수 있다. 예시로 돌아가 보자. 예시에서 나온 집합에는 a, b, c라는 3가지 원소가 존재한다. 이 세 원소는 각각 부분집합에 속할 수도, 속하지 않을 수도 있다. 다시 말해 부분집합에 a가 속할지, 속하지 않을지, b가 속할지 속하지 않을지, c가 속할지 속하지 않을지를 각 원소에 대해 독립적으로 조사할 수 있다. 그러므로 이 집합의 부분집합의 개수는 \( 2 \times 2 \times 2 = 8 \)이 된다. 자, 이제 n개의 원소를 가지는 집합의 부분집합의 개수를 구해보자.

n개의 원소를 가진 집합의 부분집합의 개수

 이 역시 앞서 예시로 든 집합의 부분집합의 개수를 구할 때와 같이 각 원소가 부분집합의 원소가 될지의 여부를 조사해 부분집합의 개수를 구할 수 있다. 각 원소의 속함 여부를 조사하면 나타나는 경우의 수는

\( \underbrace{ 2 \times 2 \times 2 \times \cdots \times 2 }_{ n \text{개} } = 2^{n} \)

이므로 n개의 원소를 가진 부분집합의 개수는 \( 2^{n} \)이다.

n개의 원소를 가진 집합의 진부분집합의 개수

 n개의 원소를 가진 집합의 부분집합의 개수를 구했으면 당연히 그 집합^[각주:1]의 진부분집합의 개수 또한 구할 수 있다. 어떤 집합 \( A \)의 진부분집합은 그 집합 \( A \)의 부분집합 중 집합 \( A \)와 같은 집합을 제외한 집합을 말한다. 그러므로 원소의 개수가 n개인 집합의 부분집합의 개수가 \( 2^{n} \)이므로 진부분집합의 개수는 \( \left( 2^{n}-1 \right) \)이다.

 

 

 

1%의 영감이 없으면 99%의 노력은 소용이 없다.

-토머스 에디슨

---

1. n개의 원소를 가진 집합 [본문으로]