普通计数原理
首先接触一个常用的玩意
A(n,k)表示n个数中取k个数的排列。
C(n,k)表示n个数中取k个数的组合。
接下来是在高中课程中的A与C的常见公式：
A(n,k)=n*(n-1)*(n-2)*(n-3)*……*(n-k+1)
C(n,k)=A(n,k)/A(k,k)=n!/(k!*(n-k)!)
这两个公式的意义都是很容易得到的就不再证明了。
接下来是一些在OI中常用（或者有点玄学）的方法（东西）。
C(n,k)=C(n-1,k-1)+C(n-1,k)（pascal公式）
这个公式由于难以计算（列表）很难在数学中应用，但是却由于满足递归而在OI界比较方便。
可以直接写递归程序来计算C，时间复杂度为O(n+k)。在n与k不大的时候可以尝试使用。而且加法很方便取模不，会溢出。如果使用乘法可能会溢出，而且还需要求逆元。所以这不失为一种好方法。
当然这是杨辉三角——也可以先打表计算C的值，可以防止栈溢出（不过如果会栈溢出的时候估计也不会用这个做了）。
C(n,k)=pai(C(ni,ki)) mod p，（pai为连乘符号）其中ni与ki是n与k在p进制下各个位上上的数，p为素数。
例如求C(11,2) mod 3的值
C(11,2) mod 3=11*10/2 mod 3=55 mod 3=1
2(10)=002(3)
11(10)=102(3)
所以
C(11,2) mod 3
=C(1,0)（第一位）*C(0,0)（第二位）*C(2,2)（第三位） mod 3=1
所以现在我们便可以通过Lucas定理来计算C(n,k)
一个简单的想法就是
C(n,k) mod p=C(n mod p,k mod p)*C(n div p,k div p) mod p
这就可以递归做下去了。
这适用于n与k很大但是p很小的情况。时间复杂度O(log(p)n)。
（Lucas定理可以通过中国剩余定理来扩展，未写完以后补上）
C(a,b)*C(b,c)=C(a,c)*C(a-c,b-c)
虽然一般用不到这个式子，但是如果出现连乘的时候，例如用Lucas，还是可以用这个来优化的。
因为这会不断的减小组合数中两个数的大小规模——可能最后是可以用杨辉三角来解决，就可以避免一些溢出之类的东西。
n个数中取出k个不相邻的数：C(n-k+1,k)
n个数中取出k个允许重复的数：C(n+k-1,k-1)
（有点显然，不过还是想有时间再证明）
错位排列（1到i的全排列中，元素i不放在i的位置的排列数）：D(n)=(n-1)*(D(n-1)+D(n-2)),D(1)=0,D(2)=1
我们考虑新加入的元素n放在哪。
显然n只要不放在最后一位就可以了。所以这是有C(n-1,1)=n-1中方法的。
假设n放到了p位置。不管p放到哪一个位置，其错位排列都是一样多的。所以设D(n)=(n-1)*a。不妨设p=1。
若1放到了位置n，那么剩下的就是n-1个数的错位排列了。
若1没有放到n，不管1放到哪一位，其错位排列数都是一样多的。不妨设1放到了2号位。这样剩下的就是n-2个数的错位排列。
所以a=D(n-1)+D(n-2)
（感觉好牵强的伪证法，我想可能自己表述不清楚，不过OI是一门应用学而不是理论学。让数学组的来解释吧（虽然浅尝辄止也不是OIer该有的品质哈））
卡特兰数
卡特兰数有四个表达公式：
C(n)
=C(2n,n)/(n+1)
=sigma(C(i)*C(n-i-1))
=C(n-1)*(4n-2)/(n+1)
=C(2n,n)-C(2n,n+1)
可以尽量挑选一些适合的公式来使用。
（有时间再证明）
斯特林数与贝尔数
第一类斯特林数：将p个元素排成k个非空循环的方案数
s(p,k)=s(p-1,k-1)+(p-1)*s(p-1,k)
s(p,0)=0,s(p,p)=1
第二类斯特林数：将p个元素划分为k个非空组的方案数
S(p,k)=S(p-1.k-1)+k*S(p-1,k)
S(p,0)=0,S(p,p)=1
贝尔数：将p个元素划分为若干非空组的方案数
B(p)=sigma(S(p,k))
=sigma(k=0,n-1)(C(n-1,k)*B(n-k-1))
（有时间再证明）