常用数学知识归纳

链接

排列组合

0! = 1

排列

定义：从 n 个不同元素中，任取 m（m小于等于n）个不同的元素按照一定顺序排成一列，叫做从n个不同元素中取 m 个元素的一个排列。

$ A_n^m = n(n-1)(n-2)…(n-m+1) = \frac{n!}{(n-m)!} $

推导：$ A_n^m = C_n^mA_m^m $

• 先从n个不同元素中选出m个元素有$ C_n^m $种可能。然后每种可能的全排列为$ A_m^m = m! $
• 所以$ C_n^m = \frac{A_n^m}{A_m^m} = \frac{n!}{m!(n-m)!} $

推导：$ A_n^m = mA_{n-1}^{m-1} + A_{n-1}^m $

example：1,2,3,4,5 求$ A_5^3 $

• 先取特定的一个数 1，再取两个数的排列有$ A_{n-1}^{m-1} $中取法
• 然后将1 放到取出的两个数的排列中去，每种排列中1 可以放在3（m）种位置上
• 所以先取有特定数的排列为$ mA_{n-1}^{m-1} $种取法
• 剩下的不含特定数的排列取法为$ A_n^{m-1} $
• 所以总的取法为$ A_n^m = mA_{n-1}^{m-1} + A_{n-1}^m $

• 得证

• 根据下面的组合推导公式$ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} $ 以及$ A_n^m = C_n^m * m! $

• 得到$ A_n^m = m!(\frac{A_{n-1}^m}{m!} + \frac{A_{n-1}^{m-1}}{(m-1)!}) = A_{n-1}^m + mA_{n-1}^{m-1} $
• 得证

组合

定义：从 n 个不同元素中，任取 m（m小于等于n）个元素并成一组，叫做从 n 个不同元素中取 m 个元素的一个组合。（没顺序要求）

$ C_n^m = \frac{A_n^m}{A_m^m} = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!} $

推导：$ C_n^m = C_n^{n-m} $

推导：$ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} $

example: 1,2,3,4,5 求$ C_5^2 $

• 先取一个特定的数 1，再取第二个数有$ C_{n-1}^{m-1} = C_4^1 $种取法
• 然后其他剩下没有 1 的数中求$ C_{n-1}^m = C_4^2 $种取法
• 所有总共有$ C_{n-1}^{m} + C_{n-1}^{m-1} $种取法
• $ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} $
• 得证

推导：$ C_n^0 + C_n^1 + C_n^2 + … + C_n^n = 2^n $

数学归纳法：

1. 当m=1时，$C_1^0 + C_1^1 = 2 = 2^1$成立。
2. 假设当n = k 时等式成立，即：$ \sum_{i = 0}^{k}C_k^i = 2^k $ 成立时
3. 当n = k+1 时，
   $ C_{k+1}^0 + C_{k+1}^1 + C_{k+1}^2 + … + C_{k+1}^k + C_{k+1}^{k+1} $
   $ = C_{k+1}^0 + (C_k^0 + C_k^1) + (C_k^1 + C_k^2) + … + (C_k^{k-2} + C_k^{k-1}) + (C_k^{k-1} + C_k^k) + C_{k+1}^{k+1} $
   $ = C_{k}^0 + (C_k^0 + C_k^1) + (C_k^1 + C_k^2) + … + (C_k^{k-2} + C_k^{k-1}) + (C_k^{k-1} + C_k^k) + C_k^k $
   $ = 2(C_k^0 + C_k^1 + C_k^2 + … + C_K^k) $
   $ = 2(2^k) $
   $ = 2^{k+1} $
4. 由1，2，3得，等式对n都成立。

全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。