通项公式
\tbinom{n}{m} = \frac{m!}{(m-n)!n!}
递推式
三角递推式(适用于求多个组合数)
\tbinom{n}{m} = \tbinom{n}{m-1} + \tbinom{n-1}{m-1}
c++代码
void initC(int m)
{
// C[m][n] 表示 m中选n个
for (int i = 0; i <= m; i++)
C[i][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= i; j++)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
打表如下
线性递推式(适用于求单个组合数)
\tbinom{n}{m} = \frac{m-n+1}{n} \tbinom{n-1}{m}
c++代码
int C(int m, int n) { // 表示 m中选n个
if (n > m)
return 0;
int ans = 1;
for (int i = 1; i <= n; i++)
ans = 1LL * ans * (m-i+1) / i;
return ans;
}
求和公式
公式一
\sum_{i=n}^m \tbinom{n}{i} = \tbinom{n+1}{m+1}
可结合三角形递推公式理解
以 m=4,n=1 为例
公式二
\sum_{i=0}^n \tbinom{i}{i+k} = \tbinom{n}{n+k+1}
以 k=2,n=2 为例