(2n-1)Cn
nH0 + nH1 + ... + nH(n-1) = (n-1)C0 + nC1 + (n+1)C2 + ... + (2n-2)C(n-1) = (2n-1)C(n-1)
n번째 숫자가 1+m 이라고 하면, (첫 번째 숫자 - 1), (두 번째 숫자 - 첫 번째 숫자), ... 에서 m 개를 뽑는 경우의 수가 되므로 nHm
혹시 nC0 + (n+1)C1 + ... + (n+m)Cm = (n+m+1)Cm 을 안 배웠다면, 이렇게 생각하면 됨:
n+m+1개중 n+1 개를 뽑는 경우,
마지막 n+1개째가 앞에서부터 n+1번째인 경우의 수는 nCn
마지막 n+1개째가 앞에서부터 n+2번째인 경우의 수는 (n+1)Cn
마지막 n+1개째가 앞에서부터 n+2번째인 경우의 수는 (n+2)Cn
...
마지막 n+1개째가 앞에서부터 n+m+1번째인 경우의 수는 (n+m)Cn
따라서 nCn + (n+1)Cn + ... + (n+m)Cn = (n+m+1)C(n+1)