排列组合

· · 学习·文化课

数学选择性必修第三册第六章。

排列组合

::::info[排列的充要條件]{open} 两个排列相同是两个排列的元素完全相同且元素的排列顺序也相同的充要条件；而两个组合相同只需要两个组合的元素相同即可。 ::::

e.g 从 4 个不同的元素 a,b,c,d 中任意取出 3 个元素的排列方式，组合方式，排列数与组合数。

则排列数 \text{A}^3_4 = 4\times 3\times 2 = 24，以“元素相同”为标准将这 24 个排列分组，则一共有 4 组，因此组合数 \text{C}^3_4 = 4.

排列数和组合数的计算

一般地，求排列数 \text{A}^m_n 可以按依次填 m 个空位来考虑：

如图，假定有排好顺序的 m 个空位，从 n 个不同元素中取出 m 个元素去填空，一个空位填上一个元素，每一种填法就对应一个排列：因此，所有不同填法的种数就是排列数 \text{A}^m_n .

\text{A}^m_n = n(n-1)(n-2)···(n-m+1)

这里，m,n\in \mathbb{N}^*, m\le n，这个公式叫做排列数公式。

特别地，我们把 n 个不同的元素全部取出的一个排列，叫做 n 个元素的一个全排列. 这时，排列数公式中 n=m，即有

\text{A}^n_n = n\times (n-1)\times(n-2)\times···\times 3\times 2\times 1 = n!

::::success[\text{A}^m_n = \displaystyle\frac{n!}{(n-m)!} 的正确性证明] 其实根据一些对于排列的计算，可以发现它们的规律与共性，例如：\text{A}^3_7 = \displaystyle\frac{\text{A}^7_7}{\text{A}^4_4} = \displaystyle\frac{7!}{4!}；\text{A}^4_6 \times\text{A}^2_2 = 6! = \text{A}^6_6. 事实上：

\text{A}^m_n = n(n-1)(n-2)···(n-m+1) \ \ \ \ \ \ \ = \displaystyle\frac{n\times (n-1)\times (n-2)\times ···\times (n-m+1)\times (n-m)\times ···\times2\times 1}{(n-m)\times ···\times2\times 1} \ \ \ \ \ \ \ = \displaystyle\frac{\text{A}^n_n}{\text{A}^{n-m}_{n-m}} \ \ \ \ \ \ \ = \displaystyle\frac{n!}{(n-m)!}

因此，排列数公式还可以写成

\text{A}^m_n = \displaystyle\frac{n!}{(n-m)!}

::::

观察图第一幅图片，还可以这样理解求“从 4 个元素中取出 3 个元素的排列数 \text{A}^3_4：

根据分步乘法计数原理，有：

\text{A}^3_4 = \text{C}^3_4 \cdot \text{A}^3_3

即

\text{C}^3_3 = \displaystyle\frac{\text{A}^3_4}{\text{A}^3_3} = 4

所以，一般地，有

\text{C}^m_n = \displaystyle\frac{\text{A}^m_n}{\text{A}^n_n} = \displaystyle\frac{n(n-1)(n-2)···(n-m+1)}{m!} = \frac{\prod\limits_{\mathclap{i=n-m+1}}^{n} i}{\prod\limits_{\mathclap{j=1}}^{\mathclap{m}} j}

这里，m,n\in {\mathbb{N}}^*,\ m\le n，这个公式叫做组合数公式。

因为 \text{A}^m_n = \displaystyle\frac{n!}{(n-m)!}，所以组合数公式还可以写成：

\text{C}^m_n = \displaystyle\frac{n!}{m! (n-m)!}

另外，数学上规定 \text{C}^0_n = 1.

组合数的性质

*性質 \bold{0} 對於組合 \text{C}_n^m：

性质 \bold{1} 进一步研究我们发现：一般地，从 n 个不同元素中取出 m 个元素后，必然剩下 (n-m) 个元素，因此从 n 个不同元素中取出 m 个元素的组合，与剩下的 (n-m) 个元素的组合一一对应. 这样，从 n 个不同元素中取出 m 个元素的组合数，等于从这 n 个不同元素中取出 (n-m) 个元素的组合数. 于是我们有

\text{C}_n^m = \text{C}_n^{n-m}

由于 \text{C}_n^0 = 1，因此上面的等式在 m=n 时也成立。

::::info[*發現]{open} 發現這樣，在計算組合數時，若 m \le \displaystyle\frac{1}{2}n，則直接使用 \text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m}；若 m > \displaystyle\frac{1}{2}n，則可以透過上述 \text{C}_n^m = \text{C}_n^{n-m} 的性質，轉化為 m < \displaystyle\frac{1}{2}n 的情況，然後再使用 \text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m} 進行計算，這樣更為簡便，且僅需記住一個公式即可。在使用 \text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m} 時，通過多次計算很容易發現分子就是從 n 往 1 逆向連乘，乘 m 個即可；分母就是從 1 往 n 順向連乘，也乘 m 個即可，之後約分得出答案。計算是按照個人喜好來的，這裡只是提供一個方法，在計算的時候只要不出錯想用什麼方法或性質都是可以的喵 ::::

性质 \bold{2} 在推导性质 1 时，我们运用了说明组合等式的一个常用而重要的方法，即把等号两边的不同表达式解释为对同一个组合问题的两个不同的计数方案。利用分类加法计数原理，可以发现

\text{C}_{n+1}^m = \text{C}_n^m + \text{C}_n^{m-1}

二项式定理

探索 (a+b)^n 的展开式。

通过分析一些二项式，易发现由于 (a+b) 是 n 个 (a+b) 相乘，每个 (a+b) 在相乘时有两种选择，选 a 或 b，而且每个 (a+b) 中的 a 或 b 都选定后，将它们相乘才能得到展开式的一项. 因此，由分步乘法计数原理可知，在合并同类项之前，(a+b) 的展开式共有 2^n 项，其中每一项都是 a^{n-k}b^k\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\}) 的形式.

对于每个 k\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\})，对应的项 a^{n-k}b^k 是由 (n-k) 个 (a+b) 中选 a，另外 k 个 (a+b) 中选 b 得到的. 由于 b 选定后，a 的选法也随之确定，因此，a^{n-k}b^k 出现的次数相当于从 n 个 (a+b) 中取 k 个 b 的组合数 \text{C}^k_n. 这样，(a+b)^n 的展开式中，a^{n-k}b^k 共有 \text{C}^k_n 个，将它们合并同类项，就可以得到

(a+b)^n = \sum\limits_{k=0}^{n}\text{C}^k_na^{n-k}b^k,\ n\in \mathbb{N}^*

这个公式叫做二项式定理，右边的多项式叫做 (a+b)^n 的二项展开式，其中各项的系数 \text{C}^k_n\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\}) 叫做二项式系数. 式中的 \text{C}^k_na^{n-k}b^k 叫做二项展开式的通项，用 \text{T}_{k+1} 表示，即通项为展开式的第 k+1 项：

\text{T}_{k+1} = \text{C}^k_na^{n-k}b^k

二项式系数的性质

*观察上图，发现什么规律？这不就是刚学编程就知道的杨辉三角形嘛）

对称性

与首末两端“等距离”的两个二项式系数相等. 事实上，这一性质可直接由 \text{C}_n^m = \text{C}_n^{n-m} 得到．

直线 r = \displaystyle\frac{n}{2} 将函数 f(r)=\text{C}^r_n 的图象分成对称的两部分，它是图象的对称轴.

增减性与最大值

各二项式系数的和

后记