组合数学基础知识回顾

1：$x_{1}+x_{2}+x_{3}+......x_{k}=r$x1​+x2​+x3​+......xk​=r的正整数解的个数
这个题目运用隔板法，r里面有r-1个孔隙，插入k-1个隔板，则可以分为k部分，那么答案就$C_{r-1}^{k-1}$Cr−1k−1​
但如果题目要求的是$x_{1}+x_{2}+x_{3}+......x_{k}=r$x1​+x2​+x3​+......xk​=r的非负整数解的个数呢。显然一个空隙就可以插入几个隔板而变的不好计算。
可以令$y_{i}=x_{i}+1$yi​=xi​+1,那么式子转为为了$y_{1}+y_{2}+y_{3}+......y_{k}=r+k$y1​+y2​+y3​+......yk​=r+k的正整数解的个数,那么就答案就是$C_{r+k-1}^{k-1}$Cr+k−1k−1​

2:Pascal公式
$C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}$Cnk​=Cn−1k​+Cn−1k−1​
这个高中老师就证明过了，假设n个球有n-1个白球和1个黑球，求n个球里面选k个球求方案数，假设选了这个黑球，那就是$C_{n-1}^{k-1}$Cn−1k−1​，如果没有选这个黑球那么就是$C_{n-1}^{k}$Cn−1k​，相加即可

这个公式有啥用呢，就是可以在$O(n^{2})$O(n2)里面处理二项式系数

3：二项式定理
$(x+y)^{n}=\sum_{k=0}^{n}C_{n}^{k}*x^{k}*y^{n-k}$(x+y)n=∑k=0n​Cnk​∗xk∗yn−k
高中得时候都是自己死记下来的qwq，现在重温的时候感觉其实自己推出来很简单
$(x+y)^{n}=(x+y)*(x+y).....(x+y)$(x+y)n=(x+y)∗(x+y).....(x+y)即有n个（x+y）相乘，如果有$x^{k}$xk那么就是从n个括号里面选出k个x，其他的括号都是y，那么就是$C_{n}^{k}*x^{k}*y^{n-k}$Cnk​∗xk∗yn−k然后累加即可

如果是多项式系数呢
$(x_{1}+x_{2}+x_{3}......+x_{k})^{n}=\sum\frac{n!}{n_{1}!n_{2}!n_{3}!....n_{k}!}x_{1}^{n_{1}}x_{2}^{n_{2}}.....x_{k}^{n_{k}}$(x1​+x2​+x3​......+xk​)n=∑n1​!n2​!n3​!....nk​!n!​x1n1​​x2n2​​.....xknk​​
其中$（n_{1}+n_{2}....+n_{k}=n）$（n1​+n2​....+nk​=n），这个式子其实也不难理解，因为每一位都有可能从任何一个括号取出，直接让这些系数全排列就行了
可能这个不太好讲，直接看百度百科的解释