专栏文章

排列组合

zzifuneko
学习·文化课参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0s1h1
此快照首次捕获于
2025/12/02 11:29
3 个月前
此快照最后确认于
2025/12/02 11:29
3 个月前
查看原文
数学选择性必修第三册第六章。

排列组合

  • 一般地，从 nn 个不同元素中取出 m (m≤n)m\ (m\le n) 个元素，并按照一定的顺序排成一列，叫做从 nn 个不同元素中取出 mm 个元素的一个排列（Arrangement\texttt{Arrangement}）.
  • 一般地，从 nn 个不同元素中取出 m (m≤n)m\ (m\le n) 个元素作为一组，叫做从 nn 个不同元素中取出 mm 个元素的一个组合（Combination\texttt{Combination}）.
排列的充要條件
两个排列相同是两个排列的元素完全相同且元素的排列顺序也相同的充要条件；而两个组合相同只需要两个组合的元素相同即可。
  • 从 nn 个不同元素中取出 m (m≤n)m\ (m\le n)个元素的所有不同排列的个数，叫做从 nn 个不同元素中取出 mm 个元素的排列数，用符号 Anm\text{A}^m_n 表示.
  • 从 nn 个不同元素中取出 m (m≤n)m\ (m\le n)个元素的所有不同组合的个数，叫做从 nn 个不同元素中取出 mm 个元素的组合数，用符号 Cnm\text{C}^m_n 表示.
e.g 从 44 个不同的元素 a,b,c,da,b,c,d 中任意取出 33 个元素的排列方式，组合方式，排列数与组合数。
则排列数 A43=4×3×2=24\text{A}^3_4 = 4\times 3\times 2 = 24，以“元素相同”为标准将这 2424 个排列分组，则一共有 44 组，因此组合数 C43=4\text{C}^3_4 = 4.

排列数和组合数的计算

一般地，求排列数 Anm\text{A}^m_n 可以按依次填 mm 个空位来考虑：
如图，假定有排好顺序的 mm 个空位，从 nn 个不同元素中取出 mm 个元素去填空，一个空位填上一个元素，每一种填法就对应一个排列：因此，所有不同填法的种数就是排列数 Anm\text{A}^m_n . Anm=n(n−1)(n−2)⋅⋅⋅(n−m+1)\text{A}^m_n = n(n-1)(n-2)···(n-m+1) 这里，m,n∈N∗,m≤nm,n\in \mathbb{N}^*, m\le n，这个公式叫做排列数公式。
特别地，我们把 nn 个不同的元素全部取出的一个排列，叫做 nn 个元素的一个全排列. 这时，排列数公式中 n=mn=m，即有
Ann=n×(n−1)×(n−2)×⋅⋅⋅×3×2×1=n!\text{A}^n_n = n\times (n-1)\times(n-2)\times···\times 3\times 2\times 1 = n!
Anm=n!(n−m)!\text{A}^m_n = \displaystyle\frac{n!}{(n-m)!} 的正确性证明
其实根据一些对于排列的计算，可以发现它们的规律与共性，例如：A73=A77A44=7!4!\text{A}^3_7 = \displaystyle\frac{\text{A}^7_7}{\text{A}^4_4} = \displaystyle\frac{7!}{4!}；A64×A22=6!=A66\text{A}^4_6 \times\text{A}^2_2 = 6! = \text{A}^6_6. 事实上：
Anm=n(n−1)(n−2)⋅⋅⋅(n−m+1)\text{A}^m_n = n(n-1)(n-2)···(n-m+1)
       =n×(n−1)×(n−2)×⋅⋅⋅×(n−m+1)×(n−m)×⋅⋅⋅×2×1(n−m)×⋅⋅⋅×2×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}
       =AnnAn−mn−m\ \ \ \ \ \ \ = \displaystyle\frac{\text{A}^n_n}{\text{A}^{n-m}_{n-m}}
       =n!(n−m)!\ \ \ \ \ \ \ = \displaystyle\frac{n!}{(n-m)!}
