组合数学基础

基础排列组合

实际上主要还是组合

常用记号

默认 𝑛 ∈ℕ

• 1 ×2 ×3 ×⋯ ×(𝑛 −1) ×𝑛 称为非负整数 𝑛 的阶乘，记为 𝑛!，特殊地，0! =1。
• (𝑛𝑚) 也记作 𝐶𝑚𝑛 表示 𝑛 个数中无序地选 𝑚 个数的方案数，𝐶𝑚𝑛 =𝑛!𝑚!(𝑛−𝑚)!。

• 𝑛,𝑚 ∈ℕ,𝑛 ⩾𝑚,[𝑛𝑚] a.k.a 𝑠⁡(𝑛,𝑚),𝑠𝑢⁡(𝑛,𝑚) 称作第一类无符号斯特林数，表示 𝑛 个数中排成 𝑚 个圆排列的方案数不知道什么是圆排列
• 𝑛,𝑚 ∈ℕ,𝑛 ⩾𝑚,{𝑛𝑚} a.k.a 𝑆⁡(𝑛,𝑚) 称作第二类斯特林数，即 𝑛 个两两不同的数分成 𝑚 个互不区分的非空集合的方案数

预处理组合数

递推法

组合数递推：(𝑛𝑚) =(𝑛−1𝑚−1) +(𝑛−1𝑚)
证明：对于还需要选 𝑗 个，还剩 𝑖 个没选的情况，则对于一个苹果来说，不选它的方案数为 (𝑖−1𝑗)，选它的方案数为 (𝑖−1𝑗−1)。

阶乘法

问题：给定 𝑝 与多组 𝑎,𝑏 ，求 (𝑎𝑏)⁢mod⁡𝑝。

设 𝑓⁡𝑎⁢𝑐⁢𝑡𝑖 =𝑖!mod⁡𝑝,𝑖⁢𝑛⁢𝑓⁡𝑎⁢𝑐⁢𝑡𝑖 =𝑓⁡𝑎⁢𝑐⁢𝑡−1𝑖⁡(mod⁡𝑝)，根据逆元的性质可得

(𝑎𝑏)=𝑎!𝑏!(𝑎−𝑏)!=𝑓⁡𝑜⁢𝑟⁢𝑚𝑎⋅𝑖⁢𝑛⁢𝑓⁡𝑜⁢𝑟⁢𝑚𝑏(𝑎−𝑏)!=𝑓⁡𝑜⁢𝑟⁢𝑚𝑎⋅𝑖⁢𝑛⁢𝑓⁡𝑜⁢𝑟⁢𝑚𝑏⋅𝑖⁢𝑛⁢𝑓⁡𝑜⁢𝑟⁢𝑚𝑎−𝑏

二项式定理

二项式就是只有两个项的多项式，如 𝑎 +𝑏

二项式定理如下：

(𝑥+𝑦)𝑛=𝑛∑𝑘=0(𝑛𝑘)⁢𝑥𝑛−𝑘⁢𝑦𝑘

可以利用组合方法证明：
(𝑥+𝑦)𝑛 相当于 𝑛 个 (𝑥 +𝑦) 相乘。然后思考多项式乘法是怎么做的：
(𝑥+𝑦)⁢(𝑥+𝑦)=𝑥2+𝑥⁢𝑦+𝑥⁢𝑦+𝑦2=𝑥2+2⁢𝑥⁢𝑦+𝑦2
显然结果中的每一项都是从相乘的每一个多项式中取出来一项，把这些项乘在一起。然后应用到 (𝑥+𝑦)𝑛 里，结果中的每一项一定形如 𝑥𝑎⁢𝑦𝑏，且 𝑎 +𝑏 =𝑛。
所以考虑 𝑥𝑎⁢𝑦𝑛−𝑎 这一项，它是从 𝑛 个 (𝑥 +𝑦) 中选出来 𝑎 个用来提供 𝑥，剩下的提供 𝑦 乘出来的，即其系数是 (𝑛𝑎)。
所以最后结果就是 ∑𝑛𝑘=0(𝑛𝑘)⁢𝑥𝑘⁢𝑦𝑛−𝑘

