加法原理
加法原理。很直白的,就是一个用加法来弄的原理。
简单来说,就是做一件事情有 \(n\) 种方法,第 \(i\) 种方法又有 \(a_i\) 个具体的操作方案。那么非常显然,做这件事情就有 \(a_1 + a_2 + \dots + a_{n-1} + a_n = \sum_{i=1}^{n} a_i\) 种方案。
说说具体用途吧:最常见的,DP 里面统计方案数,由于这些解决方案是互不干扰的,也就是说如果选择 \(1\) 类方法就不可能同时选择 \(2\) 类方法,那么很多时候就是把它们加起来啦。
这就是加法原理。
乘法原理
乘法原理,顾名思义,和加法原理一样,当然是用乘法来弄的原理啦!
乘法原理和加法原理不同,它表示的是,做一件事情有 \(n\) 个步骤,第 \(i\) 个步骤又有 \(a_i\) 种具体的操作方案,那么做这件事情一共就有 \(a_1 \times a_2 \times \dots a_{n-1} \times a_n = \prod_{i=1}^{n} a_i\) 中具体的操作方案。
用途吧,就是很多时候考虑统计方案数的时候,要分步骤来考虑——换言之,分类讨论?——总之就是有一个分步骤的阶段的情况下,就要用到乘法原理,把它们乘起来啦。
这就是乘法原理。
全排列
全排列表示有 \(n\) 个互不相同的物品,然后将这些物品全部打乱,重组地去排列,一共有多少种方法。答案显然,\(n \times (n-1) \times (n-2) \times \dots \times 2 \times 1\),定义这个东西为 \(n!\),即 \(n\) 的阶乘。
排列组合
排列,就是指从 \(n\) 个物品中选择 \(m\) 个排成一排。假设它们都互不相同,那么方案数是多少呢?很显然,排在第一个位置有 \(n\) 种选法,第二个位置有 \(n-1\) 种选法,第 \(i\) 个位置有 \(n-i+1\) 种选法,第 \(m\) 个位置有 \(n-m+1\) 种选法,全部乘起来,那就是 \(n \times (n-1) \times (n-2) \times \dots \times (n-m+1)\) 啦!这就定义为 \(A_{n}^{m}\),且有公式 \(A_{n}^{m} = \dfrac{n!}{(n-m)!}\)。
组合,同样是从 \(n\) 个物品中选择 \(m\) 个,但是不同的是,它是选择 \(m\) 个,但是只把这东西当做一个集合,并不对其进行排序——对,差别就在于,它比排列少考虑了具体的排序情况!这东西定义为 \(C_{n}^{m}\),也记做 \(\binom{n}{m}\),且有公式 \(C_{n}^{m} = \binom{n}{m} = \dfrac{n!}{(n-m)!\space{}m!}\)。对!就是比排列多除以了一个 \(m!\) 而已,因为不考虑顺序啦。
组合还有一个公式,那就是 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\),这也是求解杨辉三角时的递推公式。为什么呢?因为我们已经考虑完了前 \(n-1\) 个元素的情况,现在多了一个 \(n\) 元素,我们可以考虑选它,那么之前 \(n-1\) 个元素中就只需要选择 \(m-1\) 个了,这就是 \(C_{n-1}^{m-1}\),也可以考虑不选它,那么之前 \(n-1\) 个元素中还需要选择 \(m\) 个,这就是 \(C_{n-1}^{m}\),加法原理加起来就有公式 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\) 啦。
杨辉三角可以 \(O(n^2)\) 预处理出来,因此当 \(n\) 不大且需要使用组合数的时候常用杨辉三角预处理哦。
例题选讲
题太多了,我就挑几道重点讲,其他的带过一下好吧。