[보충] 이항정리, 중복순열을 이용하여 부분집합의 개수 구하기

내용 

 부분집합의 개수 을 구하는 방법을 이항정리와 중복순열의 아이디어로 해결하는 방법을 배웁니다.

부분집합의 개수

 집합 의 부분집합의 개수는 개 인 것은 당연하죠? 그것을 해석하는 방법입니다.

1. 이항정리를 이용하여 해석하기

 이항정리를 이용하여 해석하는 방법은 집합 에서 부분집합의 원소의 개수에 따라 분류 합니다. 전체는 부분의 합이라는 아이디어입니다.

부분집합의 원소가 없는 경우

부분집합의 원소가 1개 있는 경우

부분집합의 원소가 2개 있는 경우

부분집합의 원소가 개 있는 경우

이므로 

이므로 총 부분집합의 개수는

 가 됩니다.

2. 중복순열을 이용하기

 이른바 디지털 또는 돼지털 방식이라고 할 수 있는데요. 집합 의 원소가 부분집합에 포함이 되면 1, 포함이 되지 않으면 0으로 생각한다면  1과 0을 번 배열하는 것이니까  이 됩니다.