排列与组合

排列的定义与基本性质

定义 设一个集合 S 中有 n 个元素，从中有序地取出 m(0≤m≤n) 个元素排成一列， 称为 S 的一个 m 排列。两个排列相同，当且仅当元素相同且顺序相同。我们记 Pmn 、 Amn 或 P(n,m) 表示 S 中 m 排列的总数。

约定 当 m>n 时，Pmn=0 。

全排列的定义 设一个集合 S 中有 n 个元素，其 n 排列称为全排列。

• C++中，next_permutation 函数可以按字典序从小到大遍历数据的全排列，prev_permutation 函数与之相反。

性质1 Pmn=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)! ，其中 0≤m≤n。

性质2 Pmn=nPm−1n−1 。

性质3 Pmn=mPm−1n−1+Pmn−1 。

性质1的证明：

考虑乘法原理，按顺序选数，第 i(1≤i≤m) 个数有 n−i+1 种选法，乘在一起可得原式。

性质2的证明：

考虑乘法原理，第一个数有 n 种选法，再从剩下的 n−1 个数里选 m−1 个有 Pm−1n−1 种排列，所以 Pmn=nPm−1n−1 。

性质3的证明：

考虑加法原理，考虑分两类：

1. 先指定选一个元素，有 m 个位置可放，再从剩下 n−1 元素中选 m−1 个有 Pm−1n−1 种排列。
2. 不选1指定的元素，从其他 n−1 元素里选 m 个，共 Pm−1n 种排列。

因此 Pmn=mPm−1n−1+Pmn−1 。

错位排列的定义与基本性质

定义 设 P=(p1,p2,⋯,pn) 是 S={1,2,⋯,n} 的一个排列，若对于任意的 i∈[1,n] 满足 pi≠i ，则称 P 是 S 的一个错位排列。我们记 Dn 表示 S 的错位排列的总数。

性质1 Dn 有递推公式

性质2 Dn 有通项公式 Dn=n!n∑k=0(−1)kk! 。

性质3 Dn 有简单表达式 Dn=⌊n!e⌋ 。

性质4 {1,2,⋯,n} 的排列是错位排列的概率 Pn 有渐进 limn→∞Pn=limn→∞Dnn!=1e ，表明 Dn 的增长率与 n! 仅相差常数倍。

性质1的证明：

考虑加法原理，设 n 出现在位置 k(1≤k≤n−1) ，有两种情况：

1. k 一定出现在位置 n ，那么除去 k,n 剩下 n−2 个数错排即可，共计 Dn−2 。
2. k 不能出现在位置 n ，那么可把位置 n 视作 k 的新位置与除了 n 的数进行错排，共计 Dn−1 。

因此再根据乘法原理，有 Dn=(n−1)(Dn−1+Dn−2) 。

性质2的证明：

考虑减法原理，设全集 U 为 [1,n] 的全排列，则 |U|=n! ，设满足 pi≠i 的排列的集合为 Si ，那么满足 pi=i 的集合为 ¯Si ，那么有 |n⋂i=1Si|=|U|−|n⋃i=1¯Si| ，问题转换为求 |n⋃i=1¯Si| 。

考虑容斥原理，有 |n⋃i=1Si|=n∑k=1(−1)k−1∑1≤i1<i2<⋯<ik≤n|k⋂j=1Sij| ，其中 |k⋂j=1Sij| 为所有 i∈T 满足 pi=i 的排列数，显然为 (n−k)! ，对于 1≤i1<i2<⋯<ik<n 共有 (nk) 种方案，因此 |n⋃i=1Si|=n∑k=1(−1)k−1(nk)(n−k)!=n∑k=1(−1)k−1n!k! 。

最后，错位排列数 |n⋂i=1Si|=|U|−|n⋃i=1¯Si|=n!−n∑k=1(−1)k−1n!k!=n!n∑k=0(−1)kk! 。

圆排列的定义与基本性质

定义 设一个集合 S 中有 n 个元素，从中有序地取出 m(0≤m≤n) 个元素排成不分首尾围成一圈， 称为 S 的一个 m 圆排列。两个圆排列相同，当且仅当元素相同且不分首位地顺序相同。我们记 Qmn 表示 S 的 m 圆排列的总数。

