第一部分（上）

第一部分排列组合问题

这部分内容多为国内高中数学排列组合的知识点，在此简单归纳一下，确保大家都在同一频道上。

一、如何选择

一个由n个不同物体组成的n集合，我们通常有4种方法从n集合中选择r个物体：

（ⅰ）有序且不重复地选择

（ⅱ）有序且重复地选择

（ⅲ）无序且不重复地选择

（ⅳ）无序且重复地选择

举个例子：假如要从3个物体的集合{a,b,c}中选择2个物体，

如果用（ⅰ）有序且不重复地选择，会有6种不同的选法:：ab, ac, ba, bc, ca, cb；

如果用（ⅱ）有序且重复地选择，会有9种不同的选法：aa, ab, ac, ba, bb, bc, ca, cb, cc；

如果用（ⅲ）无序且不重复地选择，会有3种不同的选法：ab, ac, bc；

如果用（ⅳ）无序且重复地选择，会有6种不同的选法：aa, bb, cc, ab, ac, bc.

公式1.1 按照有序且不重复地选择的方法，从n个物体中选择r个物体，会有 $\frac{n!}{(n-r)!}$ 种方法

公式推理：假设从总数为n的集合中任意选择 $a_{1}$ , $a_{2}$ , . . . , $a_{r}$ ，r为我们要选择的物体数量，1 $\leq$ r $\leq$ n，由于不能重复选择，此时 $a_{1}$ 的选择会有n种， $a_{2}$ 的选择会有n-1种，以此类推，每多选一个就会减少1个选择， $a_{r}$ 就会有n-r+1种方式。因此，总共的选择方式就会有n(n − 1)(n − 2). . .(n − r + 1) = $\frac{n!}{(n-r)!}$ 种。

公式1.2 按照有序且重复地选择的方法，从n个物体中选择r个物体，会有 $n^r$ 种方法

这个公式比较显而易见，由于可以重复选择，每次选择都是n个，选几个就是n的几次方，因此就会有 $n^r$ 种方法选择。

公式1.3 按照无序且不重复地选择的方法，从n个物体中选择r个物体，会有 $\binom{n}{r}=\frac{n!}{(n-r)!r!}$ 种方法

与公式1.1相比，就是无序与有序的区别，因此可以先按有序的方法先选择 $\frac{n!}{(n-r)!}$ 个物体，然后再把因有序而重复的部分r!除掉，一共就会是 $\binom{n}{r}=\frac{n!}{(n-r)!r!}$ 种方法。像公式1.1和1.2就是排列，只考虑选择多少种排列，不考虑顺序，有时候也写成A(n,r)，而1.3这种就是所谓的组合，在排列的基础上还得考虑排列的顺序，有时候也写成c(n,r)。

公式1.4 按照无序且重复地选择的方法，从n个物体中选择r个物体，会有 $\binom{n+r-1}{r}$ 种方法

这种情况相比于前三种会稍微复杂一些，不能简单地像公式1.3那样，把公式1.2拿去除以r!，这样就错了，因为每个无序选择产生的有序选择的数量会随着选择中重复对象的数量变化而变化。举个例子说明会清晰一些：

假设从5个元素的集合{a,b,c,d,e}种选择abc，则会产生6个无序选择：abc, acb, bac, bca, cab, cba；然而，如果选择的是aab（2个重复对象），那么只会产生3个无序选择：aab, aba, baa。

因此，只能使用其他方法来解决这个问题，聪明的人们就想出了这个办法：可以利用公式1.3，把无序重复地从n个物体中选择r个物体的问题转换为按照无序且不重复地从n+r-1个物体中选择r个物体，因此总共就会有 $\binom{n+r-1}{r}$ 种方法进行选择，但是为什么可以这么转换呢？公式1.3和1.4的区别就是重复与否，于是我们可以把重复的部分加进集合里，如果要重复地从n集合里选择r个物体，其实也就是不重复地从n+r-1的集合里选择r个物体；r=1时重复与不重复是一个意思，因此得减掉r=1的情况。

例题1.5 从7个物体的集合里选择3个物体，分别在考虑重复与不重复地情况下，计算有序、无序选择的数量

有序不重复地选择的数量为： $7!/4!=7\cdot 6\cdot 5=210$

有序重复地选择的数量为： $7^3=343$

无序不重复地选择的数量为： $\binom{7}{3}=35$

无序重复地选择的数量为： $\binom{9}{3}=84$

例题1.6 要选择小于或等于 20 的五个不同的正整数，使得没有两个选定的整数是连续的,有多少种方法？

从题目可以得出，需要的是无序且不重复地进行选择，因为条件限制整数之间不连续，实际上是从16个正整数中选取5个正整数，也就是 $\binom{16}{5}$ =4368种方法。

第一部分（上）