组合数学相关

正好有空来整理一下关于组合数学相关的知识点

加法原理

加法法则其实就像字面意思一样， 我们对于按照顺序选择的一些事件， 方案数可以直接相加。百度的官方解释是：

设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。其中，事件A和事件B是互斥的。

这个还是很好理解的。
如果我们设A集合的元素个数为|A|，B的元素个数为|B|，那么加法原理的公式表示就是这个样子的：

$$| A ∪ B | = | A | + | B |$$

需要注意的是，加法原理的使用必须满足两个集合中没有重复元素的情况下使用。如果存在重复的元素， 那么必须减去重复计算的元素才能得到正确的数量。

容斥原理

斥容原理可以用公式来表示：

$$| A ∪ B | = | A | + | B | - |A ∩ B |$$

即A的元素个数和B的元素个数相加然后减去重复的元素个数|A ∩ B|

乘法法则

百度的解释：

做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。

如果我们将A集合中的所有元素和B集合中的所有元素组合起来的话， 这时候组合的总数就是两个集合元素的个数相乘的结果。因为A中的每一个元素都有|B|这么多的选择， 所以总的组合数即为|A| × |B|。

公式表示：

$$|A × B| = |A| ×|B|$$

置换

更加复杂的方式，置换又叫做全排列。即从n个数中拿出n个数，按顺序进行排列称为全排列 。

E.g. 三张不一样的扑克牌A, B, C. 按照ABC, ACB, BAC. . . . .等顺序排列，共用多少种排法？

我们可以考虑一共有3个卡槽， 对于第一个卡槽。 我们有3张卡牌可以选择，当第一张牌选择完成以后。 对于每一种情况， 第二个卡槽都还有2张卡牌可以选择， 在第2张牌选择完成之后。第三个卡槽就只剩下一张牌可以选择， 所以排列方案一共有：3 × 2 × 1 种可能性 即 3！

排列

排列就是从一些物品中取出一部分进行排列。 百度百科的解释如下：

排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。

E.g. 现在你需要从5张牌中拿出3张牌来进行排列。 问一共有多少种排列方法

我们还考虑一共有3个卡槽， 这时候我们一共有5张卡片。对于第一个卡槽来说，一共可以有5张卡牌可以选择 。当第一个卡槽选择完成之后， 你还有4张卡牌，这时候第二个卡槽共有4个选择。相似的 ，在第二个卡槽选择完成之后， 第三个卡槽就剩下了3个选择， 所以从5张牌中拿出3张牌来进行排列的方案数为 5×4×3

$$即 ：P^{3}_{5} = 5×4×3 = \frac{n!}{(n-m)!}$$

组合

置换和排列都需要考虑顺序，而组合就是一种不考虑顺序的排列方法

百度定义：

从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。

E.g. 我们现在有5张牌，A，B，C，D，E 。拿出3张进行组合，不考虑他们的顺序，比如ABE 和 BEA 被视作一种组合

我们可以这样考虑。 对于5取3的一种组合ABC在排列中重复出现了ABC, ACB, BAC, BCA, CAB, CBA一共6种情况， 但是在组合数中， 我们只记一次， 所以我们考虑直接求一下5取3的排列总数在除以重复度， 得到的就是5取3的组合数

$$即 C^3_5 = \frac{P^{3}_{5}}{P^{3}_{3}}$$

我们可以把这个公式总结一下， 一般的我们从n个数中取出k个数的组合数为：

$$C^k_m = \frac{P^k_n}{p^k_k}\ \\ = \frac{\frac{n!}{(n-k)!}}{k!}\ \\ = \frac{n!}{(n-k)!} · \frac{1}{k!}\ \\= \frac{n!}{(n-k)!k!}$$

即

$$C^k_n =\frac{n!}{(n-k)!k!}$$

置换 排列 组合 之间的关系

