大家好，又见面了，我是你们的朋友全栈君。
排列组合：
排列推导：
很好证明，将定义式子写出来后合并分数即可.
二项式定理：
证明可以利用上面的推导做归纳。
多重集的排列数
定义：
多重集是包含重复元素的广义集合。
而多重集的排列数又称为 多重组合数 。
性质：
设 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}\)，表示由 \(n_1\) 个 \(a_1\) …. \(n_k\) 个 \(a_k\) 组成的多重集，则 \(S\) 的全排列个数为：
相当于是把相同元素的排列数除掉了。
具体来说，有 \(k\) 种不一样的球，每种球的个数分别是 \(n_1,n_2,….,n_k\) ,且加和为 \(n\)。
这 \(n\) 个球的全排列数就是 多重集的排列数。
多重集的组合数 \(1\)：
设 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}\)，表示由 \(n_1\) 个 \(a_1\) …. \(n_k\) 个 \(a_k\) 组成的多重集。
那么对于整数 \(r(r < n_i)\) ,从 \(S\) 中选择 \(r\) 个元素组成一个多重集的方案数就是 多重集的组合数 。
这个问题等价于 ：\(x_1+x_2+…+x_k=r\) 的非整数解的数目，可以用插板法解决。答案为：
证明：
因为在这种情况下， \(x_{[1,k]}\) 的数可能为 \(0\) ,我们把每一个 \(x+1\) ,得到了这个式子：
代换意义就是用 \(k-1\) 个挡板，在 \(k+r-1\) 个空隙，将 \(k+r\) 个小球分成 \(k\) 部分。即以上式子。
多重集的组合数 \(2\):
设 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}\)，表示由 \(n_1\) 个 \(a_1\) …. \(n_k\) 个 \(a_k\) 组成的多重集。
对于正整数 \(r(r < n)\) , 求从 \(S\) 中选择 \(r\) 个元素组成一个多重集的方案数.
这样的话就限制了每种元素取的个数，把这个问题转化成带限制的线性方程：
我们利用容斥原理去解决，模型如下：
-
全集：\(\sum_{i=1}^k x_i=r\) 的非负整数解
-
属性：\(x_i\leq n_i\)
设 满足属性 \(i\) 的集合是 \(S_i\) ，\(\overline{S_i}\) 表示不满足属性 \(i\) 的集合，即满足 \(x_i \geq n_i+1\) 的集合，那么答案即为：
根据容斥原理。。。。。 具体在 \(OI-WIKI\) 上都有。
用全集 \(|U|=\binom{r+k-1}{k-1}\) 减去上面式子，得到了多重集的组合数：
其中 \(A\) 是充当枚举子集的作用，满足 \(|A|=p, A_i<A_{i+1}\) 。
不相邻的排列：
定义：
\([1,n]\) 这 \(n\) 个自然数中选 \(k\) 个，这 \(k\) 个数中任何两个数都不相邻的组合有：
错排：
详情见我另外一篇博客：错排
圆排列：
定义：
\(n\) 个人全部来围成一圈，所有的排列数即为 \(Q_n^n\)
分析：
考虑其中已经排好的一圈，从不同位置断开，又变成不同的序列，所以有以下推导：
从这里能推导出 \(n\) 个人其中 \(m\) 个围成一圈的方案数：
组合数性质：
1. 将选出的集合对全集取补集：
2. 递推式：
3. 组合数递推式(和上方相同)
然后一开始初始化是这样的：
c[1][1]=1; for(int i=0;i<=n;i++) c[i][0]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++){
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
这个式子是杨辉三角的公式表达。
4. 二项式定理特殊情况：
5. 二项式定理另一种情况：
6. 拆组合数：
当 \(m=n\) 的时候，则有式子：
剩下的看 OI-WIKI 好了.
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/154644.html原文链接：https://javaforall.net
