组合数学基础

基础排列组合

实际上主要还是组合

常用记号

• \(n \in \mathbb N,n!:= 1\times 2\times 3\times \dots \times (n-1) \times n\) 称为非负整数 \(n\) 的阶乘，特殊地，\(0! =1\)。
• \(n,m\in \mathbb N,n\geqslant m, \binom{n}{m}=\frac{n!}{m!(n-m)!} \text{ a.k.a } C^m_n\) 表示 \(n\) 个数中无序地选 \(m\) 个数的方案数。
• \(n,m\in \mathbb N,n\geqslant m, {n \brack m} \text{ a.k.a } s(n,m),s_u(n,m)\) 称作第一类无符号斯特林数，表示 \(n\) 个数中排成 \(m\) 个圆排列的方案数不知道什么是圆排列
• \(n,m\in \mathbb N,n\geqslant m, {n \brace m} \text{ a.k.a } S(n,m)\) 称作第二类斯特林数，即 \(n\) 个两两不同的数分成 \(m\) 个互不区分的非空集合的方案数

预处理组合数

递推法

组合数递推：\(\tbinom{n}{m} = \tbinom{n-1}{m-1} + \tbinom{n-1}{m}\)
证明：对于还需要选 \(j\) 个，还剩 \(i\) 个没选的情况，则对于一个苹果来说，不选它的方案数为 \(\tbinom{i-1}{j}\)，选它的方案数为 \(\tbinom{i-1}{j-1}\)。

阶乘法

问题：给定 \(p\) 与多组 \(a,b\) ，求 \(\tbinom{a}{b} \bmod p\)。

设 \(fact_i = i! \bmod p,infact_i = fact_i^{-1}\pmod p\)，根据逆元的性质可得

\[ \begin{aligned} \binom{a}{b} &= \frac{a!}{b!(a-b)!}\newline &= \frac{form_a \cdot inform_b}{(a-b)!}\newline &= form_a \cdot inform_b \cdot inform_{a-b} \end{aligned} \]

二项式定理

二项式就是只有两个项的多项式，如 \(a+b\)

二项式定理如下：

\[ (x+y)^n = \sum^n_{k=0} \binom nk x^{n-k}y^k \]

可以利用组合方法证明：
假设有 \(n\) 个 \((x+y)\) 相乘，由多项式乘法的法则可以知道，对于 \(x^ky^{n-k}\) 这一项来说（容易想到 \(x,y\) 的指数和为 \(n\)），它来自于 \(n\) 个括号中的 \(k\) 个 \(x\) 与剩下 \(n-k\) 个括号中的 \(n-k\) 个 \(y\)，也就是说“\(n\) 个括号中选 \(k\) 个 \(x\) 的方案数”就是该项的系数，即 \(\binom nk\)。

卢卡斯定理

下方 \(p\) 均为质数

\[ \binom nm \bmod p = \binom { \lfloor n/p \rfloor } {\lfloor m/p \rfloor} \binom {n\bmod p}{m \bmod p}\bmod p \]

引理

\[ (a+b)^p \equiv a^p+b^p \pmod p \]

证明：考虑 \(\tbinom pk\) ，易得到\(\binom pk = \frac{p!}{n!(p-n)!}\)，这玩意 \(\bmod p\) 基本上是 \(0\) ，于是我们开始把它扔到上面 二项式定理 里面想。
分两种情况

• \(n \neq p\) 且 \(n\neq1\) 此时 \(p\) 没法被分母任何一个因数整除，因此一定会在值中被保留下来，则该式被 \(p\) 整除
• \(n=p\) 或 \(n=1\) 容易得到此时该式值为 \(1\)

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

\[ (x+y)^p = \binom p 0 x^p + \binom p1 x^{p-1}y^1 + \dots + \binom {p}{p-1}x^{p-(p-1)}y^{p-1} + \binom pp y^p \]

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

\[ (x+y)^p=x^p+y^p \]

证明

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

考虑一个二项式 \((1+x)^n \bmod p\)，设 \(n = kp+r\)，则在 \(\bmod p\) 意义下有：

\[ \begin{aligned} (1+x)^n &= (1+x)^{kp}(1+x)^r \newline &= (1+x^p)^k(1+x)^r \newline &= (1+x^p)^{\lfloor n/p \rfloor}(1+x)^{n\bmod p} \end{aligned} \]

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

\[ (1+x)^n = \binom n0 x^1 + \binom{n}{1}x^2+\dots+\binom n{n-1}x^{n-1} + \binom nn x^n \]

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

\[ \binom nm \bmod p = \binom { \lfloor n/p \rfloor } {\lfloor m/p \rfloor} \binom {n\bmod p}{m \bmod p}\bmod p \]