|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
09/04/25 14:49
아마도 이런거 아닐까요
예를들어 전체집합이 a b c d e 즉 5개의 원소를 가진 집합의 부분집합을 생각해봅시다 그러면 원소개수가 작은거부터 하면 5C0,5C1,5C2,5C3,5C4,5C5 이런식으로 되죠 ? (C는 다들알다시피 컴비네이션 조합 입니다 작은글씨를 못쓰겠네요..) 짝 홀 짝 홀 짝 홀 인데 이걸보면 ( 0개를 짝수개로 보는게 맞는지는 모르겠습니다 ) 5C0=5C5 5C1=5C4 5C2=5C3 짝수인것과 홀수인것이 정확히 반이죠 ^^; 이런식으로하면 원소의 개수가 n개인 것에대해서도 성립할듯 하네요 이해가 안되는 부분이나 잘못된 점이있다면 지적해주세요 ~ㅠ
09/04/25 14:49
음.. 저는 질문이 이해가 잘 안되어서 그런데, 정제를 좀 해주시면 안될려나요;
해피새우님// 까칠하신 것 같네요. 승연님// 그러면 4개일 땐.. 아니 모든 짝수개의 원소를 가진 집합에 대해서는 성립하기 힘들 것 같은데요.. 댓글 달면서 승연양에게 뭐라하는 것 같아서 가슴이 아프긴 합니다만.
09/04/25 14:52
정확히 맞춰보진 않았지만 대강 떠오른게
n이 홀수면 홀수인 것 개수 = nC1+nC3+nC5+...+nCn = (n-1C0+n-1C1) + (n-1C2+n-1C3) + ... + (n-1Cn-1) = 2^(n-1) (n-1개 원소인 집합의 부분집합 수) 짝수인 것 개수 = nC0+nC2+nC4+..+nCn-1 = n-1C0+ (n-1C1+n-1C2)+ (n-1C3+n-1C4) + ... + (n-1Cn-2+n-1Cn-1) =2^(n-1) 짝수일 때도 거의 같은 식이 나오겠네요.
09/04/25 14:52
수학1 이항정리 단원에서 보면
nC0+nC2+nC4+.....=nC1+nc3+....= 2^(n-1) 이란 공식이 있습니다. 이걸 참고하시면 될것 같아요
09/04/25 14:53
일단 집합의 개수를 n이라고 하면 모든 부분집합의 개수는 2^n 입니다. 각 n에 따라 포함될 수도 있고 안될 수도 있는 두 가지의 경우가 존재하기 때문이죠. 일단 k번째 원소가 (1<=k<=n)가 포함될 경우 역시 2가지겠죠. k를 제외한 부분집합을 생각해봤을 때 2^n-1가지의 경우가 있겠네요. 이 경우가 짝수였다면 k를 포함할 경우 홀수가 되고 포함하지 않으면 짝수가 됩니다. 이 경우가 홀수였다면 그 반대겠죠. 애초에 2^n개라는 부분집합의 개수 자체가 하나의 원소에 대해서 포함할 수 있느냐 없느냐에서 나온 것이므로 그 모든 경우를 합하면 짝수와 홀수가 같아지겠네요.
09/04/25 15:29
nC0+nC2+nC4+.....=nC1+nc3+....= 2^(n-1) 에서요
nC0 이 뜻하는 것은 공집합을 말하는거에요.( nC0=1 이라고 정의가 내려져있죠) nC1 이 뜻하는 것은 n개에서 1개를 뽑는 경우의수. 다시 말해, 원소의 갯수가 1인 부분집합의 갯수죠 nC2 이 뜻하는 것은 n개에서 2개를 뽑는 경우의수. 다시 말해, 원소의 갯수가 2인 부분집합의 갯수죠 ... ... nC0+nC2+nC4+.....=nC1+nc3+.... 에서 좌변은 원소의 갯수가 0인 부분집합의 갯수 + 원소의 갯수가 2인 부분집합의 갯수 + .... 즉, 원소의 갯수가 짝수인 부분집합의 갯수입니다.
09/04/25 16:23
이항정리로 간단히 설명이 되긴하는데요..
원래 홀수개의 원소로된부분집합에서 원소를 하나씩 빼거나 더한다는 개념으로 보면 쉬울수도 있습니다.
09/04/25 16:27
MoreThanAir님//
제가 이해를 잘 못해서 그런지 몰라도 설명이 조금 이상한 것 같습니다. 님께서 설명 하신건 어떤 한 원소를 포함하는 부분집합의 갯수와 그렇지 않은 부분집합의 갯수가 같다는 것을 설명 하고 계신것 같습니다.
09/04/25 16:44
천재테란님// 저도 연습장에 안 끄적이고 머리 속으로만 생각해서 좀 산만한 얘기가 된 것 같네요. 일단 induction으로 증명을 하면 어떨까 싶습니다.
집합상의 모든 element는 편의를 위해 1이라고 가정하겠습니다. (basis step ) n=1인 경우 부분집합의 수=2^1=2 , 1
짝수인 것과 홀수인 것이 모두 1개씩이므로 명제를 만족하네요. (inductive step) n=k일 때 짝수와 홀수의 개수가 같다고 가정을 하면 부분집합의 수=2^k이고 각각 짝수와 홀수의 부분집합은 2^(k-1)개씩이 됩니다. n=k+1일때 부분집합의 수=2^(k+1) k+1이 없는 부분 집합에서 짝수와 홀수의 개수가 같다고 가정을 했으므로 o1,o2,o3,...,oa e1,e2,e3,...,ea 여기서 각 o1~oa, e1~ea에서 k+1번째 원소가 들어간 경우와 아닌 경우를 생각하면 각각 2가지씩 나오죠. 그래서 전체 개수는 2X2^k= 2^(k+1)이 됩니다. n=k에서의 부분집합이 짝수 홀수의 수가 같다고 가정을 했을 때 n=k+1인 경우에도 여전히 짝수와 홀수의 수가 같네요. 따라서 n은 자연수일 때 언제나 성립하는 명제입니다. 뭔가 오류가 있나요...?;
09/04/25 20:46
MoreThanAir님//
오류 없습니다. 처음 댓글 보고 induction 인거 같기도 했는데 생략된 부분이 있어서 그렇게 생각 했던 겁니다^^
09/04/25 20:51
천재테란님// 네 말씀을 듣고 보니 처음 적은걸로는 가정 부분이 빠져있어서 그렇게 생각하시는게 당연한거군요.
증명은 정확성이 생명인데 명확하지 않게 끄적인 제 불찰입니다. ^^;
|
||||||||||