<更新提示>
<第一次更新>
<正文>
基础知识
加法原理
若完成一件事情的方法有(n)类，其中第(i)类方法包括(a_i)种不同的方法，且这些方法互不重合，那么完成这件事共有(sum a_i)中不同的方法。
乘法原理
若完成一件事情需要(n)个步骤，其中第(i)个步骤有(a_i)种不同的完成方法，且这些步骤互不干扰，那么完成这件事共有(prod a_i)中不同的方法。
排列数
从(n)个不同元素中依次取出(m)个元素排成一列(在乎顺序)，产生的不同排列的数量为：
组合数
从(n)个不同元素中取出(m)个组成一个集合(不在乎顺序)，产生的不同集合数量为：
组合数的性质
(1. C_n^m=C_n^{n-m})
证明：
由组合数的定义，对于从(n)个元素中取出(m)个构成的集合，剩余的元素也恰好构成了一个集合，两个集合一一对应，故产生的集合数量也相同，性质成立。
(2. C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1})
证明：
从(n)个不同元素取出(m)个数组成一个集合有两类方法：取(n)号元素，不取(n)号元素。取(n)号元素时，则在(n-1)个元素中还取了(m-1)个数，有(C_{n-1}^{m-1})种取法。不取(n)号元素时，则在(n-1)个元素中取了(m)个元素，有(C_{n-1}^m)种取法，故性质成立。
(3. sum_{i=0}^nC_n^{i}=2^n)
证明：
从(n)个元素中取出若干个元素组成一个集合，有(n+1)类方法，即分别取出(0,1,2,...,n)个元素，其方案数分别对应(C_n^1,C_n^2,...,C_n^n)。从另一方面看，每一个元素有取或不取两种选择，方案数为(2^n)，所以性质成立。
常见拓展知识
二项式定理
证明：
利用数学归纳法，当(n=1)时，((a+b)^1=C_n^0a^0b^1+C_n^1a^1b^0=a+b)成立。
若(n=p)时命题成立，则(n=p+1)时：
故原命题成立。
多重集排列数
多重集指含有重复元素的广义集合。设多重集(S={n_1*a_1,n_2*a_2,...,n_k*a_k})是由(n_1)个(a_1)，(n_2)个(a_2)，(...)，(n_k)个(a_k)组成的集合，则(S)的全排列个数为$$frac{(sum_{i=1}^k n)!}{prod_{i=1}^k(n_i!)}$$
证明：
对于朴素全排列，显然有((sum_{i=1}^k n)!)种方案，而在多重集的排列过程中，每个(a_i)出现了(n_i)次，在这(n_i)个位置间各个(a_i)可以互相调换位置，有(n_i!)中方案，故除去每一个(n_i)可以调换位置的重复方案即为总排列数。
多重集的组合数
设多重集(S={n_1*a_1,n_2*a_2,...,n_k*a_k})是由(n_1)个(a_1)，(n_2)个(a_2)，(...)，(n_k)个(a_k)组成的集合，对于(rleq n_i (forall i in [1,k]))，从(S)中取出(r)个元素组成一个多重集，产生不同的多重集数量为$$C_{k+r-1}^{k-1}$$
证明：
该问题等价于统计如下集合的数量：({x_1*a_1,x_2*a_2,...,x_k*a_k})，其中(sum_{i=1}^kx_i=r)。故原问题等价于多重集({r*0,(k-1)*1})的全排列数，即类似于插板法，每连续的一串(0)代表元素(a_1)的个数，使用(k-1)个(1)将(r)个(0)分成(k)部分。利用多重集的排列数公式可得方案数为(C_{k+r-1}^{k-1})。
Lucas定理
(Lucas)定理：(p)为质数时，(C_n^mequiv C_{n mod p}^{m mod p}*C_{n/p}^{m/p}(mod p))。
证明：
预备和引理
(1.)费马小定理：(p)为质数时，有(aequiv a^p(mod p))。
(2.)二项式定理：((a+b)^n=sum_{k=0}^nC_n^{k}a^{k}b^{n-k})。
(3.)引理：(p)为质数时，有((1+x)^pequiv 1+x^p(mod p))。
证明： 由费马小定理可得((1+x)^pequiv 1+x(mod p))，又因为(xequiv x^p(mod p))，则可得((1+x)^pequiv 1+x^p(mod p))。
(4.)引理：((1+x)^n)第(m)项的系数即为(C_n^m)。
证明： 由二项式定理展开可得。
主体证明
对于((1+n)^p)，分解指数得： $$(1+x)^nequiv (1+x)^{lfloor frac{n}{p} floor p}(1+x)^{n mod p}(mod p)$$ 利用引理(3)，可得： $$(1+x)^nequiv(1+x^p)^{lfloor frac{n}{p} floor}(1+x)^{n mod p}(mod p)$$ 二项式定理展开，得： $$(1+x)^nequivsum_{i=0}^{lfloor frac{n}{p} floor}C_{lfloor frac{n}{p} floor}^ix^{pi}sum_{j=0}^{n mod p}C_{n mod p}^jx^j$$ 当且仅当(pi+j=m)时，(x)指数为(m)，故(i=lfloor frac{p}{m} floor,j=p mod m)。 而此时(x^m)的系数为$$C_{lfloor frac{n}{p} floor}^{lfloor frac{p}{m} floor}C_{p mod n}^{p mod m}$$ 所以(C_n^mequiv C_{lfloor frac{n}{p} floor}^{lfloor frac{p}{m} floor}*C_{p mod n}^{p mod m}(mod p))，证毕。
Catalan数列
给定(n)个(0)和(n)个(1)，将他们排成长度为(2n)的序列，满足任意前缀中(0)的个数都不少于(1)的个数的排列的数量为$$Cat_n=frac{C_{2n}^n}{n+1}$$
证明：
对于(n)个(0)和(n)个(1)任意排成的一个序列(S)，若(S)不满足要求，则必然存在一个最小位置(2p+1in[1,2n])，使得(S[1,2p+1])中存在(p)个(0)，(p+1)个(1)，那么将(S[2p+2,2n])这一部分取反，就可以得到由(n-1)个(0)和(n+1)个(1)排成的序列。
同理，对于一个(n-1)个(0)和(n+1)个(1)随意排成的一个序列(S')，也必定存在一个最小的位置(2p'+1)，使得(S'[1,2p'+1])中有(p')个(0)，(p'+1)个(1)，那么将(S'[2p'+2,2n])这一部分取反，也能得到由(n)个(0)和(n)个(1)排成的一个序列，并且存在前缀(1)比(0)多的位置。
由上可知，每个不符合要求的序列和每一个由(n-1)个(0)和(n+1)个(1)排成的序列呈一一对应关系，根据组合数的定义，后者显然有(C_{n2}^{n-1})个，那么符合要求的序列就有
(Catalan)数还有如下的计算公式：
其他有关(Catalan)数，可以看Miskcoo's Space的博客。
<后记>