性质1 Qmn=Pmnm 。

性质1的证明：

对于每一种圆排列，我们可以规定首尾使其变成标准排列，共有 m 种首尾方案，因此有 Qmn⋅m=Pmn ，所以 Qmn=Pmnm 。

多重集排列

多重集排列的定义与基本性质

定义 设多重集 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} ，从中任选 m 个元素组成排列，称为 S 的 m 排列。

多重组合数的定义 设多重集 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} ， n=k∑i=1ni ，则 S 的 n 排列（即全排列）的总数称为多重组合数，记为 (nn1,n2,⋯,nk) 。

性质1 设多重集 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} ，n=k∑i=1ni ，则全排列数为 (nn1,n2,⋯,nk)=n!k∏i=1ni! 。

性质2 设多重集 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} ，若 m 满足 m≤n≤+∞(1≤i≤k) ，则 m 排列数为 km 。

性质1的证明：

不考虑元素重复的全排列为 n! ，再对每个元素的全排列 ni!(1≤i≤k) 去重，所以 (nn1,n2,⋯,nk)=n!k∏i=1ni! 。

性质2的证明：

因为选 m 个小于等于任意元素的个数，所以每次都能选 k 个元素，因此总数为 km 。

组合的定义与基本性质

定义 设一个集合 S 中有 n 个元素，从中无序地取出 m(0≤m≤n) 个元素组成集合， 称为 S 的一个 m 组合。两个组合相同，当且仅当元素相同。我们记 Cmn 、 (nm) 或 C(n,m) 表示 S 中 m 组合的总数。

约定 当 m>n 时，(nm)=0 。

性质1 (nm)=Pmnm!=n!m!(n−m)! 。

性质2 (nm)=(nn−m) 。

性质3 (nm)=n−m+1m(nm−1) 。

性质4 (nm)=nm(n−1m−1) 。

性质5（杨辉三角） (nm)=(n−1m)+(n−1m−1) 。

性质6 n∑i=0(im)=(n+1m+1) 。

性质7 (nm)(mk)=(nk)(n−km−k) 。

性质8 n∑i=0(n−ii)=Fn+1 ，其中 F 是斐波那契数列。

性质1的证明：

先考虑顺序得到的总数为 m 排列数 Pmn ，而对于一种 m 组合有 m! 种排列方式，所以 m!(nm)=Pmn ，因此根据排列性质1可得 (nm)=Pmnm!=n!m!(n−m)! 。

性质2的证明：

由性质1易得。

n 个里选 m 个组合，等价于 n 个里选 n−m 不在组合。

性质5的证明：

由性质1易得。

画出杨辉三角，由数学归纳法易得。

指定一个元素，如果一定不选它则有 (n−1m) 种组合，如果一定选它则有 (n−1m−1) 种组合，考虑加法原理，得证。

性质6的证明：

根据性质5可得

n∑i=0(im)=n∑i=m(im)=(m+1m+1)+(m+1m)+(m+2m)+⋯+(nm)=(m+2m+1)+(m+2m)+⋯+(nm)=(m+3m+1)+⋯+(nm)=(n+1m+1)

从 [0,n] 的整数中选出 m+1 个数的组合数为 (n+1m+1) ，在这些组合中最大数为 i(0≤i≤n) 的组合数为 (im) ，考虑加法原理得证。

性质7的证明：

由性质1可得

(nm)(mk)=n!m!(n−m)!⋅m!k!(m−k)!=n!k!⋅1(m−k)!(n−m)!=n!k!(n−k)!⋅(n−k)!(m−k)!(n−m)!=(nk)(n−km−k)

左式是正着选，从 n 个元素中选 m 个，对于每个 m 组合再选 k 个的 k 组合的总数的总和。

右式是倒着选，先从 n 个元素中选 k 个，对于每个 k 组合从剩下 n−k 个元素中再选 m−k 个元素，代表这个 k 组合会被所有 m 组合选到的次数，最后总和与左式意义等价。

性质8的证明：

设 Gn=n∑i=0(n−ii) ，则 G0=1=F1,G1=1=F2 。

