排列数
从(n)个元素中取出(m)个元素排成一列,产生的不同排列的数量为:$$P_n^m=dfrac{n!}{(n-m)!}=n(n-1)(n-2)dots(n-m+1)$$
组合数
从(n)个元素中取出(m)个组成一个集合(不考虑顺序),产生的不同集合的数量为:$$C_nm=dbinom{n}{m}=dfrac{n!}{m!(n-m)!}=dfrac{prodlimits_{i=1}{m}{n-i+1}}{prodlimits_{i=1}^m{i}}$$
由于每一种组合有(P_m^m=m!)种不同的排列方式,根据乘法原理,在原来的组合方案上累计每一种方案的排列数,得到:$$C_n^m cdot P_mm=P_nm$$.
组合数有以下三点性质:
1.对称,即(dbinom{n}{m}=dbinom{n}{n-m})
2.递推,即(dbinom{n}{m}=dbinom{n-1}{m}+dbinom{n-1}{m-1})
3.求和,即(sumlimits_{i=0}^ndbinom{n}{i}=2^n)
第一点,选择(m)种元素等价于放弃另外(n-m)种元素,那么从"放弃集合"中选取(n-m)种元素的方案数和从"选择集合"中选取(m)种元素的方案数一致.
第二点,当选到最后的第(n)个元素时,我们可以选择选或不选.
如果不选,那么我们就必须在前(n-1)个元素里选出(m)个元素.方案数为(dbinom{n-1}{m}).
如果选,那么我们只需要在前(n-1)个元素里选出(m-1)个元素.方案数为(dbinom{n-1}{m-1}).
两种决策合并到一起,就有(dbinom{n}{m}=dbinom{n-1}{m-1}+dbinom{n-1}{m}).
第三点,我们直接用集合的子集划分来证明.考虑一下,如何求一个大小为(n)的集合的子集个数?
对于每一个含有(i)个元素的子集,这样的子集应该有(dbinom{n}{i})个.
子集的大小可以是(0,1,dots,n),那么对应的子集个数就是(sumlimits_{i=0}^ndbinom{n}{i}).
从另一方面,对于集合第(j)个元素,我们可以决定选或者不选.这样一共有两种决策可以形成不同的子集.
总共有(n)个元素,由乘法原理,可以形成不同的子集个数为(prodlimits_{i=1}^n2=2^n)
这两种方案数应该是一样的,即(sumlimits_{i=0}^ndbinom{n}{i}=2^n)
组合数的计算方法
如果需要一系列的组合数值,我们可以用线性递推的公式.边界是(dbinom{n}{0}=dbinom{n}{n}=1)
如果计算的值比较大,而答案要求对某个数取模,我们有Lucas定理.
除此之外,我们还可以保存一下模意义下的阶乘和它的逆元,然后用(O(1))的时间套公式回答.
我们还可以用"阶乘质因式分解"的方法来避免大数除法,时间复杂度为(O(nlog n)).
二项式定理
注意到((a+b)^n=(a+b)(a+b)^{n-1}=a(a+b)^{n-1}+b(a+b)^n).这意味着对于乘积(egin{matrix}underbrace{(a+b)(a+b)(a+b)dots(a+b)}\n ext{个项}end{matrix}),我们每次从一个项中可以选择(a)或者选择(b),相乘得到一个(n)次的整式.这样的整式一共有(2^n)个,合并同类项之后就只有(n+1)个了.
试问:整式(a^kb^{n-k})一共有多少个呢?我们从(n)个项里面选出(k)个(a),可以选出(dbinom{n}{k})个(a^kb^{n-k})出来.((a+b)^n)展开之后所有的项一定是(a^kb^{n-k})或者(a^{n-k}b^k)的形式,每一个项的个数(dbinom{n}{k}),故(sumlimits_{i=0}^ndbinom{n}{i}a^ib^{n-i}=(a+b)^n).
这种思想还可以在这里进一步了解。
还可以用数学归纳法.
当(n=1)时,((a+b)^1=a+b=dbinom{1}{0}a^0b^{1-0}+dbinom{1}{1}a^1b^{1-1}),成立.
若命题对(n=m)成立,则对(n=m+1):
((a+b)^{m+1}=(a+b)(a+b)^m=(a+b)sumlimits_{i=0}^mdbinom{m}{i}a^ib^{m-i})
(=sum_{i=0}^mdbinom{m}{i}a^{i+1}b^{m-i}+sum_{i=0}^mdbinom{m}{i}a^ib^{m-i+1})
(=sum_{i=1}^{m+1}dbinom{m}{i-1}a^ib^{m-i+1}+sum_{i=0}^mdbinom{m}{i}a^ib^{m-i+1})
(=sum_{i=0}^{m+1}(dbinom{m}{i-1}+dbinom{m}{i})a^ib^{m-i+1}=sum_{i=0}^{m+1}dbinom{m+1}{i}a^ib^{m+1-i}).
证毕.
多重集
多重集不满足互异性。多重集中每个元素可以用(n cdot x)来表示，代表(x)在多重集中出现了(n)次。
多重集的（全）排列。我们把多重集中的全部元素（包括重复的元素）拿出来排成一个序列。两个多重集的排列不同，当且仅当两个排列的对应某位置上，它们的元素不同。比如说，({a,a,b,b,a,c,d})和({a,a,b,b,a,c,d})是同一个排列，而和({a,b,a,b,a,c,d})就不是。
多重集的组合。我们从多重集中选取若干个元素（可以重复选取同一元素，但次数不能超过原来多重集中的个数），得到一个新的多重集。两个多重集不同，当且仅当他们对应元素的个数不相等。({a,a,b,b,c,c,d})和({a,b,a,b,c,c,d})代表同一个多重集的组合，而和({b,b,b,b,c,c,d})则不是。
我们假定多重集的大小(N=|S|=sum_{i=1}^kn_i)。
多重集的排列数
如果把多重集中每一个重复的元素标上不同的序号，那么我们就可以把原来的多重集(S={n_1cdot a_1,n_2cdot a_2,cdots,n_kcdot a_k})看成是一个长度为(N)的序列({a_{11},a_{12},cdots,a_{1n_1},a_{21},a_{22},cdots,a_{2n_2},cdots,a_{kn_k}})。这个序列的排列数是(N!)。
另一方面，我们不考虑标号。我们假设直接对整个多重集进行全排列，得到集合(S)的全排列(P(S))。假如同一种元素调换位置，多重集的排列是不会变的，但是上面的序列的排列会不一样。在多重集排列的基础上，对每种元素进行全排列，可以得到不同的序列排列。每种元素对应的全排列数是(n_i!)，我们得到了等式:
即：
多重集的组合数
已知多重集(S={n_1cdot a_1,cdots,n_kcdot a_k})。现从多重集中随意选取(r)个元素组成一个新的多重集，满足(forall i=1,2,cdots,k,rleq n_i)。求不同的新多重集的方案数。
假设我们取(v_i)个(a_i)元素，那么组成的多重集应当满足(sumlimits_{i=1}^kv_i=r)。那么新的问题就是要求满足上述条件的向量(v)的个数。
以下做法参考至李煜东老师《算法竞赛进阶指南》。我们不妨考虑一个长度为(r)的面包：
我们把这个面包切(k-1)刀变成(k)个面包条，每一个面包条的长度对应一个(v_i)的值，这样就得到了一种合法的方案。
(uparrow)这里把一个长度为(r=11)的面包切成了(4)条，对应的(v=<3,3,4,1>)。
我们可以切在不同的位置，从而得到不同的方案，每一种均满足(sum_{i=1}^kv_i=r)。因此，我们要求的答案就是所有可行的切面包方案，也就是所有可行的刀痕排列。
把长度为(1)的面包块(Box)和刀痕(dagger)都看成元素，它们构成多重集({rcdot Box,(k-1)cdot dagger})。这个多重集的排列数等于(dfrac{(r+k-1)!}{r!(k-1)!}=dbinom{r+k-1}{k-1})。所以多重集(S={n_1cdot a_1,cdots,n_kcdot a_k})的组合数就是(dbinom{r+k-1}{k-1})。
如果不满足(forall i=1,2,cdots,k,rleq n_i)，而是(r leq N)，我们就需要用到容斥原理来解决。