부분집합의 개수

[부분집합의 개수]

오늘은 부분집합의 개수를 구하는 방법에 대해

알아보도록 하겠습니다.

예시로 원소르 4개 가지는

아래와 같은 집합을 가져와봤습니다.

1,2,3,4 이 네 개의 원소로 이루어진

A라는 집합이 있습니다.

공식을 배우기전에

무식하게 부분집합을 전부 구해보겠습니다.

위와 같이 A의 부분집합은 총 16개가

나오는 것을 확인할 수 있습니다.

매번 이렇게 구할 수 없을 뿐더러

원소의 개수가 5개만 넘어가도

일일이 세기는 어렵기 때문에

좀 더 쉬운 방법을 알아보겠습니다.

원소의 개수가 4개이므로 들어갈 자리가 4곳입니다.

각각의 자리에 원소를 넣는다/안넣는다

두개의 경우의 수가 존재합니다.

예를 들어 전부 안넣는다를 선택하면

공집합이 되는 것이고

넣는다 / 안넣는다 / 안넣는다 / 넣는다를 

선택하는 경우의 수는

{1,4}라는 부분집합이 만들어집니다.

이처럼 2개의 경우의 수가 들어가는 곳이 4곳

2^4으로 16이라는 개수를 얻을 수 있습니다.

일반화 시켜보면

부분집합의 개수는 2를 원소의 개수만큼

곱한 것과 같고 2^n으로 표현할 수 있습니다.

다음 시간에는 특정한 원소를 포할할 때

혹은 포함하지 않을 때의

부분집합의 개수를 알아보도록 하겠습니다.