<문제>

집합A={a1,a2,a3,a4,a5}에서 a1,a2가 들어있는 부분집합의 개수를 구하여라.


<해설>

(원문 링크)


a1,a2를 포함하는 부분집합의 갯수가 [a3,a4,a5]의 부분집합갯수와 같다는것은

a1,a2는 이미 포함되어있다고 확정이 되어있으니깐 생각할 필요가 없는거예요.

그러니깐 문제에서 요구하는 모든 부분집합들에게는 a1,a2는 무조건적으로 들어가있으므로

생략을 해주고 [a3,a4,a5]의 부분집합 갯수만 구하면 된다는 것이죠.

 

문제에서 구하고자 하는 부분집합 몇개만 살펴보자면,

전체집합=[a1,a2,a3,a4,a5]

 

[a3,a4,a5]에서의 부분집합(몇개만 보여드릴께요.)

(공집합)의 경우 = [a1,a2]

[a3]의 경우 = [a1,a2,a3]

[a4]의 경우 = [a1,a2,a4]

[a5]의 경우 = [a1,a2,a5]

[a3,a4]의 경우 = [a1,a2,a3,a4]

[a3,a5]의 경우 =[a1,a2,a3,a5]

      .

      .

      .

이런식으로 모든 부분집합에 a1,a2가 포함이 되므로

a1,a2를 생략하고 [a3,a4,a5]의 부분집합 갯수만 구한 것입니다.

따라서, 전체집합의 갯수가 5개이므로 구하고자하는 부분집합의 갯수는 a1,a2를 제외한

입니다.

 

부분집합을 구하는 공식 = 이 되는 이유는

원소 하나당 속할수있는 경우의 수가 2가지이기때문입니다.

 

위의문제를 예로 들었을때, 모든 부분집합의 경우에서 a1이라는 원소가

부분집합에 속하고 속하지 않을 경우의 수는 2입니다.('속한다'와 '속하지 않는다')

모든 원소가 부분집합에 속하고 속하지 않을 경우의 수를 가지므로(a1=2가지, a2=2가지...이런식으로)

전체집합에서의 부분집합 갯수는

(개)가 됩니다.




<좀더 쉬운 해설>

(원문 링크)


간단한 예를 생각하면 쉽답니다.ㅋ

 

{1,2,3}에서, 1을 포함한 부분집합은

(중괄호 없이 쓸께요.ㅋ)

1  1,2  1,3  1,2,3 이 있답니다.ㅋ


그런데 잘 생각해보신다면..

1을 일단 빼놓은 {2,3}에서 부분집합을 전부 구해보세요

그러면

공집합 2 3 2,3 이 있답니다.ㅋ

여기에다가 1을 각각 집어넣는 거죠


그러면

1 1,2 1,3 1,2,3 이 되서 위의 결과와 같아지는 거랍니다~


도움이 되었길 바래요.ㅎㅎ



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by 앙돌이 트랙백 0 : 댓글 0

티스토리 툴바