组合数学

1. 加法原理 加法原理是分类计数原理，常用于排列组合中，具体是指：做一件事情，完成它有n类方式，第一类方式有M1种方法，第二类方式有M2种方法，……，第n类方式有Mn种方法，那么完成这件事情共有M1+M2+……+Mn种方法。 比如说：从武汉到上海有乘火车、飞机、轮船3种交通方式可供选择，而火车、飞机、轮船分别有k1，k2，k3个班次，那么从武汉到上海共有 k1+k2+k3种方式可以到达。 2. 乘法原理 做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。 3. 排列 排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。 计算公式：$P^m_n=\frac{n!}{(n-m)!}$ 4. 组合 组合（combination）是一个数学名词。一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。 计算公式： $C_n^m=\frac{n!}{m!(n-m)!}$ $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$（杨辉三角） [组合数求法](https://www.luogu.com.cn/blog/ButterflyDew/post-oi-CRTblabla)