组合数公式

大家好，又见面了，我是你们的朋友全栈君。

排列组合：

排列推导：

很好证明，将定义式子写出来后合并分数即可.

二项式定理：

证明可以利用上面的推导做归纳。

多重集的排列数

定义：

多重集是包含重复元素的广义集合。

而多重集的排列数又称为 多重组合数 。

性质：

设 \(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\) 个元素组成一个多重集的方案数.

这样的话就限制了每种元素取的个数，把这个问题转化成带限制的线性方程：

我们利用容斥原理去解决，模型如下：

1. 全集：\(\sum_{i=1}^k x_i=r\) 的非负整数解

2. 属性：\(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 好了.