yongk's dev space: 2015

2015년 2월 1일 일요일

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

이항계수 식은 다음과 같다
$\binom{n}{r}+\binom{n}{k-1}=\binom{n+1}{k}$
<<증명>>
좌변을 풀어쓰면 다음과 같다.
$\frac{n!}{(n-k)!k!}+\frac{n!}{(n-(k-1))!(k-1)!}$

분모를 합쳐서 정리하면, 짜잔!
$=\frac{(n-(k-1))n!+kn!}{(n-(k-1))!k!}=\frac{(n+1)!}{((n+1)-k)!k!}=\binom{n+1}{k}$
증명 끝.

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

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

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

가장 많이 본 글

2015년 2월 1일 일요일

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