因此，排列数公式还可以写成 Anm=n!(n−m)!\text{A}^m_n = \displaystyle\frac{n!}{(n-m)!}
观察图第一幅图片，还可以这样理解求“从 44 个元素中取出 33 个元素的排列数 A43\text{A}^3_4：
  • 第 11 步，从 44 个元素中取出 33 个元素作为一组，共有 C43\text{C}^3_4 种不同的取法；
  • 第 22 步，将取出的 33 个元素作全排列：共有 A33\text{A}^3_3 种不同的排法.
根据分步乘法计数原理，有：
A43=C43⋅A33\text{A}^3_4 = \text{C}^3_4 \cdot \text{A}^3_3 即
C33=A43A33=4\text{C}^3_3 = \displaystyle\frac{\text{A}^3_4}{\text{A}^3_3} = 4
所以，一般地，有 Cnm=AnmAnn=n(n−1)(n−2)⋅⋅⋅(n−m+1)m!=∏i=n−m+1ni∏j=1mj\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∈N∗, m≤nm,n\in {\mathbb{N}}^*,\ m\le n，这个公式叫做组合数公式。
因为 Anm=n!(n−m)!\text{A}^m_n = \displaystyle\frac{n!}{(n-m)!}，所以组合数公式还可以写成：
Cnm=n!m!(n−m)!\text{C}^m_n = \displaystyle\frac{n!}{m! (n-m)!}
另外，数学上规定 Cn0=1\text{C}^0_n = 1.

组合数的性质

*性質 0\bold{0} 對於組合 Cnm\text{C}_n^m：
  • 當 m≤12nm \le \displaystyle\frac{1}{2}n 時，使用公式 Cnm=AnmAmm\text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m}
  • 當 m>12nm > \displaystyle\frac{1}{2}n 時，使用公式 Cnm=n!m!(n−m)!=∏i=m+1ni∏j=1n−mj\text{C}_n^m = \displaystyle\frac{n!}{m!(n-m)!} = \frac{\prod\limits_{\mathclap{i=m+1}}^{n} i}{\prod\limits_{\mathclap{j=1}}^{\mathclap{n-m}} j}
  • 特別地，若 m=2m = 2 時，則會有 Cn2=∑i=1n−1i\text{C}_n^2 = \sum\limits_{i=1}^{n-1}i