对于组合来说，“组合是不考虑顺序的” 其实也可以理解为“顺序是固定的”，对于从五张牌A，B，C，D，E中拿三张的组合中， 其实就是一定遵循：A，B，C，D，E的顺序

对于排列和置换和组合之间的关系：

我们可以认为排列就是组合乘上重复度，并且重复度其实就是这几个的全排列，那么我们可以知道:

$$P^m_n = C^m_n × P^m_m$$

其实这和组合数的公式的道理是一样的。

几个基本模型

排列例题：

图片来自网络：

组合例题：

图片来自网络：

隔板法

其实隔板法使用来解决形如，有n个没有区别的球，把他们放到k个篮子里， 保证每一个篮子里至少有一个球，求有多少种组合数这样的问题。这时候我们把这些球中想作有n-1个空隙，共有k-1个隔板，将k-1个隔板插入这n-1个空隙中。使之成为k组的方法。这就是隔板法的经典应用。公式如下：

$$答案即为: C^{k-1}_{n-1}$$

变形有：

1.求方程 x+y+z=10的正整数解的个数。 等于10个球， 3个盒子，盒子不能为空

2.把10个相同小球放入3个不同箱子，第一个箱子至少1个，第二个箱子至少3个，第三个箱子可以放空球，有几种情况？ 先把第二个盒子放2个球，第3个盒子里从别的地方拿来一个球，这时候就转换成1个模型，答案就是C(8,2)

3.将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。（减少球数用隔板法） 先将四个盒子中放入0， 1， 2， 3个球，然后变成第一个模型 ，答案就是C(13,3)

相似的，这道题有一些拓展。比如题目要求可以有篮子可以空，这时候我们可以将球的个数加上k个，使之总数成为n+k个，这时候我们把这n+k个分为k个部分就转换成了上面这个相似的问题。只要我们分好组之后再从每一个组中拿走一个球，就是本题的答案了。所以：

$$答案为：C^{k-1}_{n+k-1}$$

变形有：

1.求方程 x+y+z=10的非负整数解的个数。 等于10个球， 3个盒子， 盒子可以为空，答案是C(12,2)

更加拓展一下，还有一种情况。题目要求有n个物品， k个盒子， 但是每个盒子可以不放物品，且物品可以不放完 。这时候的方案数为多少。我们可以考虑多加一个盒子来放剩下的物品， 然后和第二种情况一样在n个物品的基础上再加上盒子那么多的物品， 这样可以保证每个盒子里可以为空 ，这就是本题的答案：

$$答案为：C^{k-1+1}_{n+k+1-1} = C^{k}_{n+k}$$

变形有：

1.有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止，如257，1459等等，这类数共有几个？ 因为我们只需要计算出合法的前两个数字即可，前两个数字决定了这个数字。我们设前两位为ab 显然a+b<=9 ,且a不为0。（1_1_ 1_1_ 1_1_1_1_1） 1代表9个1，_代表8个空位。我们要把9个1分成两组，但b可以为0，我们先给b一个1，然后就相当于10个小球放入两个（a，b）不同的箱子 ，且可以剩下1不拿， 就是第三个模型，答案是C(10,2)

选板法

E.g. 有10粒糖，如果每天至少吃一粒(多不限)，吃完为止，求有多少种不同吃法？

o - o - o - o - o - o - o - o - o – o o代表10个糖，-代表9块板 10块糖，9个空，插入9块板，每个板都可以选择放或是不放，相邻两个板间的糖一天吃掉 这样一共就是 2^9= 512啦

组合数板子

inline void init() {
	for (int i=0;i<=maxn;++i) {
		C[i][0] = C[i][i] = 1;
		for (int j=1;j<i;++j) {
			C[i][j] = C[i-1][j] + C[i-1][j-1];
			C[i][j] %= MOD;
		}
	}
}
//这个板子可以预处理出maxn之内的所有组合数

参考链接：

https://blog.csdn.net/sdz20172133/article/details/81431066