科数网知识库
首页
目录
排列组合
日期:
2023-08-29 20:35
查看:
100
次
**引入** 排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。 在高中初等数学中，排列组合多是利用列表、枚举等方法解题。 **加法 & 乘法原理** 加法原理 完成一个工程可以有 $n$ 类办法，$a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$ 种不同的方法。 加法原理举例：从北京到上海可以：（1）开车过去 （2）做火车过去 （3）乘飞机过去 所以，一共有3种方法。 乘法原理 完成一个工程需要分 $n$ 个步骤，$a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。 乘法原理举例：吃饭主食有 馒头和米饭，菜食有：烧肉、烧鱼和烧鸡，那么吃饭的组合有 馒头烧肉、馒头烧鱼、馒头烧鸡、米饭烧肉、米饭烧鱼、米饭烧鸡 共6种排法。 排列与组合基础 排列数 从 $n$ 个不同元素中，任取 $m$（$m\leq n$，$m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$（或者是 $\mathrm P_n^m$）表示。 排列的计算公式如下： $$ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} $$ $n!$ 代表 $n$ 的阶乘，即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。 公式可以这样理解：$n$ 个人选 $m$ 个来排队 ($m \le n$)。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推，第 $m$ 个（最后一个）可以选 $n-m+1$ 个，得： $$ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} $$ 全排列：$n$ 个人全部来排队，队长为 $n$。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得： $$ \mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! $$ 全排列是排列数的一个特殊情况。 组合数 从 $n$ 个不同元素中，任取 $m$($m\leq n$) 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $\mathrm C_n^m$ 来表示。 组合数计算公式 $$ \mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} $$ 如何理解上述公式？我们考虑 $n$ 个人 $m$($m \le n$) 个出来，不排队，不在乎顺序 $\mathrm C_n^m$。如果在乎排列那么就是 $\mathrm A_n^m$，如果不在乎那么就要除掉重复，那么重复了多少？同样选出的来的 $m$ 个人，他们还要“全排”得 $\mathrm A_n^m$，所以得： $$ \begin{aligned} \mathrm C_n^m \times m! &= \mathrm A_n^m\\ \mathrm C_n^m &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned} $$ 组合数也常用 $\dbinom{n}{m}$ 表示，读作「$n$ 选 $m$」，即 $\displaystyle \mathrm C_n^m=\binom{n}{m}$。实际上，后者表意清晰明了，美观简洁，因此现在数学界普遍采用 $\dbinom{n}{m}$ 的记号而非 $\mathrm C_n^m$。 组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。 特别地，规定当 $m>n$ 时，$\mathrm A_n^m=\mathrm C_n^m=0$。
本系统使用
启明星知识库Kbase
搭建，最后更新于
2023-08-29 20:35
，如果您有意见或建议请点击
反馈
。