假设当 n=k+1(k≥0) 时， Gk=Fk+1,Gk+1=Fk+2 成立。

那么当 n=k+2 时，由性质5可得

Gk+Gk+1=k∑i=0(k−ii)+k+1∑i=0(k+1−ii)=k+1∑i=1(k−i+1i−1)+k+1∑i=1(k+1−ii)+1=k+1∑i=1((k+1−ii−1)+(k+1−ii))+1=k+1∑i=1(k+2−ii)+(k+20)+(0k+2)=k+2∑i=0(k+2−ii)=Gk+2

同时有 Gk+Gk+1=Fk+1+Fk+2=Fk+3 ，因此 Gk+1=Fk+2,Gk+2=Fk+3 ，得证。

二项式定理

定理1（二项式定理） (x+y)n=n∑i=0(ni)xn−iyi 。

• 推论1（定理1的推论） n∑i=0(ni)=2n 。

• 推论2（定理1的推论） n∑i=0(−1)i(ni)=[n=0] 。

• 推论3（推论2的推论） (n0)+(n2)+⋯=(n1)+(n3)+⋯=2n−1 ，其中 n≥1 。

定理2（扩展二项式定理） (k∑i=1xi)n=∑n1+n2+⋯+nk=n(nn1,n2,⋯,nk)k∏i=1xnii 。

广义组合数的定义 设 α∈R,m∈N ，则 (αm)=m∏i=0(α−i)m! 。

定理3（广义二项式定理） (x+y)α=∞∑i=0(αi)xα−iyi ，其中 α∈R 。

定理1的证明：

当 n=0 时显然得证。

假设当 n=k 时， (x+y)k=k∑i=0(ki)xk−iyi 成立。

当 n=k+1 时，根据组合基本性质5有

(x+y)k+1=(x+y)k∑i=0(ki)xk−iyi=xk∑i=0(ki)xk−iyi+yk∑i=0(ki)xk−iyi=k∑i=0(ki)xk+1−iyi+k+1∑i=1(ki−1)xk−i+1yi=(k0)xk+1+k∑i=1(ki)xk+1−iyi+k∑i=1(ki−1)xk−i+1yi+(kk)yk+1=(k0)xk+1+k∑i=1(k+1i)xk+1−iyi+(k+1k+1)yk+1=k+1∑i=0(k+1i)xk+1−iyi

于是得证。

我们枚举 x,y 的指数 i,j 满足 i+j=n 的情况，等价于枚举 i(0≤i≤n) 得到 j=n−i 。对于一个 i 的情况，需要求在 n 个 (x+y) 括号中有 i 个选 x 和 n−i 个选 y 的方案数。

我们可以 n 选 i 后 n−i 选 n−i 共 (ni)(n−in−i)=(ni) 种方案。

当然，我们也可以理解为一个多重集的模型，有 i 个选 x 的 (x+y) 和 n−i 个选 y 的 (x+y) ，选择相同的 (x+y) 算相同的元素，不同的顺序算不同的方案，所以是求有限多重集的全排列数，为 (ni,n−i)=(ni) 种方案。

因此 (x+y)n=n∑i=0(ni)xn−iyi 。

定理2的证明：

同样可以使用归纳法，但比较复杂，我们使用定理1的证法2，即组合意义证明。

我们枚举 xi(1≤i≤k) 的指数 ni 满足 n1+n2+⋯+nk=n 的情况。对于一组非负整数解 n1,n2,⋯,nk ，需要求在 n 个 (x1+x2+⋯+xk) 括号中有 ni(1≤i≤k) 个括号内选了 xi 的方案数。

我们设多重集有 ni(1≤i≤k) 个选 xi 的 (x1+x2+⋯+xk) ， 其全排列数为 (nn1,n2,⋯,nk) 。

因此 (k∑i=1xi)n=∑n1+n2+⋯+nk=n(nn1,n2,⋯,nk)k∏i=1xnii 。

范德蒙德卷积

定理1（范德蒙德卷积） k∑i=0(ni)(mk−i)=(n+mk) 。

