排列与组合
排列数
1.定义
从 NNN 个不同的元素中任意取 m(m≤n)m(m\le n)m(m≤n)个元素按照一定的顺序排成一排，叫做从 nnn 个不同的元素中取 mmm 个元素的一个排列。
表示：AnmA_n^mAnm 或 PnmP_n^mPnm
2.计算公式
Anm=n(n−1)(n−2)…(n−m+1)=n!(n−m)!A_n^m=n(n-1)(n-2)\dots(n-m+1)=\frac{n!}{(n-m)!} Anm =n(n−1)(n−2)…(n−m+1)=(n−m)!n!
组合数
1.定义
从 nnn 个元素中取出 m(m≤n)m(m\le n)m(m≤n)个组成一组（不计较组内的各个元素的次序）叫做从 nnn 个元素中取出 mmm 个元素的组合。
特点：两个组合相同，只需要两个组合的元素相同，不考虑元素的先后顺序。
abc acb bac 是相同的。
表示：CnmC_n^mCnm
2.计算公式
Cnm=AnmAmm=n!(n−m)!m!=n(n−1)(n−2)…(n−m+1)m!C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{(n-m)!m!}=\frac{n(n-1)(n-2)\dots(n-m+1)}{m!} Cnm =Amm Anm =(n−m)!m!n! =m!n(n−1)(n−2)…(n−m+1)
3.与排列数的关系
Anm=Cnm×Amm=Cnm×m!A_n^m=C_n^m\times A_m^m=C_n^m\times m! Anm =Cnm ×Amm =Cnm ×m!
排列：
1. 先从 nnn 个里面选 mmm 个组合；
2. 再把 mmm 个全排列；
3. 乘法原理。
4.组合数的性质
对称性：
Cnm=Cnn−mC_n^m=C_n^{n-m} Cnm =Cnn−m
递推式：
Cnm=Cn−1m+Cn−1m−1C_n^m=C_{n-1}^m+C_{n-1}^{m-1} Cnm =Cn−1m +Cn−1m−1
二项式定理：
(a+b)n=∑m=0nCnman−mbm(a+b)^n=\sum_{m=0}^nC_n^ma^{n-m}b^m (a+b)n=m=0∑n Cnm an−mbm
