부분집합의 개수_2

[부분집합의 개수_2]

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

특정 원소를 포함할 때, 포함하지 않을 때르

구하는 것을 알아보도록 하겠습니다.

이전 포스팅에서 부분집합의 개수는

아래 처럼 각각의 자리에 원소를 넣는다/안넣는다

경우의 수를 구하는 것이라고 말씀드렸습니다.

집합 {1,2,3,4} 의 부분집합의 개수는 아래처럼

16개입니다.

그러면 이 중에서 원소 3을 포함하는 부분집합의 개수는

어떻게 구할 수 있을까요?

예상하신 것처럼 3을 넣을자리의 경우의 수를

넣는다 / 안넣는다 2개가 아닌

넣는다 1개로 해주면 됩니다.

조금 응용해봐서 원소 1과 3을 포함한

경우의 수도 구해보도록 하겠습니다.

1과 3이 들어갈 자리의 경우의 수를 1로 바꿔주면

즉 포함해야하는 원소의 개수만큼

2를 곱하는 숫자를 줄여주면 됩니다.

같은 원리로 특정 원소를 포함하지 않을 때도

구하는 방식은 같습니다.

1과 3을 포함하지 않는 부분집합을 구해보면

위와 같이 같은 결과값을 구할 수 있습니다.

포함하지 않는다와 포함한다가 의미는 반대지만

부분집합의 개수 측면에서는 같은 원리로 적용됩니다.

그러면 이것을 공식화 해보겠습니다.

위의 예시로 들었던 집합 {1,2,3,4}에 대입해보면

n = 4

특정원소 1,3을 포함한다고 했을 때

k=2

로 최종 개수를 2^2으로 구할 수 있습니다.