• 推论1（定理1的推论） r∑i=−s(ni+s)(mr−i)=(n+ms+r) 。
• 推论2（定理1的推论） n∑i=0(ni)(ni−1)=(2nn−1) 。
• 推论3（定理1的推论） n∑i=0(ni)2=(2nn) 。
• 推论4（定理1的推论） m∑i=0(ni)(mi)=(n+mm) 。

定理1的证明：

由二项式定理的定理1可得

n+m∑k=0(n+mk)xk=(1+x)n+m=(1+x)n(1+x)m=(n∑i=0(ni)xi)(m∑j=0(mj)xj)=n∑i=0m∑j=0(ni)(mj)xi+j=n+m∑k=0k∑i=0(ni)(mk−i)xk

根据待定系数法 xk 的系数相同，可得 k∑i=0(ni)(mk−i)=(n+mk) 。

一个集合有 n+m 个元素，从中选 k 个元素的方案数为 (n+mk) 。

其等价于，将集合分成 n,m 两部分，从 n 中选 i(0≤i≤k) 个再从 m 中选 k−i 个，共 k∑i=0(ni)(mk−i) 种方案。

推论1的证明：

由定理1简单变换可得

k∑i=0(ni)(mk−i)=k−r∑i=−r(ni+r)(mk−i−r)=s∑i=−r(ni+r)(ms−i)=(n+ms+r)

于是得证。

推论2的证明：

由定理1简单变换可得

n∑i=0(ni)(ni−1)=n∑i=0(ni)(nn−i+1)=(2nn+1)=(2nn−1)

于是得证。

推论3的证明：

由定理1简单变换可得

n∑i=0(ni)2=n∑i=0(ni)(nn−i)=(2nn)

于是得证。

推论4的证明：

由定理1简单变换可得

n∑i=0(ni)(mi)=n∑i=0(ni)(mm−i)=(n+mm)

于是得证。

在 n×m 的网格图上，从 (0,0) 走到 (n,m) ，只能向右或者向下走，有多少方案。

显然会向右走 m 步和向下走 n 步共 n+m 步，所以方案数是 (n+mm)(nn)=(n+mm) 。

其等价于，将 n+m 步分为 n,m 步，在 n 步中选 i(0≤i≤m) 步向右，然后在 m 步选 m−i 步向右，有 m∑i=0(ni)(mi) 种方案。

卢卡斯定理

定理1（卢卡斯定理） 若 p 是质数，则 (nm)≡(nmodpmmodp)(⌊n/p⌋⌊m/p⌋)(modp) 。

• 推论1（定理1的推论） 若 p 是质数，整数 n,m(0≤m≤n) 的 p 进制表达分别为 n=akak−1⋯a0,m=bkbk−1⋯b0 ，其中 ai,bi∈[0,p)(0≤i≤k) ，则 (nm)≡k∏i=0(aibi)(modp) 。

定理1的证明：

先证明 (x+y)p≡xp+yp(modp) ，其中 p 为素数。

考虑二项式 (x+y)p ，根据二项式定理有 (x+y)p=p∑i=0(pi)xp−iyi ，其中 (pi)=p!i!(p−i)! ，显然当且仅当 i=0 或 i=p 时 (pi) 没有质因子 p 且此时值为 1 ，因此 (pi)≡[i=0∨i=p](modp) ，所以 (x+y)p≡xp+yp(modp) 。

现在我们证明定理。

考虑二项式 (1+x)n ，我们有

(1+x)n≡(1+x)p⌊n/p⌋(1+x)nmodp≡(1+xp)⌊n/p⌋(1+x)nmodp≡(⌊n/p⌋∑i=0(⌊n/p⌋i)xip)(nmodp∑j=0(nmodpj)xj)≡⌊n/p⌋∑i=0nmodp∑j=0(⌊n/p⌋i)(nmodpj)xip+j(modp)

其中 j∈[0,nmodp],nmodp<p ，那么不会有同一组 (i,j) 使得 ip+j 相等，因此和式里的系数就是 xip+j 的系数。

