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