加法原理#

若某一试验结果只能是集合$A$或者$B$.

$A$包含$m$个子结果, $B$包含$n$个子结果.

那么该试验最终可能的结果数为$m+n$.

例: 假如一些数据包, 随机发送给上海和深圳的某个服务器, 其中上海有$100$个服务器, 深圳有$50$个服务器.

那么最终可能收到这些数据包的服务器有$100 + 50$个.

乘法原理#

若某一试验结果拥有两个部分(子试验), 两个部分(子试验)之间互不影响.

第一个子试验可能得到$n$个子结果, 第二个子试验可能得到$m$个子结果.

那么该试验最终可能的结果数为$mn$.

例: 投掷两个6面骰子

最终可能得到的结果数为$6 \times 6 = 36$种.

容斥原理#

$|A \cup B| = |A| + |B| - |A \cap B|$ 这个大家很熟了. 加法原理可以看作容斥原理在$|A \cap B| = \emptyset$的特殊情况.

向下取整函数(floor)和向上取整函数(ceil)#

屋檐了.

注意负数的情况就好.

狄利克雷抽屉原理(鸽巢原理, Pigeonhole principle)#

若$n$个集合中有$n+1$个元素, 则存在一个集合, 其元素个数大于等于2.

广义鸽巢原理#

若$n$个集合中有$m$个元素, 则存在一个集合, 其元素个数大于等于$\operatorname{ceil}(\frac{m}{n})$

其他计数原理

可以在离散数学的相关内容中找到. 对于本博客来说, 可以在组合数学(待更新)中找到.

排列(permutation)#

$n$个元素在$m$个位置进行排列, 第1个位置有$n$种可能, 第2个位置有$(n - 1)$种可能… 第m个位置有$(n - m + 1)$种可能.

可以写出排列数公式.

也可记作$P(n, m), P_n^m, A_n^m$等

组合(combination)#

$n$个元素中选$m$个形成组合(无关顺序), 每种组合要产生$A(n, n)$种排列.

于是可以写出组合数公式.

TIP

组合数又叫二项式系数.