性质 1\bold{1} 进一步研究我们发现：一般地，从 nn 个不同元素中取出 mm 个元素后，必然剩下 (n−m)(n-m) 个元素，因此从 nn 个不同元素中取出 mm 个元素的组合，与剩下的 (n−m)(n-m) 个元素的组合一一对应. 这样，从 nn 个不同元素中取出 mm 个元素的组合数，等于从这 nn 个不同元素中取出 (n−m)(n-m) 个元素的组合数. 于是我们有
Cnm=Cnn−m\text{C}_n^m = \text{C}_n^{n-m}
由于 Cn0=1\text{C}_n^0 = 1，因此上面的等式在 m=nm=n 时也成立。
*發現
發現這樣，在計算組合數時，若 m≤12nm \le \displaystyle\frac{1}{2}n，則直接使用 Cnm=AnmAmm\text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m}；若 m>12nm > \displaystyle\frac{1}{2}n，則可以透過上述 Cnm=Cnn−m\text{C}_n^m = \text{C}_n^{n-m} 的性質，轉化為 m<12nm < \displaystyle\frac{1}{2}n 的情況，然後再使用 Cnm=AnmAmm\text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m} 進行計算，這樣更為簡便，且僅需記住一個公式即可。在使用 Cnm=AnmAmm\text{C}_n^m = \displaystyle\frac{\text{A}_n^m}{\text{A}_m^m} 時，通過多次計算很容易發現分子就是從 nn 往 11 逆向連乘，乘 mm 個即可；分母就是從 11 往 nn 順向連乘，也乘 mm 個即可，之後約分得出答案。計算是按照個人喜好來的，這裡只是提供一個方法，在計算的時候只要不出錯想用什麼方法或性質都是可以的喵
性质 2\bold{2} 在推导性质 11 时，我们运用了说明组合等式的一个常用而重要的方法，即把等号两边的不同表达式解释为对同一个组合问题的两个不同的计数方案。利用分类加法计数原理，可以发现
Cn+1m=Cnm+Cnm−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) 是 nn 个 (a+b)(a+b) 相乘，每个 (a+b)(a+b) 在相乘时有两种选择，选 aa 或 bb，而且每个 (a+b)(a+b) 中的 aa 或 bb 都选定后，将它们相乘才能得到展开式的一项. 因此，由分步乘法计数原理可知，在合并同类项之前，(a+b)(a+b) 的展开式共有 2n2^n 项，其中每一项都是 an−kbk (k∈{k∈Z ∣ 0≤k≤n})a^{n-k}b^k\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\}) 的形式.
对于每个 k (k∈{k∈Z ∣ 0≤k≤n})k\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\})，对应的项 an−kbka^{n-k}b^k 是由 (n−k)(n-k) 个 (a+b)(a+b) 中选 aa，另外 kk 个 (a+b)(a+b) 中选 bb 得到的. 由于 bb 选定后，aa 的选法也随之确定，因此，an−kbka^{n-k}b^k 出现的次数相当于从 nn 个 (a+b)(a+b) 中取 kk 个 bb 的组合数 Cnk\text{C}^k_n. 这样，(a+b)n(a+b)^n 的展开式中，an−kbka^{n-k}b^k 共有 Cnk\text{C}^k_n 个，将它们合并同类项，就可以得到
(a+b)n=∑k=0nCnkan−kbk, n∈N∗(a+b)^n = \sum\limits_{k=0}^{n}\text{C}^k_na^{n-k}b^k,\ n\in \mathbb{N}^*
这个公式叫做二项式定理，右边的多项式叫做 (a+b)n(a+b)^n 的二项展开式，其中各项的系数 Cnk (k∈{k∈Z ∣ 0≤k≤n})\text{C}^k_n\ (k\in \{k\in \mathbb{Z}\ |\ 0\le k\le n\}) 叫做二项式系数. 式中的 Cnkan−kbk\text{C}^k_na^{n-k}b^k 叫做二项展开式的通项，用 Tk+1\text{T}_{k+1} 表示，即通项为展开式的第 k+1k+1 项：
Tk+1=Cnkan−kbk\text{T}_{k+1} = \text{C}^k_na^{n-k}b^k

二项式系数的性质

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

对称性

与首末两端“等距离”的两个二项式系数相等. 事实上，这一性质可直接由 Cnm=Cnn−m\text{C}_n^m = \text{C}_n^{n-m} 得到．
直线 r=n2r = \displaystyle\frac{n}{2} 将函数 f(r)=Cnrf(r)=\text{C}^r_n 的图象分成对称的两部分，它是图象的对称轴.

增减性与最大值

各二项式系数的和

后记

  • 可恶的 Luogu 让 zifu 写了好几个小时的文章全没啦！！！怒怒怒怒啊呜...
  • 注意带 ∗* 的性质为非官方且不一定准确的性质，仅供参考。
  • ∑k=0nCnkan−kbk=Cn0an+Cn1an−1b1+⋅⋅⋅+Cnkan−kbk+⋅⋅⋅+Cnnbn \sum\limits_{k=0}^{n}\text{C}^k_na^{n-k}b^k = \text{C}^0_na^n + \text{C}^1_na^{n-1}b^1 + ··· + \text{C}^k_na^{n-k}b^k + ··· + \text{C}^n_nb^n

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...