Pascal's triangle (파스칼의 삼각형)

// Pascal's triangle

---

   What is Pascal's triangle?   

 

  좌측의 수식과 같은 이항계수의 값을 구할 때 사용할 수 있다. 하지만 아래 설명을 보면 알 수 있듯 점화식을 활용한 Dynamic Programming의 알고리즘을 사용하는 형태로, n의 값이 상당히 커진다면 사용하기 곤란한 알고리즘이다. 

  n의 값이 상당히 커졌을 경우에는 Lucas Theorem (뤼카의 정리) 를 사용하면 된다.

---

   Explanation   

파스칼의 삼각형

이항계수 성질

  위 파스칼의 삼각형을 나타낸 피라미드 모양의 그림에 연두색 값들은, 위에 있는 두 블록의 값의 합과 같다. 또한 양 변들은 nC0, nCn 이 되므로 값이 1이 된다. 이는 이항계수의 성질로서 증명이 된다.

 

  Dynamic Programming으로 C[n][k] 와 같은 벡터에 값을 미리 할당해두면 편할 것이다.