组合数公式整理
[Warning]:作者在现在粗略看了一下这个东西后发现自己好像有点锅…之前找出来的锅已经fixed了。但是不排除可能还有锅。暑假应该会重写一篇。如果各位有看到错的地方麻烦在评论指出一下…
首先明确一下定义：$C(n,m)$表示的意义是从$m$个数里面取出$n$个数的方案数
一.通项公式
$$C(n,m)=\frac{m!}{n!(m-n)!}$$
二.递推公式
$$C(n,m)=C(m-1,n-1)+C(m,n-1)$$
三.组合数相关问题
1.杨辉三角与二项式定理
好像关于组合数的都有涉及到这个
$$(a+b)^{n}=\sum_{k=0}^{n} C(k,n)*a^{n-k}*b^{k}$$
二项式定理大概就是这个样子
因为一般的杨辉三角是用上面提到的组合数递推公式来算出每一项的系数的，效率$O(n^2)$，如果要快速求$(a+b)^n$的值可以用二项式定理$O(n)$求出
由
$$C(k,n)=\frac{n!}{k!(n-k)!}$$
可以得到
$$C(k,n)=\frac{n-k+1}{k}*C(k-1,n)$$
所以也可以用这个公式来$O(n)$计算出杨辉三角某一行的值
$upd:$
杨辉三角第$n$行的和，其实就是$2^{n-1}$
2.有相同元素的全排列
设有$n$个元素，其中第$i$个元素有$xi$个，总数为$m$，求全排列
全排列数为：$$\frac{m!}{x1!*x2!*…*xn!}$$
证明：
对于$m$个不同的元素，它的全排列个数为$m!$
同理，对于$xi$个不同的元素，它的全排列个数为$xi!$
于是除掉那些相同的排列即可
3.
$$c(n,m)=c(m-n,m)$$
证明：
胡乱证明一下（数学证明我不想写好长啊，所以很不严谨，大家可以跳过下面那一行）
回顾一下开篇说的定义：$C(n,m)$表示的意义是从$m$个数里面取出$n$个数的方案数。这其实等价于在$m$种取出$n-m$个物品然后扔掉的方案数。也就是说，$c(n,m)=c(m-n,m)$
4.
$$C(n,m)*C(r,n)=C(r,m)*C(n-r,m-r)$$
证明：
$C(n,m)=\frac{m!}{n!(m-n)!}$
$C(r,n)=\frac{n!}{r!(n-r)!}$
$C(n,m)*C(r,n)$
$=\frac{m!}{n!(m-n)!}*\frac{n!}{r!(n-r)!}$
$=\frac{m!}{r!(m-r)!}*\frac{(m-r)!}{(m-n)!(n-r)!}$
$=C(r,m)*C(n-r,m-r)$