12.计数原理II - Shane Lorien

果然直接截图很好吧，为什么要手打公式呢（

韦恩图是一个很好的表示方法。从此图以及加法原理有：结合以上三个公式，可以看到如果把两个集合的势相加，交集被多算了一次，所以类似地，对于三个集合但如果我们直接减去两两的交，又会多减去一些那么就可以看出需要加回去三个集合的交集的势类似地可以推广到个集合的情形，我们有如下定理：

更优雅地，我们写成：

这就是容斥原理。

Ex.有一个包含到的整数集合，他的排列中有多少至少满足下面三个之一条件：后面是 (后简写)，,？

仍然高中题，但是我们审慎地思考我们在做什么：

首先我们要计算符合条件的集合的势，这不好求，我们构造双射把他转换成容易求的。是和其他剩下的数字的排列，容易验证这就是双射，所以，那么我们算就好了。由于的元素都不同，这就是一个全排列，于是。

接下来我们看看有多少排列同时满足，类似地建立双射，变成，和其他数字的排列，得到势为。如果是呢，那就是和其他数字的排列，还是。类似地，我们可以得到三个集合的交。最后利用容斥原理，三个集合的并的势就是。

什么叫簿记员规则（总之是说，一个序列有个重复的字符，那么能组成的字符串个数就是：

的时候实际上就是二项式

拆成个东西相乘就能很好地匹配选的意义。

Ex. 抓五张扑克牌（52张），抓到四张一样的情况有多少种？

同样双射，映射到 $一样的牌的大小，剩下的牌的大小，剩下的牌的花色$ ，那么就利用乘法原理得到。

如果三带二呢，用CSHD表示花色，同样可以构造双射：然后：第一个牌的大小：13 第二个是四选三：第三个是另一个值：12 最后是两张牌的花色：最后利用乘法原理得到结果。

这一切都和高中朴素的直觉非常吻合呢。高中老师对排列组合题强调的所谓策略，其实就是建立双射的方法。

有时候建立的未必是双射，那就要利用除法原则。

Ex. {1,2,3}要拍照，{1,2}要待一起。我们建立映射到{12,3}，那么注意到{1,2,3}和{2,1,3}都被映射到{12,3}，因而需要有一个的因子。

算两次 要从人里面选个代表，要么选了要么没选，分别对应和，那么也就有

这是组合问题的一种常见证明方法。另一个问题：

[!证明] 记是从个红球和个绿球中选个球的集合。，因为这就是个球选个。

考虑选个红球的情况，那么就选了个绿球，那么就有种情况。对所有的情况求和就得到了。

综合以上两种算法得到原等式成立。