부분집합의 개수를 구하는 방법을 기억하고 있죠? 부분집합의 개수는 원소의 개수만큼 2를 거듭제곱 하는 거죠.
A = {1, 2, 3, 4, 5}이라면 25 = 32니까 부분집합의 수는 32개네요.
이제 여기서 조금 더 어려운 문제를 풀어보죠. A의 부분집합 중에서 2가 들어있지 않은 부분집합의 개수는 몇 개일까요? 반대로 2를 반드시 포함하는 부분집합의 개수는 몇 개일까요?
특정 원소를 포함하지 않는 부분집합의 개수
A = {1, 2, 3, 4, 5}일 때, 2를 포함하지 않는 부분집합을 구해보죠.
- 원소가 하나도 없는 공집합:
- 원소가 한 개인 부분집합: {1}, {3}, {4}, {5}
- 원소가 두 개인 부분집합: {1, 3}, {1, 4}, {1, 5}, {3, 4}, {3, 5}, {4, 5}
- 원소가 세 개인 부분집합: {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {3, 4, 5}
- 원소가 네 개인 부분집합: {1, 3, 4, 5}
직접 구해봤더니 16개네요.
좀 더 쉬운 방법으로 구해볼까요? A라는 집합에 애초부터 2라는 원소가 없다고 생각해보세요. 그리고 A대신 B라고 이름 붙여볼까요? B = {1, 3, 4, 5}라는 집합이 되겠네요. 이 집합의 부분집합의 개수는 24 = 16, 총 16개네요.
처음부터 2라는 원소를 가지고 있지 않다면 당연히 그 집합의 부분집합에는 2라는 원소가 포함되지 않겠죠. 이 방법을 이용해서 A의 부분집합 중 2를 포함하지 않는 부분집합을 구하면 16개가 나와요.
그럼 A의 부분집합 중 2와 4를 포함하지 않는 부분집합의 개수도 구할 수 있겠네요. 처음부터 2, 4를 포함하고 있지 않다고 생각하면 C = {1, 3, 5}가 되고, 원소의 개수는 세 개, 23 = 8, 8개가 되겠네요.
정리해보면 특정한 원소를 포함하지 않는 부분집합의 개수는 원래 원소 개수에서 특정한 원소 개수를 뺀 만큼 2를 거듭제곱하는 겁니다.
특정 원소를 포함하는 부분집합의 개수
이번에는 반대로 반드시 2를 포함하는 부분집합의 개수를 구해볼까요?
2를 포함하는 부분집합은 2를 포함하지 않는 부분집합에서 구하면 쉬워요. 2를 포함하지 않는 부분집합을 모두 구한 다음에 거기에 2를 집어넣으면 되거든요.
위에서 직접 구해본 부분집합이 있죠. 거기에 전부 다 2를 집어넣어 볼게요.
- 원소가 하나도 없는 공집합: {2}
- 원소가 한 개인 부분집합: {1, 2}, {2, 3}, {2, 4}, {2, 5}
- 원소가 두 개인 부분집합: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}
- 원소가 세 개인 부분집합: {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {2, 3, 4, 5}
- 원소가 네 개인 부분집합: {1, 2, 3, 4, 5}
모든 부분집합이 2를 포함하고 있어서 원소의 개수가 한 개씩 늘었어요. 부분집합의 개수는 총 16개고요.
2를 포함하는 부분집합은 2를 포함하지 않는 부분집합에 원소 2를 집어넣어서 찾았어요. 그렇다면 그 개수는 몇 개일까요? 2를 포함하는 부분집합의 개수와 2를 포함하지 않는 부분집합의 개수는 같아요.
그래서 2를 포함하는 부분집합의 개수는 2를 포함하지 않는 부분집합의 개수를 구하는 것과 똑같은 방법으로 구합니다.
24 = 16 개입니다.
부분집합의 개수 구하기
n(A) = n일 때
집합 A의 부분집합의 개수 = 2n
집합 A의 진부분집합의 개수 = 2n - 1
특정원소 k개를 포함하지 않는 부분집합의 개수 = 2n - k
특정원소 k개를 포함하는 부분집합의 개수 = 2n - k
특정원소 k개 중 적어도 한 개를 포함하는 부분집합의 개수 = 2n - 2n - k
진부분집합은 자기 자신을 제외한 부분집합이니까 전체 부분집합의 개수에서 1을 빼서 구해요.
특정 원소 k개를 포함하지 않는 부분집합은 애초부터 그 원소를 포함하지 않은 집합으로 생각하면 됩니다. 애초부터 원소에 포함되지 않았으면 부분집합에도 포함되지 않으니까요. 또 특정 원소 k개를 포함하는 부분집합은 특정 원소 k개를 포함하지 않는 부분집합에 그 원소들을 넣어주는 것으로 생각하면 쉬워요. 따라서 둘은 개수가 서로 같은 거예요.
마지막에 있는 게 처음으로 나오는 건데요. 적어도 한 개가 들어있는 것의 개수를 바로 구하기 어려우니까 반대로 생각해봤어요. 적어도 한 개를 포함하는 것의 반대는 하나도 들어있지 않은 거잖아요. 그래서 전체에서 한 개도 들어있지 않는 부분집합의 개수를 빼서 구하는 거죠. 하나도 들어있지 않는 부분집합의 개수는 (특정원소 k개를 포함하지 않는 부분집합의 개수)에요.
(특정 원소 k 개중 적어도 하나를 포함하는 부분집합의 개수)
= (전체 부분집합의 개수) - (특정 원소 k개를 포함하지 않는 부분집합의 개수)
집합 A = {1, 2, 3, 4, 5}일 때 다음을 구하여라.
(1) 2, 4를 포함하지 않는 부분집합의 개수
(2) 2, 4를 반드시 포함하는 부분집합의 개수
(3) 2, 4중 적어도 하나를 포함하는 부분집합의 개수
(1) 2, 4를 포함하지 않는 부분집합의 개수를 구하라고 했는데, 애초부터 A라는 집합이 2, 4를 포함하지 않았다고 생각해보죠. 이 집합을 B라고 한다면 B = {1, 3, 5}예요. (B의 부분집합의 개수) = (2, 4를 포함하지 않는 부분집합의 개수)이므로 23 = 8이에요.
공식을 이용해서 바로 구해보면 n(A) = 5이고, 2, 4라는 두 개의 원소를 포함하지 않으니까 25 - 2 = 23 = 8(개)이에요. 공식으로 바로 구해도 같네요.
(2)번은 (1)에서 구한 B의 부분집합에는 2, 4가 들어있지 않으니까 거기에 2, 4를 모두 넣어준다고 생각하면 돼요. 따라서 개수가 같죠. 8개에요.
(3)번 2, 4중 적어도 하나를 포함한다는 건 2를 포함하거나 4를 포함하거나 2, 4 둘 다를 포함하는 거예요. 전체 부분집합의 개수에서 2, 4를 둘 다 포함하지 않는 부분집합의 개수를 빼서 구해요. 25 - 25 - 2 = 32 - 8 = 24(개)
두 집합 A = {x|x는 5 이하의 자연수}, B = {1, 3, 5}일 때 B ⊂ X ⊂ A를 만족하는 X의 개수를 구하여라.
문제가 좀 복잡하네요. A = {1, 2, 3, 4, 5}, B = {1, 3, 5}
B ⊂ X니까 X는 B의 모든 원소를 포함하고 있어요. 그리고 X ⊂ A죠. 정리해보면 X는 B의 원소인 {1, 3, 5}를 포함하는 A의 부분집합이에요.
특정한 원소를 포함하는 부분집합의 개수를 구하는 공식을 사용하면 되겠네요.
25 - 3 = 4
X를 직접 구하는 게 아니라 개수만 구하는 거니까 답은 4개입니다.
헐 감사합니다ㅠㅠㅠ이해안갔던건데 이해가 가네요
원리가 간단하니까 잊어버리지는 않을 거에요.
비밀댓글입니다
특정한 원소를 포함하지 않는 부분집합의 개수 = 특정한 원소를 포함하는 원소의 개수 = 특정한 원소를 뺀 나머지 원소 개수만큼 2를 곱
그러니까 맞게 쓴 거예요. 본문을 한 번 더 읽어보시면 이해가 될 거에요.
프린트하고싶은데 어떻게 해요??
모니터로 보고 공부하기 힘들어서..
재수생인데..
이거보고 후딱 정리하려고ㅠㅎ
그냥 한글파일 인쇄하는 것처럼 메뉴의 파일 - 인쇄 누르시면 돼요.
항상 도움을 많이 받고있어서 고맙습니다~ 왠만한 자습서보다 정리가 잘돼있네요!!!
그래도 자습서와 함께 보셔야해요.
공집합의 경우라서 2를 넣었을 때 2만 나오는 건가요?
네
비밀댓글입니다
이런 오타는 그냥 애교(?)로 넘어가 주세요. ㅋㅋ
비밀댓글입니다
틀린 글자가 있을 때 내용을 고치면 네이버나 다음에서 스팸을 발행하는 블로그로 인식되어서 불이익을 받거든요. 그래서 가급적이면 내용이 틀리거나 중요한 게 빠졌을 때는 글을 수정을 하지만 이해하는데 별 문제가 없는 단순 오타는 수정을 안해요.
제가 고생한 거 알아주셔서 고맙습니다. ㅎㅎ
비밀댓글입니다
적어도 하나의 짝수를 포함하는 집합과 짝수를 하나도 포함하지 않은 집합의 개수를 더하면 부분집합 전체의 개수가 되겠죠?
(적어도 하나의 짝수를 포함하는 부분집합의 수)
= (전체 부분집합의 수) - (짝수가 하나도 없는 부분집합의 수)
부분집합의 개수(http://mathbang.net/286)의 예제를 참고하시면 풀 수 있을 거예요.
특정 원소를 포함한 갯수 중에서여 2를뺀3가지 원소가 더있어요{5.4.3} {5.3.4} {5.1.3}
{5.4.1} 이렇게 4가지는 왜 뺸거죠??
원소가 3개인 부분집합에 있어요.
집합에서 원소의 순서는 중요하지 않아서 원소만 같다면 순서가 달라도 같은 집합이에요.
{3, 4, 5} = {5, 4, 3} = {5, 3, 4}
감사합니다!! 덕분에 쉽게 확 이해했어요ㅎㅎ
확 쉽게 이해하면 확 쉽게 잊어버릴 수 있으니 조심하세요. ㅎㅎ