r*nCr=n*(n-1)C(r-1) 두가지로 증명해야하는데
하나는 수식계산인데.. 남은 언어적 증명을 어떻게 해야함?
내가 생각한 접근은
집합 A={a_1,a_2,..,a_n}와 1<=k<=n인 자연수 k에 대하여
a_k을 반드시 포함하는
원소의 개수가 r인 A의 부분집합을 A_k라 정의하면
l A_k l = (n-1)C(r-1) 이므로
ㅣA_1 l +...+ l A_n l = n*(n-1)C(r-1)이 성립한다.
nCr = l A_1 U A_2 U ... U A_n l 이므로
l A_1 U A_2 U ... U A_n l = ( l A_1 l + ... + l A_n l ) / r
임을 보이면 되므로, A_1,..A_n 각각의 경우에 해당하는
집합들에서 중복되는 원소가 r개씩 있음을 밝히면됨.
다시 말해서, n이하의 모든 자연수 i와
xㅌA_i인 임의의 x에 대해
xㅌA_k 를 만족하는 i가 아닌 n이하의 자연수 k가
정확히 r개 있어야 함.
근데 이걸 못보이겠음 너무 복잡해서.
수식으로는 너무간단한데.. 이걸 언어적으로
증명하는 방법이 있는 지 궁금합
- dc official App
n개 중에 r개 뽑고 그 중에서 대표 하나 고르기 vs n개 중에 대표 하나 미리 뽑고 나머지 r-1개 뽑기
아..그냥 개똥쌋는데걍이렇게풀리네; - dc App
근데 n이하의 모든 자연수 i와 xㅌA_i인 임의의 x에 대해 xㅌA_k를 만족하는 i가 아닌 n이하의 자연수 k가 정확히 r개 있으면 저 등식이 성립한다는 참인데 저 등식이 성립하는거로부터 저 정확히r개잇다 결론을 도출하려면 어떻게함? 나열 예시로 계속해보면 맞는거같은데, 어떤 경우에대해 하나는 r-1개잇고 하나는 r+1개잇어서 둘이더해서 r배수되게 상쇄해버려도 등식은 성립하니까 고민임 - dc App
Ai에 속하는 X가 Ak에도 속하려면 k가 X에 있기만 하면 되고 X의 원소가 r개니까 정확히 r개씩 중복됨