我们通常使用$\binom{n}{r} $ 表示 $C_{n}^{r}$，在下面都会使用 $\binom{n}{r} $ 来描述组合数。
下面给出两种最常见计算组合数计算方法，需要配合逆元食用。
- 组合数计算公式：$ \binom{n}{r} = \frac{n!}{r!(n-r)!} $
- 组合数递推公式：$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} $
下面是对于组合数应用的一些公式和性质：
- 对称性：$ \binom{n}{r} = \binom{n}{n-r} $
- 二项式定理：$(x+y) ^n = \sum\limits_{r=0}^n \binom{n}{r}x^{n-r}y^r$
- 替换定理：$k\binom{n}{r} = n\binom{n-1}{k-1}$ （常使用在组合数求和式化简）
- 组合数求和式：$ \sum\limits_{r=0} ^n \binom{n}{r} = 2^{n} $
- 等差数列合组合数求和式：$\sum\limits_{r=0} ^n r \binom{n}{r} = n 2^{n-1}$
- 等比数列合组合数求和式：$\sum\limits_{r=0} ^n r^2 \binom{n}{r} = n(n+1) 2^{n-2} $
- 组合数平方求和式：$\sum\limits_{r=0} ^n \binom{n}{r}^2 = \binom{2n}{n}$
接下来是一个关于组合数的简单方法——隔板法。
- 求$x_1 + x_2 +...+x_n = m $正整数解的个数。
- 考虑到有$m$个小球被$n-1$块板割成不为空的$n$份的方案数。
- 由于有$m-1$个空，相当于$m-1$个空里插入$n-1$个隔板的方案数。
- 即$\binom{m-1}{n-1}$
- 求$x_1 + x_2 +...+x_n = m $非负整数解的个数。
- 考虑强制每一个$x_i$初始值为$1$ ,然后再使用上述的正整数解的隔板法。
- 转化为$m+n$个小球被$n-1$块板割成不为空的$n$份的方案数。
- 即$\binom{n+m-1}{n-1}$
接下来是一个非常经典的问题：错排列问题。
- 有$n$本书，按照一个原始排列存放，$f(n)$表示重新排列后每一本书都不在自己原来位置的排列总数。
- 考虑dp，使用$f(i)$表示答案。
- 将第$i$本书放在$[1,i-1]$的位置$j$上 。对$j$的位置分类：
- 如果$j$放在$i$的位置上，就是$i-2$个数的错排问题了。
- 如果$j$不在$i$的位置上，就是$i-1$个数的错排问题了。
- 于是答案就是： $f(i) = (i-1) (f(i-1)+f(i-2))$
组合排列和组合数 学习笔记
原文：https://www.cnblogs.com/ljc20020730/p/11302718.html
