부분집합의 개수
<br>
(1)집합 A의 원소의 개수가n개일 때, A의 부분집합의 개수
<br>
<br>
n개 2x2x...x2(개)
<br>
<br>
(2)r개의 특정한 원소를 갖는 집합 A의 부분집합의 개수
<br>
<br>
n-r개 2x2x...x2(개)
<br>
<br>
이게 도대체 뭔말인지 ㅡㅡ; 좀 가르쳐주세요.
<br>
<!-- -->
첫댓글적어도 이것만은 꼭 외워야 할것. 부분집합의 개수는 2ⁿ 입니다. 왜 그런지 설명해볼까요.? A의 원소가 1,2,3이 있는데, 부분집합을 만들어봐요. 1은 부분집합에 속할수도 있고, 속하지 않을수도 있어서 2가지 입니다. 2 역시, 3도 마찬가지로 속할수고 있고 속하지 않을수도 있어요.
흠.. 이해가 안가신다면 관점을 변환해서 생각해보죠. 100원짜리 동전 3개를 던졌는데요, 총 몇가지 경우가 나올까요? 첫번째 동전은 앞뒷면 둘중에 하나를 취할수 있어요. 두번째 동전역시 앞면 아니면 뒷면,, 그런식으로, 부분집합에 있어서, 자기 자신을 부분집합으로 갖는다는 말은 동전 세개가 모두 앞면인 경우에요
2번.. 특정한 원소가 몇개라고 하면,, 그 몇개는 ×2 가 될수 없고 ×1 이 여야 합니다. 100원짜리를 던져서 꼭 앞면이 나와야 하기때문에.. 꼭 ×2 가 아니라 ×1 인거죠. 원소가 5개인 집합에서 한 원소를 꼭 가져야 한다면, 이미 그 원소는 선택되어서 ×1 이고, 나머지 선택권은 4개의 원소에만 주어졌죠.
첫댓글 적어도 이것만은 꼭 외워야 할것. 부분집합의 개수는 2ⁿ 입니다. 왜 그런지 설명해볼까요.? A의 원소가 1,2,3이 있는데, 부분집합을 만들어봐요. 1은 부분집합에 속할수도 있고, 속하지 않을수도 있어서 2가지 입니다. 2 역시, 3도 마찬가지로 속할수고 있고 속하지 않을수도 있어요.
흠.. 이해가 안가신다면 관점을 변환해서 생각해보죠. 100원짜리 동전 3개를 던졌는데요, 총 몇가지 경우가 나올까요? 첫번째 동전은 앞뒷면 둘중에 하나를 취할수 있어요. 두번째 동전역시 앞면 아니면 뒷면,, 그런식으로, 부분집합에 있어서, 자기 자신을 부분집합으로 갖는다는 말은 동전 세개가 모두 앞면인 경우에요
반대로, 모든 부분집합은 공집합을 원소로 갖는 다는 말은 즉, 동전 세개가 모두 뒷면인 경우에요.
동전 하나가 늘때마다, 앞면 혹은 뒷면을 취할수 있는게 늘어나서 ×2가 하나씩 늘어나요. 동전이 집합으로 따지면 하나의 원소인 셈이죠. 만약 동전 3개가 있다면, 원소가 3개 여서 ×2가 3개 그래서 2³ 이 되는거에요.
1번.. 원소의 개수가 n개 라면 (동전이 n 개 라면) ×2 역시 n번 있어서 2ⁿ
2번.. 특정한 원소가 몇개라고 하면,, 그 몇개는 ×2 가 될수 없고 ×1 이 여야 합니다. 100원짜리를 던져서 꼭 앞면이 나와야 하기때문에.. 꼭 ×2 가 아니라 ×1 인거죠. 원소가 5개인 집합에서 한 원소를 꼭 가져야 한다면, 이미 그 원소는 선택되어서 ×1 이고, 나머지 선택권은 4개의 원소에만 주어졌죠.
그러면 2⁴ 개 겠죠? 2^n-r 이 답입니다. r은 특정한 몇개의 원소의 개수이고, n은 전체 원소의 개수.
<1> 집합 A = {a1, ..., an} 부분집합의 개수; [{ }; nC0] [{a1}, ..., {an}; nC1] [{a1,a2}, ...{a1,an}, {a2, a3}, ..., {a2,an}, ..., {an-1, an}; nC2] ... [{a1, ..., an}; nCn] --> nC0 + ... + nCn = 2^n