목록이항계수 (1)
블로그 옮겼습니다
꼭 알아야 하는 이항계수 공식
개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..
Algorithm/Memo &Tips
2017. 5. 23. 08:48