이항계수 증명(pascal's rule)과 프로그래밍

이항계수 식은 다음과 같다

<<증명>>
좌변을 풀어쓰면 다음과 같다.


분모를 합쳐서 정리하면, 짜잔!

증명 끝.

이항계수를 프로그램 하면 다음과 같다.

int bino(int n, int r) {
  if (r == 0 || n == r)) return 1;
  return bino(n-1, r-1) + bino(n-1, r);
}

물론 메모이제이션을 하는 것이 효과적이다.