组合数学_排列与组合
加法原理
完成一件事情，有N类方式去实现，第一类方式有 a1a_1a1种，第二类方法有a2a_2a2种，…，第N类方法有ana_nan种，则完成这件事情的总方法数为： ∑i=1Nai\sum_{i=1}^N a_ii=1∑Nai 例如：从北京到上海有火车、飞机、轮船 3 种方式，火车、飞机、轮船分别有 a1，a2，a3 个班次，那么从北京到上海有 a1+a2+a3 种方式可以到达。
乘法原理
做一件事，完成它要分成 n 个步骤，第一步有 a1a_1a1 种不同的方法，第二步有 a2a_2a2 种不同的方法，…，第 n 步有 ana_nan 种不同的方法，那么完成这件事共有 a1×a2×a3×…×ana_1 ×a_2×a_3×…×a_na1×a2×a3×…×an 种不同的方法
例如：从北京乘坐火车到上海，需要转 3 次车，每次专车分别有 a1，a2，a3 个班次，那么从北京到上海有 a1×a2×a3 种方式可以到达。
排列组合
在排列与组合问题中，经常会出现计数问题，解决计数问题的思路一般有以下三种：
1）只取需要的。将各种符合条件的情形枚举出来，再利用加法原理求和。
2）先取后排。将各步符合条件的排列或组合计算出来，再根据乘法原理求积。
3）先全部取，再减去不要的。利用容斥定理，将各种符合条件的情形枚举出来，再减去不符合条件的。
排列数
从nnn个不同元素中取出m(m<=n)m(m<=n)m(m<=n)个元素的所有排列的个数，叫做从nnn个不同元素中取出mmm个元素的排列数，⽤符号AnmA_n^mAnm表示 Anm=n!(n−m)!A_n^m=\frac{n!}{(n-m)!}Anm=(n−m)!n!
组合数
从nnn个不同元素中取出mmm个元素的所有组合的个数，叫做从nnn个不同元素中取出mmm个元素的组合数。⽤符号CnmC_n^mCnm或C(n,m)C(n,m)C(n,m)来表示 Cnm=Anmm!=n!m!(n−m)!C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}Cnm=m!Anm=m!(n−m)!n!
组合恒等式
1）Cnm=Cnn−mC_n^m=C_n^{n-m}Cnm=Cnn−m
2）Cnm=Cn−1m+Cn−1m−1C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}Cn