Pascal Triangle: 이항계수

Pascal Triangle, 파스칼 삼각형, 이항계수

정의

Pascal Triangle 은 각 원소가 위 두 원소의 합인 삼각형. 행 n, 열 k 의 원소가 이항계수 $\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}$.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

계산

vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}

O(N²) 공간/시간.

성질

• 행 합: ${\sum }_k\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}=2^n$
• hockey stick: ${\sum }_{\{}i=r{\}}^{\{}n\}(\genfrac{}{}{0ex}{}{\{}{i})\}\{r\}=\left(\genfrac{}{}{0ex}{}{\{}{n}\right)+1\}\{r+1\}$
• Catalan: $C_n=\left(\genfrac{}{}{0ex}{}{\{}{2}\right)n\}\{n\}-(\genfrac{}{}{0ex}{}{\{}{2})n\}\{n+1\}$
• Lucas’ Theorem: mod p 이항계수 계산

참고

• 조합론
• Catalan Number
• Inclusion-Exclusion