组合数学 笔寄

加法原理

完成一个事情有 \(n\) 类做法，第 \(i\) 类做法又分为 \(a_i\) 种。所以这件事情有 \(S=\sum_{i=1}^{n}a_i\) 的不同的完成方法。

乘法原理

草字头有 \(3\) 种写法，回字有 \(4\) 种写法，所以茴香豆的茴有 \(S=3\times 4\) 种写法。
同样，一件事情有 \(n\) 个步骤，每个步骤又有 \(a_i\) 种不同的方法。所以这件事情一共有 \(S=\prod_{i=1}^{n}a_i\) 种不同的完成方法。

排列

从 \(n\) 个不同元素中，取出其中 \(m\) 个元素按照一定顺序组成一个排列，共有多少种不同的排列数？
设排列数为 \(\operatorname{\large A}_{n}^{m}\)，易得 \(\operatorname{\large A}_{n}^{m}=\prod_{i=1}^{m}(n-i+1)=\dfrac{n!}{(n-m)!}\)。
解释：首先在 \(n\) 个元素中选一个，再在 \(n-1\) 个元素中选一个…………以此类推。
特别的，定义 \(0!=1\)。当 \(m=n\)，\(\operatorname{\large A}_{n}^{m}=n!\)；当 \(m>0\)，规定 \(\operatorname{\large A}_{n}^{m} = 0\)。

组合

和排列很像，只不过无序。可以理解为从 \(n\) 个中选 \(m\) 个组成一个集合。写作 \(\operatorname{\large C}_{n}^{m}\) 或 \(\dbinom{n}{m}\)（二者上下的 \(n\) 和 \(m\) 顺序不同），读作 n 选 m别读西恩艾姆了。
组合数公式 \(\operatorname{\large C}_{n}^{m}=\dfrac{\operatorname{\large A}_{n}^{m}}{m!}=\dfrac{n!}{m!(n-m)!}\)，也就是把元素相同顺序不同的排列只算一次。
当然 \(\operatorname{\large A}_{n}^{m}=\operatorname{\large C}_{n}^{m}\times m!\)。