根据二项式定理 (1+x)n=n∑i=0(ni)xi ， xm 的系数为 (nm) 。在模 p 下，令 ip+j=m 有 i=⌊mp⌋,j=mmodp ， xm 的系数为 (nmodpmmodp)(⌊n/p⌋⌊m/p⌋) 。因此，根据待定系数法可得， (nm)≡(nmodpmmodp)(⌊n/p⌋⌊m/p⌋)(modp) 。

推论1的证明：

把定理1的 n,m 持续递推，发现每次得到的都是 p 进制下的数位，因此得证。

组合数的求法

根据性质5可得加法递推公式 (nm)=(n−1m)+(n−1m−1) ，依次递推可得 0≤m≤n 的所有组合数。

这个递推在模数为素数时，完全可以被公式法替代，其他情况可以考虑使用。

时间复杂度 O(n2)

空间复杂度 O(n2)

根据性质3可得乘法递推公式 (nm)=n−m+1m(nm−1) ，可以直接求确定 n 的组合数，注意先乘法后除法。

可以利用性质2 (nm)=(nn−m) 去掉一半计算量。

当我们无法保存加法递推的所有组合数，但只需要一行组合数时，可以考虑此法。

注意此法不可直接取模，并且取模情况可以由公式法直接替代。

时间复杂度 O(n)

空间复杂度 O(n)

公式法是组合数取素数模时最好的解法，其利用逆元处理除法求 (nm)=n!m!(n−m)! ，可以在线性时间内处理出 0≤m≤n 的所有组合数。

公式法在复杂度上优于加法递推，与乘法递推相同；在使用范围上与加法递推相同，优于乘法递推，可以完全替代前两个方法。

时间复杂度 O(n)

空间复杂度 O(n)

卢卡斯定理

在模数为不大的素数，但 n 很大时，可以考虑用卢卡斯定理 (nm)≡(nmodpmmodp)(⌊n/p⌋⌊m/p⌋)(modp) 分解组合数，再利用公式法求解。

时间复杂度 O(p+logn)

空间复杂度 O(n)

扩展卢卡斯定理

扩展卢卡斯定理解决了卢卡斯定理无法解决的非素数模数情况，其主要利用了CRT将问题分解，又通过威尔逊定理相关解决了质数幂模数的组合数求模问题。

我们先将问题分解为多个质数幂的模，因为模数互质，所以最后可以用CRT合并，于是有

{(nm)≡a1(modpα11)(nm)≡a2(modpα22)⋮(nm)≡ak(modpαkk)

接下来我们要求出 k 个方程中的 ai 。

不妨我们考虑其中一个方程 (nm)≡n!m!(n−m)!≡a(modpα) ，我们可以对各个阶乘取模后合并，其中分母取逆元。

注意到阶乘可能含有因子 p ，可能导致结果为 0 或者无法求逆元，但实际上在分式中因子 p 会被消除，因此我们可以考虑先将 p 因子全部提出，再对除去所有 p 因子的阶乘求模，于是有 n!vp(n!)m!vp(m!)⋅(n−m)!vp((n−m)!)⋅px−y−z≡a(modpα) 。

不妨考虑 n!vp(n!) 的求法，根据威尔逊定理的推论1有 n!vp(n!)≡(±1)⌊n/pα⌋⌊n/p⌋!vp(⌊n/p⌋!)((nmodpα)!)p(modpα) ，其中 ±1 的判定根据威尔逊定理的定理5即可， ((nmodpα)!)p 可以预处理，于是我们可以递归求解。但这是尾递归，我们可以改为迭代形式。因此，我们将分式三部分的余数求完，对分母取逆元变为乘法， px−y−z 利用快速幂求解，最后相乘即可求出 a 。

最后，求完 k 个方程的余数后，我们通过CRT合并。

这个过程证明相当复杂，初学者可以学个板子略过了。

时间复杂度 O(∑i(logpin+logpi+pαii))

空间复杂度 O(max{pαii})

枚举质因子重数

对于不取模的大组合数，直接使用高精度乘除法的复杂度比较大，因此考虑先求出质因子的幂次，再高精度累乘即可。

注意先预处理 n 以内的质数，复杂度玄学，估计下面这个。

时间复杂度 O(nlog(nm))

空间复杂度 O(log(nm))

多重集的组合

排列组合技巧