卢卡斯定理

下方 𝑝 均为质数

(𝑛𝑚)⁢mod⁡𝑝=(⌊𝑛/𝑝⌋⌊𝑚/𝑝⌋)⁢(𝑛⁢mod⁡𝑝𝑚⁢mod⁡𝑝)⁢mod⁡𝑝

引理

(𝑎+𝑏)𝑝≡𝑎𝑝+𝑏𝑝(mod⁡𝑝)

证明：考虑 (𝑝𝑘) ，易得到(𝑝𝑘) =𝑝!𝑛!(𝑝−𝑛)!，这玩意 mod⁡𝑝 基本上是 0 ，于是我们开始把它扔到上面 二项式定理 里面想。
分两种情况

• 𝑛 ≠𝑝 且 𝑛 ≠1 此时 𝑝 没法被分母任何一个因数整除，因此一定会在值中被保留下来，则该式被 𝑝 整除
• 𝑛 =𝑝 或 𝑛 =1 容易得到此时该式值为 1

于是我们就把二项式定理中的所有项讨论完了。

(𝑥+𝑦)𝑝=(𝑝0)⁢𝑥𝑝+(𝑝1)⁢𝑥𝑝−1⁢𝑦1+⋯+(𝑝𝑝−1)⁢𝑥𝑝−(𝑝−1)⁢𝑦𝑝−1+(𝑝𝑝)⁢𝑦𝑝

根据上面的讨论，左右两边的两项系数为 1，其余被 𝑝 整除，也就是被模掉了，于是最后剩下：

(𝑥+𝑦)𝑝=𝑥𝑝+𝑦𝑝

证明

引理 推导的过程中没有任何限制，于是我们可以把它用在多项式身上

考虑一个二项式 (1+𝑥)𝑛⁢mod⁡𝑝，设 𝑛 =𝑘⁢𝑝 +𝑟，则在 mod⁡𝑝 意义下有：

(1+𝑥)𝑛=(1+𝑥)𝑘⁢𝑝⁢(1+𝑥)𝑟=(1+𝑥𝑝)𝑘⁢(1+𝑥)𝑟=(1+𝑥𝑝)⌊𝑛/𝑝⌋⁢(1+𝑥)𝑛⁢mod⁡𝑝

用二项式定理拆开的话，可以观察一下这个式子的内部结构

(1+𝑥)𝑛=(𝑛0)⁢𝑥1+(𝑛1)⁢𝑥2+⋯+(𝑛𝑛−1)⁢𝑥𝑛−1+(𝑛𝑛)⁢𝑥𝑛

现在我们的目标是求 (𝑛𝑚)，实际上在上面的式子里就是 𝑥𝑚 的系数。
想办法从前面推导出来的东西表示 𝑥𝑚 的系数，这里采用类似的办法，把 𝑚 拆开为 ⌊𝑚/𝑝⌋⁢𝑝 +(𝑚⁢mod⁡𝑝)，于是目标转化为如何在最上面的式子中找到 𝑥 相乘表示出左侧的次数。
分开考虑贡献，⌊𝑚/𝑝⌋⁢𝑝 只能从 (1+𝑥𝑝)⌊𝑛/𝑝⌋ 处得到贡献，因为这玩意显然是个 𝑝 的倍数，而另外半边式子中 𝑛⁢mod⁡𝑝 绝对小于 𝑝。
于是我们也就考虑到了 𝑚⁢mod⁡𝑝 的贡献应当从 𝑛⁢mod⁡𝑝 中来，因为 ⌊𝑛/𝑝⌋ >𝑝。
这样就找到了对 (𝑛𝑚) 的总贡献，从 𝑛⁢mod⁡𝑝 中选 𝑚⁢mod⁡𝑝 个，另外半边同理，则为

(𝑛𝑚)⁢mod⁡𝑝=(⌊𝑛/𝑝⌋⌊𝑚/𝑝⌋)⁢(𝑛⁢mod⁡𝑝𝑚⁢mod⁡𝑝)⁢mod⁡𝑝