数论——组合数学入门

排列组合

排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。--------OI Wiki

乘法原理和加法原理

加法原理，就好比一个工作，有 \(n\) 个解决的方案，第 \(i\) 项方案有 \(a_{i}\) 种不同的实现方式，所以这个工作有 \(a_{1}+a_{2}+a_{3}+\ldots+a_{n}\) 种方式来解决。

乘法原理，就好比一个工作，有 \(n\) 个步骤，第 \(i\) 步有 \(a_{i}\) 种方法来完成，所以这个工作的方式有 \(a_{1}\times a_{2}\times a_{3}\times \ldots \times a_{n}\) 种方式来解决。

排列数

给定 \(n\) 个数，从中选取 \(m\) 个数形成一个排列，可能的排列的数量，用 \(A_{n}^{m}\) 来表示（给定的数都为正整数）。

排列的计算公式：

其实就是分子分母同乘一个 \((n-m)!\)。

其中 \(n!=1\times 2\times 3\times \ldots \times n\)。

全排列就是当 \(n=m\) 的时候的一种特殊情况，此时 \(A_{n}^{n}=n!\)。

组合数

区别就是，排列数是要求顺序的，而组合数是从 \(n\) 个元素里面选取 \(m\) 个数组成一个集合，问有多少种可能，通常用 \(C_{n}^{m}\) 来表示。

组合数计算公式：

可以发现只比排列的公式分母多了一个 \(m!\)，因为不考虑顺序，所以可以想到，挑出来的 \(m\) 个元素组成的集合，里面的排列数是 \(m!\)，而这里面的元素组成的集合都是相同的，也就是这 \(m\) 个数本来应该算一个，但是排列里面是算了 \(m!\)，所以排列的公式除以 \(m!\) 即为我们要求的答案。

现在人们习惯用 \(\binom{n}{m}\) 表示 \(n\) 个元素里面选 \(m\) 个，但是我个人觉得不如用 \(C_{n}^{m}\) 直观，但我们还是要了解这个表示方式。