基本概念

加法原理：完成一个工程有n类方法，每类个方法，一共有种方法。
乘法原理：完成一件事要n个步骤，每个步骤个方法，一共有种方法。
排列数：从n个不同的元素中依次取出m个元素排成一列，产生的不同排列的数量为

组合数：从n个不同的元素中取出m个组成一个集合(不考虑顺序)，产生的不同集合数量为

不过现在更多人用这种形式表达
当m>n时
组合数的性质
1.
2.
3.
4.

---

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

二项式定理

---

证明
数学归纳法。当n=1时，
假设n=m时命题成立，当n=m+1时：

---

lucas定理

若p是质数，则对于任意整数,有：

将m和n表示成p进制数。，对p进制下的每一位分别计算组合数，最后再乘起来。
不会证明，以后在更新。

如何求组合数

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

多重集

排列数
设这个集合是由组成的多重集合。S的全排列个数为：

组合数
设这个集合是由组成的多重集合，并且。从s中取出r个元素组成一个多重集，产生的不同多重集的数量为：

---

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