排列组合

基本概念

加法原理：完成一个工程有n类方法，每类 $a_i$ 个方法，一共有 $S = \sum_{i=1}^n a_i$ 种方法。
乘法原理：完成一件事要n个步骤，每个步骤 $a_i$ 个方法，一共有 $S = \prod_{i=1}^n a_i$ 种方法。
排列数：从n个不同的元素中依次取出m个元素排成一列，产生的不同排列的数量为
$A_n^m = \frac{n!} {(n-m)!} = n*(n-1)*...*(n-m+1)$
组合数：从n个不同的元素中取出m个组成一个集合(不考虑顺序)，产生的不同集合数量为
$C_n^m = \frac{n!} {m!(n-m)!} = \frac {n*(n-1)*...*(n-m+1)} {m*(m-1)*...*2*1}$
$C_n^m = \binom {n}{m}$ 不过现在更多人用这种形式表达 $\binom {n}{m}$
当m>n时 $A_n^m = C_n^m = 0$
组合数的性质
1. $C_n^m = C_{n-1}^m+C_{n-1}^{m-1}$
2. $C_n^m = C_n ^{n-m}$
3. $2^n = \sum _{i=0}^n C_n^i$
4. $C^m_{ n } = \frac n m *C^{m-1}_{n-1}$

证明，性质1：从n个不同的元素中取出m个元素，第一种是取n号元素，第二种是不取n号元素。
性质2：从n个不同的元素中取m个元素，剩下的构成一个集合就是n-m个元素，两个集合一一对应。
性质3：从n个元素中取出若干个元素作为一个集合有，0,1,2,3，。。。，n个元素有n+1类方法。另一种是集合每个元素可取可不取一共 $2^n$ 种取法。

二项式定理

$(a+b)^n = \sum_{k=0}^n C_n^ka^kb^{n-k}$

证明
数学归纳法。当n=1时， $(a+b)^1 = C_1^0 a^0 b^{1}+C_1^1 a^1 b^{0} = a+b$
假设n=m时命题成立，当n=m+1时：
$(a+b)^{(m+1)}=(a+b)(a+b)^m=(a+b)\sum_{k=0}^mC_m^ka^kb^{m-k}$
$=\sum_{k=0}^mC_m^ka^{k+1}b^{m-k}+\sum_{k=0}^mC_m^ka^{k}b^{m-k+1}$
$=\sum_{k=1}^{m+1}C_m^{k-1}a^{k}b^{m-k}+\sum_{k=0}^mC_m^ka^{k}b^{m-k+1}$
$=\sum_{k=0}^{m+1}(C_m^{k-1}+C_m^k)a^{k}b^{m-k+1}$
$=\sum_{k=0}^{m+1}C_{m+1}^k a^{k}b^{m+1-k}$

lucas定理

若p是质数，则对于任意整数 $1\leq m\leq n$ ,有：
$C^m_n \equiv C^{n \mod p}_{m \mod p}*C^{n/p}_{m/p}$
将m和n表示成p进制数。，对p进制下的每一位分别计算组合数，最后再乘起来。
不会证明，以后在更新。

如何求组合数

整体分为两种一种是不取模，使用高精度来做求解 $C_n^m$ 。首先使用线筛求出1~n之间所有的质数。 $C_n^m = \frac {n!} {m!(n-m)!}$ 对于三个阶乘，使用阶乘分解然后将剩余的质数使用高精度相乘即可。阶乘分解的时间复杂度是， $O(n\log n)$ 如果某个质数比较小，可以先对几个质数进行乘法，再进行高精度乘法。
第二种是取模的先使用卢卡斯定理，当p是质数的时候，可以将m和n缩小到p的范围内。然后有 $C_n^m = C_{n-1}^m+C_{n-1}^{m-1},O(n^2)$ 的递推式。可以经过预处理后快速回答，范围太局限了。也可以使用逆元求出阶乘和阶乘的逆元，时间复杂度是 $O(n)$ ,然后 $O(1)$ 的时间回答。

多重集

排列数
设 $S=\{n_1a_1,n_2a_2,...,n_ka_k\}$ 这个集合是由 $n_1个a_1,n_2个a_2...$ 组成的多重集合。S的全排列个数为：
$\frac {n!} {n_1! n_2!...n_k!}$
组合数
设 $S=\{n_1a_1,n_2a_2,...,n_ka_k\}$ 这个集合是由 $n_1个a_1,n_2个a_2...$ 组成的多重集合，并且 $r\leq n_i(\forall i\in[1,k])$ 。从s中取出r个元素组成一个多重集，产生的不同多重集的数量为：
$C^{k-1}_{k+r-1}$

证明：首先将这个问题转换为一个更简单的问题。根据前提条件可以知道，每个元素的个数都大于r，所以每个元素的个数都可以看做无穷大。问题可以转换为从a_i中选x_i个数，使得 $\sum _{i=1}^k x_i = r$ ，对于当前的 $a_i$ 来说，我们可以选择他使得 $x_i +1$ 也可以选择下一个 $a_{i+1}$ ,每次从i到i+1过度时，我们使用0代表这个操作。使用1代表选择一个数的操作。那么最后的结果就是选择k-1个0选择r个1组成的全排列有多少中可能。这个就是多重集的排列数
$\frac {(k+r-1)!} {r! (k-1)!} = C^{r}_{k+r-1} = C^{k-1}_{k+r-1}$