排列数公式
\[A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}\]
推导: 把 \(n\) 个不同的元素任选 \(m\) 个排序, 按计数原理分步进行:
取第一个: 有 \(n\) 种取法;
取第二个: 有 \((n-1)\) 种取法;
取第三个: 有 \((n-2)\) 种取法;?
......
取第 \(m\) 个: 有 \((n-m+1)\) 种取法;
......
最后一步, 取最后一个: 有 \(1\) 种取法.
根据分步乘法原理, 得出上述公式.
组合数公式
- \[C_n^m=\frac{
- A_n^m
- }{
- A_m^m
- }=\frac{
- n(n-1)(n-2)\cdots (n-m+1)
- }{
- m!
- }=\frac{
- n!
- }{
- m!
- }\]
- \[C_n^n=1\]
证明: 利用排列和组合之间的关系以及排列的公式来推导证明.
将部分排列问题 \(A_n^m\) 分解为两个步骤:?
第一步, 就是从 \(n\) 个球中抽 \(m\) 个出来, 先不排序, 此即定义的组合数问题 \(C_n^m\);
第二步, 则是把这 \(m\) 个被抽出来的球全部排序, 即全排列 \(A_n^m\).
根据乘法原理,\(A_n^m=C_n^m A_m^m\), 那么 \[C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!}\]
来源: http://www.bubuko.com/infodetail-3004304.html