组合数

定义

我们定义 $C_n^m$ 为在 $n$ 个元素中选择 $m$ 个元素的不同的组合方式，即组合数。

性质

1.计算公式：

$$C_n^m=\frac{n!}{m!(n-m)!}  $$

我们记 $A_n^m$ 为在 $n$ 个元素中选 $m$ 个元素的不同的排列方式，即排列数。

我们易得：

$$A_n^m=n(n-1)(n-2)(n-3)…(n-m+1)=\frac{n!}{(n-m)!}$$

则有：

$$C_n^m=\frac{\frac{n!}{(n-m)!}}{m!}=\frac{n!}{m!(n-m)!}$$

不理解可以手推一下。

2.互补性

$$C_n^m=C_n^{n-m}$$

口胡：对于每选出 $m$ 种元素的一种组合，都有剩余没选的 $n-m$ 个元素组成另一种组合。

3.组合数恒等式 

$$C_{n+1}^m=C_n^m+C_n^{m-1}$$

通俗一点翻译过来为：在原先的 $n$ 个元素中多加入一个元素，根据分类加法计数原理，在原先的$C_n^m$下，显然少了含有新元素的情况。若要放进一个新元素，要拿出一个老元素供这个新元素放置， 即加上 $C_n^{m-1}$ 种方案。

求解

对于数据范围较小且在$long long$范围内，直接套公式求即可，但如果需重复计算，这将会浪费大量时间，可以先求出阶乘表，直接调用即可。

当然这里不是要说这个，这里要介绍的是递推求法。

基于组合数恒等式，令 $n=n+1$，那么式子就转化为了

$$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$$

结合数学上的规定：$C_0^i=C_1^1=1$ 和 $C_0^0=0$ 得出递推开始条件。

 $$dp[0][0]=0$$

 $$dp[0][i]=dp[1][1]=1，i \in [1,m]$$

递推式：

$$dp[i][j]=dp[i-1][j]+f[i-1][j-1]$$

有点类似于杨辉三角的递推式，有待继续学习。