Ruibin_Ningh
排列与组合的根本区别
排列严格要求顺序,例如有5个元素 $A,B,C,D,E$ ,想要对这些元素中选取三个作为一组,那么在排列中, $ABC$ 与 $BCA$ 是两种不同的排列.但是在组合中, $ABC$ 与 $BCA$ 以及 $CBA$ 等性质都是一样的
总结:
💡 排列：元素个数指的是从总集合中选择并排列的元素数量，顺序不同的排列被视为不同。($ABC 不等同于BCA$) 组合：元素个数指的是从总集合中选择的元素数量，顺序相同的组合被视为相同。($ABC等同于BCA$)
排列
对指定个数的元素中取出指定个数的元素进行排序,这就是排列
用公式表示:就是在 $n$ 个元素内取 $m$ 个元素
$$
A_{n}^{m}=\frac{n!}{\left( n-m \right) !} (也可以是P_{n}^{m})
$$
探究
例:现有 $n$ 个元素,对于这些元素,取 $m$ 个不同的元素排列,那么有多少种排列方法?
假设第i个元素表示为 $a_i$ ,因为要在 $n$ 个元素中取 $m$ 种不同的排列方法所以我们可以容易的推断出一下过程
第一步: $a_1$ 有 $n$ 中可能性,
第二步: $a_2$ 有 $n-1$ 种可能性(第一个元素占用一种可能性)
第三步: $a_3$ 有 $n-2$ 种可能性…
递推:一直到 $a_m$ 有 $n\cdot \left( n-1 \right) \times \left( n-2 \right) \times ...\times \left( n-m+1 \right) =\frac{n!}{\left( n-m \right) !}$种可能性
也就是 $A_{n}^{m}$ 种排列方法
表达式:
$$
f\left( n,m \right) =n\times f\left( n-1,m-1 \right) \\ f\left( 1,m \right) =0 \\ f\left( n,1 \right) =n
$$
值得注意的是, $0!=1$ ,这经常会被遗忘
解释:
为什么最后递到 $(n-m+1)$ ?
答:因为 $n$ 到 $(n-m)$ 有 $n+1$ 种可能性,超出选的范围 比如 $1$ 到 $n$ 有 $n$个数, $n-1$ 到 $n-m$ 有 $m$ 个数,加上最前面的$n$ 就是 $n-m+1$个数了
为什么不是 $n!-\left( n-m \right) !$ 种可能性?
答:因为除法是乘法的逆运算,所以 $(n-m)!$ 就把 $1$ 到 $(n-m)$ 的阶乘部分直接抵消了
$$\frac{n!}{\left( n-m \right) !}=n\cdot \left( n-1 \right) \times \left( n-2 \right) \times ...\times \left( n-m+1 \right) \times \left( n-m \right) \div \left( n-m \right) \times \left( n-m-1 \right) \div \left( n-m-1 \right) ...\times 1\div 1$$
组合
组合不考虑元素的排列顺序,仅关心元素的组合
$$
\left( \begin{array}{c} n\\ m\\\end{array} \right) =C_{n}^{m}=\frac{A_{n}^{m}}{m!}=\frac{n!}{m!\left( n-m \right) !}
$$
💡 例如有元素$A,B,C,D$,选其中三个组合,那么选$A,B,C$与选$B,C,A$是同一种结果
探究
例:现有 $n$ 个元素,若在这些元素中取 $m$ 个不同的元素,有多少种不同的组合?
我们都知道,如果考虑排列顺序,就是 $A_{n}^{m}$ 种可能性,但是组合是不考虑排列顺序的,所以在排列的基础上,我们要去掉多余的排列方式,仅保留一种组合,那么就要除以 $m!$ 种可能性
$$
C_{n}^{m}=\frac{n\times \left( n-1 \right) \times \left( n-2 \right) \times ...\times \left( n-m+1 \right)}{1\times 2\times 3\times ...\times m}
$$
其中, $n\times \left( n-1 \right) \times \left( n-2 \right) \times ...\times \left( n-m+1 \right)$ 有 $m$ 个元素,所以 $n$ 有 $m$ 种可能(因为只选取 $m$ 个元素,那么第一个元素有 $m$ 种可能)那么,我们去除掉了这 $m!$ 的可能性,剩下的只有一种排列,也就代表了组合的个数
表达式:
$$
f\left( n,m \right) =f\left( n-1,m-1 \right) +f\left( n-1,m \right) \\f\left( n,0 \right) =1\\f\left( n,n \right) =1
$$
为什么$C_{n}^{m}=C_{n}^{n-m}$？
$$
C_{n}^{m}=\frac{n!}{m!\text{(}n-m\text{)!}}\\C_{n}^{n-m}=\frac{n!}{\left( n-m \right) !\left[ n-\left( n-m \right) \right] !}=\frac{n!}{\left( n-m \right) !\left( n-n+m \right) !}=\frac{n!}{\left( n-m \right) !m!}
$$
展开完我们发现, $C_{n}^{m}$ 与 $C_{n}^{n-m}$ 是等价的,故 $C_{n}^{m}=C_{n}^{n-m}$