[일반] 조합 질문

[익명(220.84)]

nCr=n!/(n-r)!(r)! 이게 항상 자연수 라는 것을 증명 없이 받아들여도 되나요?

[익명(104.28)]

nCr = n개중 r개를 뽑고 그 r개끼리의 순열을 하나로 보는 것 = 우변이라 생각하는게 보통이고 그래도 이해가 안가면 파스칼의 삼각형에 수학적 귀납법을 적용하면 무지성으로 보일 수도 있죠

[수갤러 3(220.81)]

근데 이미 n!/(n-r)!(r)!이 nCr이 된다는걸 증명하기만 하면 자연수가 되는건 nCr의 정의로부터 당연한거라서.

[수갤러 3(220.81)]

엄밀하게 증명하고 싶으면 {1,2,..,n}의 순열의 집합으로부터 {1,2,..,n}의 크기가 r인 부분집합들의 모임으로 가는 함수 phi를 잡아주면 됨. 어떻게 잡냐면, {1,2,..,n}의 순열 f에 대해서, {f(1), f(2), ..., , f(r)}로 보내면 됨. 그러면 이 함수는 전사함수가 되는데, 임의의 크기가 r인 부분집합 S에 대해서 phi(f) = S인 f가 정확히 r! (n-r)!개 있다는걸 보이면 충분함.

[수갤러 2(125.180)]

n=1일때 1C0과 1C1 모두 1로 자연수 n=k일때 kCr은 모두 자연수라고 가정하면 n=k+1일때 r이 0과 k+1일때는 k+1Cr는 1로 자연수고, 아닐때는 k+1Cr = kCr + kC(r-1), 자연수 더하기 자연수이므로 자연수 - dc App