[일반] 조합식이 항상 자연수임을 증명

[익명(121.136)]

자연수 n에 대해 nCk (k는 0이상 n이하)가 자연수임을 어떻게 보이지
n!/[k!(n-k)!] 이거 ㅇㅇ

물론 n개 중 k개를 선택하는 경우의 수와 같기에 자연수다라는 답 말고 정수론적으로 보이고 싶은데 잘 안 됨...

[익명(223.38)]

연속된 n개의 정수는 항상 n의 배수를 포함합니다

[익명(121.136)]

인터넷 보니 그거 증명을 조합으로 하던데, 혹시 그거 증명을 다른 식으로 어케하는지 암?

[익명(223.39)]

비둘기집의 원리?

[ALTa(tladud123)]

f(n, k) = (k+1)(k+2)×...×(k+n) 이라고 하면 f(n, 0) = n! = 0 (mod n) f(n, 1) = 2×3×...n×(n+1) = 0 (mod n) ... f(n, n-1) = n×(n+1)×...×(2n-1) = 0 (mod n) 따라서 f(n, k) = 0 (mod n) for all k i

[ALTa(tladud123)]

for all k in Z

[ScARfaCE(kayuaao)]

파스칼 삼각형의 성질로도 증명가능할걸

[ScARfaCE(kayuaao)]

https://math.stackexchange.com/questions/11601/proof-that-a-combination-is-an-integer/3152934#3152934

[익명(118.235)]

이 증명만으로는 부족한데.. 분자에 1, 2, ..., r의 배수가 곱해져 있는건 맞는데, 그 배수들이 서로 겹칠 수 있고(분자의 인수 하나가 3의 배수 겸 6의 배수라든가) 이런 경우 저 논리만으로는 약분이 잘 됨을 보장 못하지. 예를 들어 12는 1, 2, 3, 4로 나누어 떨어지지만 4!=24로는 나누어지지 않잖아. - dc App

[익명(211.226)]

파스칼 등식 써서 귀납법으로 해

[익명(121.130)]

ㄹㅇ 윗댓 말대로 파스칼 삼각형으로 귀납법이 개꿀

[익명(lemontiktok)]

르장드르공식