组合数学基础

组合数学非常有用！我们先从一点点简单的性质开始

• 加法原理

  这非常简单，我们举一个例子即可：考虑我有 5 个红苹果和 3 个绿苹果，如果你要选一个苹果去吃，那么你一共有 5+3=8 种选择的方法

• 乘法原理

  同样非常简单：考虑我有 5 个苹果，涵儿有 6 个苹果，我们各自拿出一个苹果，那么一共有 5×6=30 种拿出的方案

• 减法原理和除法原理

  本质与加法原理和乘法原理相似，这里不做展开

• 抽屉原理

  (广义）如果 n 个物品一共有 k 种状态，那么至少有 ⌈nk⌉ 种物品处于一个状态

  推论：一个从有 >k 个元素的集合映射到 k 个元素的集合的函数一定不是一对一函数。

终于正式开始将排列组合了！

定理：具有 n 个元素的集合，选出 r 个排列的可能数（顺序相关）

P(n,r)=n(n−1)(n−2)⋯(n−r+1)

证明：由于顺序相关，不能选择同一个数多次，那么第一个位置有 n 种选法，第二个位置有 n−1 中选法，以此类推，第 i 个位置有 n−i+1 种选法。考虑乘法原理，那么就得出了上述结论。

特殊的：只要 n 是一个非负整数，那么 P(n,0)=1，因为恰好有一种方法来排列 0 个元素

简写公式：一般来说，我们不会写成上述形式，而是

P(n,r)=n!(n−r)!

考虑这样一个问题：我有 7 个盘子，2 个苹果，3 个橘子和 2 个桃子，分别在一个盘子中放一个水果，一共有多少种放法（我们认为同一种水果是相同的）？

经过计算，一共有 7!2!3!2!=210 种放法。

抽象来说，我们将 k 个元素进行排列，对于第 i 个元素一共有 xi 个。那么总的排列方案数为

其实就是顺序无关的排列

定理：具有 n 个元素的集合，选出 r 个数组成新的集合，本质不同的集合数为

C(n,r)=(nr)=n!r!(n−r)!

由于顺序无关，我们考虑通过排列推导。

证明：为了得出所有集合，我们先考虑顺序相关，也就是有 P(n,r) 个排列，而对于每一个排列，如果不考虑顺序，一共重复计算了 P(r,r) 次，所以

接下来我们考虑组合的各种性质

(nm)=(nn−m)=nm(n−1m−1)=(n−1m)+(n−1m−1)

• 前两个等式，考虑按照定义展开化简即可

• 考虑最后一个等式，其实就是杨辉三角的递推，我们钦定 n 中的一个元素，分情况讨论

  • 如果不选择这个数，也就是在剩下的数中选择 m 个数，那么一共有 (n−1m) 种情况

  • 如果选择这个数，那么只需要在剩下的数种选择 m−1 个数即可，那么一共有 (n−1m−1) 种情况

(nk)(km)=(nm)(n−km−k)

证明：展开即可

n∑i=k(ik)=(n+1k+1)

证明：还是考虑展开

(kk+1) 是不合法的，所以其值为 0，加上去之后不会对结果产生影响

我们通过公式 (nm)=(n−1m)+(n−1m−1) 两两合并即可。

推论：我们将 i 平移，那么得出

n∑i=0i(ni)=n2n−1

证明：

考虑代数展开，通过 (nm)=(nn−m) 变化即可。

但是，其实可以通过生成函数推导。推导步骤如下：

生成函数可以参考另外一篇博客：普通型生成函数 - Ricky2007 - 博客园

我认为讲的不错

我们先展开，得到

我们可以由此联想到生成函数求导的公式

那么我们考虑求导前的生成函数序列：

显然，其生成函数展开之前为 F(x)=(1+x)n

那么我们对其求导得到 F′(x)=n(1+x)n−1

展开之后为

我们考虑需要把所有的系数加起来，那么我们令 x=1 即可

所以，得出

我们考虑扩展一下上述式子

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

考虑还是利用生成函数的思路。

将生成函数 F′(x)=n(1+x)n−1 向右平移一位并再次求导：

那么我们还是借上面的思路，令 x=1，所以

二项式定理

定理：令 n 是非负整数，那么有

(x+y)n=n∑i=0xn−iyi=(n0)xny0+(n1)xn−1y1+⋯+(nn−1)x1yn−1+(nn)x0yn

考虑展开之后每一项都应该是 n 次的，所以 x 为 i 次一共有 (ni) 种情况

我们利用这个找到一些有用的性质：

推论：令 n 为非负整数，那么

n∑i=0(ni)=2n

证明：用二项式定理，令 x=y=1，那么

推论：令 n 为非负整数，那么

n∑i=0(−1)i(ni)=0

证明：令 x=−1,y=1 即可

范德蒙卷积

已知 n,m,t

t∑i=0(ni)(mt−i)=(n+mt)

证明：在组合意义上，相当于在 n 中选 i 个，在 m 中选剩下的，也就是在 n+m 中选择 t 个。

而二项式证明这里就不展开了。

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

Lucas定理

(nm)≡(⌊np⌋⌊mp⌋)(n%pm%p)(modp)

这个证明相对复杂，请酌情食用

证明：

我们考虑通过带余方程改写上述式子：

我们通过生成函数 F(x)=(1+x)sp+t 的第 kp+r 次项的系数求。

我们先求一个推导的时候需要的东西：

那么我们正式开始推导：

我们取 xkp+r 项

那么当且仅当 i=k,j=r 时，就可以取出 xkp+r 项的系数。

考虑为什么当且仅当？

可知，我们需要 ip+j=kp+r

∵j∈[0,t],t∈[0,p),r∈[0,p)∴j=r,i=k

那么，其系数为

所以，可知

程序实现：

这里还是稍微讲一下吧

首先，我们需要求出组合数，那么我们先预处理一下模数以内的阶乘和阶乘逆元：

long long fac[N] = {1}, ifac[N];
for (int i = 1; i < MOD; ++i) fac[i] = (i * fac[i - 1]) % MOD;
ifac[MOD - 1] = quickPow(fac[MOD - 1], MOD - 2, MOD);
for (int i = MOD - 1; i; --i) ifac[i - 1] = ifac[i] * i % MOD;

考虑一下组合数的特殊情况，如果 n<m 那么 (nm)=0

所以我们求模数以内的组合数方法如下：

inline int C(int i, int j) {
    if (i > j) return 0;
    return fac[j] * ifac[i] % MOD * ifac[j - i] % MOD;
}

那么Lucas定理呢？我们处理一下 n=0 的特殊情况即可

inline int Lucas(int i, int j) {
    if (i == 0) return 1;
    return Lucas(i / MOD, j / MOD) * C(i % MOD, j % MOD) % MOD;
}

广义容斥与二项式反演

这个部分相对较复杂，我给出反演公式

令 fn 表示之多拥有 n 个属性的集合个数，gn 表示恰好拥有 n 个属性的集合

反演推导证明