排列组合

排列组合

排列数

从 $n$ 个不同元素中，任取$m(m\leq n,\ m与n均为自然数，下同)$个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$个元素的排列数，用符号$A_n^m(或是P_n^m)$表示。 排列的计算公式如下： \(A_n^m=n(n-1)(n-2)···(n-m-1)=\frac{n!}{(n-m)!}\)
公式可以这样理解：$n$个人选$m$个来排队$(m\leq n)$。第一个位置可以选$n$个，第二位置可以选$n-1$个，以此类推，第$m$个 (最后一个) 可以选$n-m+1$个，得：
\(A_n^m=n(n-1)(n-2)···(n-m-1)=\frac{n!}{(n-m)!}\)
全排列：$n$个人全部来排队，队长为$n$。第一个位置可以选n个，第二个可以选$n-1$个，以此类推得：
\(A_n^n=n(n-1)(n-2)···2\times 1=n!\) 全排列是排列数得一个特殊情况

组合数

从$n$个不同元素中，任取$m\leq n$个元素组成一个集合，叫做从$n$个不同元素中取出$m$个元素的一个组合；从$n$个不同元素中取出$m\leq n$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数，用符号$\binom{n}{m}$来表示，读作$「n选m」$。
组合数计算公式 \(\binom{n}{m}=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!}\) 如何理解上述公式？我们考虑从$n$个人选$m$个出来$(m\leq n)$，不排队，不在乎顺序。若在乎顺序，结果就是 $A_n^m$，若不在乎，则需要除掉重复，那么重复了多少？同样选出来的$m$个人，排列中，还要排 $m!$次，所以得：
\(\begin{align*} \binom{n}{m}\times m! &=A^m_n\\ \binom{n}{m} &= \frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!} \end{align*}\) 组合数也被称为「二项式系数」，下文二项式定理会阐述其中的联系。
特别的，规定当$m>n$时，$A_n^m=\binom{n}{m}=0$.

二项式定理

二项式定理阐明了一个展开式的系数： \((a+b)^n=\sum\binom{n}{i}a^{n-i}b^i\) 证明可以采用数学归纳法，利用$\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$做归纳。
二项式定理也可以容易扩展成多项式的形式：
设$n$为正整数，$x_i$为实数,
\((x_1+x_2+···+x_i)^n=\sum_{满足$n_1+···+n_i=n的非负整数解}\binom{n}{n_1,n_2,···,n_t}x_1^{n_1}x_2^{n_2}···x_t^{n_t}\) 其中$\binom{n}{n_1,n_2,···,n_t}$是多项式系数，它的性质也很相似：
\(\sum{\binom{n}{n_1,n_2,···,n_t}}=t^n\)