四大基本计数原理

· · 算法·理论

基础原理

这是一个非常基础的原理：

全体等于其各部分之和

设S是集合，将其划分为两两不相交的子集S1，S2，S3...Sm，则S所有子集的并集就为S。

加法原理

在刚刚的条件下，设|S|为集合S的对象数目，则有一下结论:

|S|=|S1|+|S2|+|S3|+...+|Sm|

总结:

加法原理的本质是将集合划分成少量的易处理部分

乘法原理

设S是对象为有序对(a,b)的集合，其中a属于一个大小为p的集合，对于a的每种选择，b都有q种选择。求集合S的大小

由上易知，集合S的大小为pq，即|S|=pq

所以乘法原理实际上是加法原理的一个推论

水题

请确定下面这个数的正整数因数的个数

3^4*5^2*11^7*13^8

3,5,11,13都是素数，可知每个因子都是如下形式

3^a*5^b*11^c*13^d

(0<=a<=4 , 0<=b<=2 , 0<=c<=7 , 0<=d<=8)

a，b，c，d分别有5，3，8，9种选择，根据乘法原理，因子总数为5*3*8*9=1080

减法原理

设A是一个集合，U是包含A的更大集合，设A在U中的补集为\overline{\text{A}}。则有一下结论:

|A|=|U|-|\overline{\text{A}}|

重点

  1. 运用减法原理时，可以将集合U理解为全集，它通常是包含讨论中所有对象的某个自然集合。

  2. 只有计数集合U和集合\overline{\text{A}}比直接计数集合A更容易时，才会运用到减法原理

减法原理水题

取字母a~z与数字0~9中的6个，构成长度为六的字符串作为密码，求有多少个有重复字符的密码？

除法原理

设S为一个有限集合，把它换分成k个包含对象数量相等的部分(k等分)，可得

所以，如果知道了|S|与每个部分所包含对象的数量就可以求得k(~~废话~~ [排列组合基础知识](https://www.luogu.com.cn/blog/cody2508/pai-lie-zu-ge)