排列与组合

组合数学 数学

---

基本概念

排列

从 $n$ 个元素中取 $r$ 个按顺序排成一列, 称为从 $n$ 中取 $r$ 的排列, 其排列方案数以 $P(n,r)$ 表示.

书上的定义中写的是用 $P$ 表示, 但好像现在一般都是用 $A$ 了.

排列和组合其实都还挺好理解的,

要在 $n$ 个元素中取 $r$ 个元素, 那么第 1 个元素就有 $n$ 种选择, 第 2 个元素有 $n-1$ 种选择, 第 $i$ 个元素就有 $n-i+1$ 种选择, 根据乘法法则, 总方案数就是这些选择的乘积, 所以

$$A(n,r)=n*(n-1)*(n-2)* \cdots (n-r+1).$$

化简一下可以得到

$$A(n,r)=\frac{n!}{(n-r)!}.$$

特别的, 当 $n=r$ 时, $A(n,n)$ 称为 $n$ 的全排列, 其排列数为

$$n!$$

书上还提到了一个模型的转换,
从 $n$ 中取 $r$ 的排列就相当于: 有 $n$ 个有区别的球, $r$ 个有区别的盒子, 每个盒子必须且只能放一个球, 求放球的方案数.

组合

从 $n$ 个元素中任取 $r$ 个元素一组, 若不考虑它们的顺序时, 则称为从 $n$ 中取 $r$ 的组合 , 它的方案数以 $C(n,r)$ 或 $\binom{n}{r}$ 表示.

排列和组合的区别就在于 排列要考虑选取元素的顺序, 而组合不用.

若转换成刚才那个 球和盒子 的模型, 那么就是:
有 $n$ 个有区别的球, $r$ 个没有区别的盒子, 每个盒子必须且只能放一个球, 求放球的方案数.

可以看到, 排列中的盒子是有区别的, 组合中的盒子是没有区别的, 而 $r$ 个盒子的全排列的排列数为 $r!$，这就是组合的重复度, 那我们将在 $n$ 中取 $r$ 的排列数除以 $r!$ 就可以得到组合数了.(相当于把 $r$ 个有区别的盒子变得没区别了)

所以, 组合数的公式为

$$C(n,m)=\frac{n!}{m!(n-m)!}.$$

再补一个老师上课讲的东西, 感觉挺有用的.

求从 $n$ 个元素中依次取 $r_1,r_2,r_3,\cdots r_k$ 个元素的方案数, 其中 $r_1+r_2+r_3+\cdots r_k=n$.

开始推吧, 设方案数为 $X$ 则,

$$\begin{align} X &=C_n^{r_1} * C_{n-r_1}^{r_2} * C_{n-r_1-r_2}^{r_3} * \cdots *C_{n-r_1-r_2-r_3-\cdots - r_k}^{r_k} \nonumber \\ &=\frac{n!}{r_1!(n-r_1)!}*\frac{(n-r_1)!}{r_2!(n-r_1-r_2)!}*\frac{(n-r_1-r_2)!}{r_3!(n-r_1-r_2-r_3)!}* \cdots *\frac{(n-r_1-r_2-r_3-\cdots - r_k)!}{r_k!(r_k-r_k)!} \nonumber \\ &=\frac{1}{r_1*r_2*r_3* \cdots * r_k} \nonumber \end{align}$$

所以, 我们就可以直接套结论了

$$X=\frac{1}{r_1*r_2*r_3* \cdots * r_k}.$$

---

例题

书上的例题我就不抄在这里了, 就记一下老师上课时讲的两道题吧

例1

从 [1,300] 中取三个不同的数, 使这三个数的和能被 3 整除, 有多少种方案?

先考虑一下若三个数的和能被 3 整除的条件是什么.
首先, 三个能被 3 整除的数的和一定能被 3 整除, 因为它们除 3 的余数都为 0, 余数的和也为 0.
继续从余数的角度来考虑, 可以发现, 只要这三个数除 3 的余数的和能够被 3 整除, 那么这三个数的和就一定能被 3 整除.

用式子来表示或许会清楚一点, 设选出的三个数分别为 $a,b,c$, 那么方案合法的条件为

$$3\mid (a\%3+b\%3+c\%3).$$

分类讨论一下,
1. 三个数的余数都为 0.
2. 三个数的余数都为 1.
3. 三个数的余数都为 2.
4. 三个数的余数分别为 0,1,2.

把 [1,300] 中的数按照除 3 的余数分为三个集合,

$A=\{x\mid x\%3=0\}, \\ B=\{x\mid x\%3=1\}, \\ C=\{x\mid x\%3=2\}, \\ $
显然, 每个集合中都有 100 个数.

那么这 4 种情况就分别是:
1. 从集合 $A$ 中选 3 个数.
2. 从集合 $B$ 中选 3 个数.
3. 从集合 $C$ 中选 3 个数.
4. 从集合 $A,B,C$ 中分别选 3 个数.

所以, 总方案数就为

$$3*C_{100}^3+(C_{100}^3)^3$$

例2

某车站有 6 个入口, 每个入口每次只能进 1 个人, 现有 9 个人, 问进站方案数为多少? (两个方案不同当且仅当 有至少 1 个人的进站口不一样 或 2 个人的进站顺序不一样)

这题的解法真的超级巧妙, 我听到的时候都惊了.

先考虑第一个人, 他有 6 种选择;
第二个人, 是否还是 6 种选择呢?

我们发现, 若第二个人选择了第一个人选择的入口, 那么他可以选择在第一个人前进站, 也可以在第一个人后进站, 再加上剩下的 5 个入口, 总共就是 7 种选择.

同理, 第 3 个人就有 8 种选择,

所以, 总方案数为

$$6*7*8* \cdots *14=726485760$$

---

想说的

排列组合的基础还是挺简单的, 多做几道题就可以熟练了.

写这篇笔记的时候, 机房里就 2 个人, 其他人明天就回赣州了, 我和另外两个同学还得留下来听数学课....22 号回到家, 26号就要去军训了, 几乎一个暑假都在长郡.
真的有点无心学习的感觉, 边听歌边写完了这篇, 用了可能有 2 个小时, 写的也不是很严谨.
怎么说呢, 希望努力有回报吧, 还是那句话: Keep Going.