组合数(Binomial coefficient)

性质

首先我们回顾一下一些简单性质

$\begin{pmatrix}n\\k\end{pmatrix}=\displaystyle\frac{n!}{k!(n-k)!}$
$\begin{pmatrix}n\\k\end{pmatrix}=\displaystyle\frac{n}{k}\begin{pmatrix}n-1\\k-1\end{pmatrix}$
$\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n-1\\k\end{pmatrix}+\begin{pmatrix}n-1\\k-1\end{pmatrix}$
$\begin{pmatrix}n\\m\end{pmatrix}\begin{pmatrix}m\\k\end{pmatrix}=\begin{pmatrix}n\\k\end{pmatrix}\begin{pmatrix}n-k\\m-k\end{pmatrix}$
$\displaystyle\sum_{m=0}^n\begin{pmatrix}m\\k\end{pmatrix}=\begin{pmatrix}n+1\\k+1\end{pmatrix}$
$\displaystyle\sum_{k=0}^nk\begin{pmatrix}n\\k\end{pmatrix}=n2^{n-1},\quad\sum_{k=0}^nk^2\begin{pmatrix}n\\k\end{pmatrix}=n(n+1)2^{n-2}$

组合数的计算

直接算

ll binom(int n, int m) {
    if (m < 0 || m > n) return 0;
    ll res = 1;
    for (int i = 1; i <= m; ++i) {
        res *= n - i + 1; res /= i;
    }
    return res;
}

利用性质3

for (int i = 0; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
}

预处理阶乘和阶乘逆元

费马小定理(Fermat's little theorem)

$p$为质数，且$p\nmid a$，则

\[a^{p-1}\equiv1\pmod p\]

\[inv(a)\equiv a^{p-2}\pmod p\]

\[\begin{pmatrix}n\\m\end{pmatrix}=fac(n)*inv(m!)*inv((n-m)!)\]

\[inv(i!)\equiv inv((i+1)!)*(i+1)\pmod p\]

int C(int n, int m) {
    if (m > n) return 0;
    return fac[n] * power(fac[m], p - 2) % p * power(fac[n-m], p - 2) % p;
}

求解$C_n^m mod\ p$，该法要求p为质数

Lucas定理(Lucas's theorem)

\[\begin{pmatrix}n\\m\end{pmatrix}\equiv\begin{pmatrix}\lfloor n/p\rfloor\\\lfloor m/p\rfloor\end{pmatrix}\begin{pmatrix}n\mod p\\m\mod p\end{pmatrix}\pmod p\qquad (p为素数)\]

$proof:\quad$设$n=sp+q,m=tp+r\ (q,r\leq p)$,那么 \[\begin{array}{l} (1+x)^n&=&\left((1+x)^p\right)^s(1+x)^q\\ &\equiv&(1+x^p)^s(1+x)^q\pmod p\\ &=&\displaystyle\sum_{i=0}^s\begin{pmatrix}s\\i\end{pmatrix}x^{ip}\sum_{j=0}^q\begin{pmatrix}q\\j\end{pmatrix}x^j\\ \end{array}\]

可以得到

\[(1+x)^{sp+q}\equiv\sum_{i=0}^s\begin{pmatrix}s\\i\end{pmatrix}x^{ip}\sum_{j=0}^q\begin{pmatrix}q\\j\end{pmatrix}x^j\pmod p\]

$LHS$中$(1+x)^{sp+q}$中的$x^{tp+r}$系数为$\begin{pmatrix}sp+q\\tp+r\end{pmatrix}$, $RHS$中的$x^{tp+r}$系数为$\begin{pmatrix}s\\t\end{pmatrix}\begin{pmatrix}q\\r\end{pmatrix}$, 从而

\[\begin{pmatrix}sp+q\\tp+r\end{pmatrix}\equiv\begin{pmatrix}s\\t\end{pmatrix}\begin{pmatrix}q\\r\end{pmatrix}\pmod p\]

这与原命题等价, 证毕.

Lucas定理模板题

code

Lucas定理+CRT合并

CRT合并

对同余方程

\[\begin{cases}x\equiv{a_1}\pmod{p_1}\\x\equiv{a_2}\pmod{p_2}\end{cases}\]

令$x=mp_1+a_1,$代入方程2得

\[mp_1\equiv{a_2-a_1}\pmod{p_2}\]

即

\[mp_1-np_2=a_2-a_1\]

由贝祖定理(Bezout's identity)，若$m$有解$m_0$(即$\gcd(p_1,p_2)|a_2-a_1,m_0$可用exgcd求)，则$m$满足通项

\[m=m_0+k\frac{p_2}{\gcd(p_1,p_2)}\quad k\in\Bbb{Z}\]

代入$x$表达式有

\[x=m_0p_1+k{\rm{lcm}}(p_1,p_2)+a_1\]

故

\[x\equiv m_0p_1+a_1\pmod{ {\rm lcm}(p_1,p_2) }\]

孙子定理(Chinese remainder theorem)

对同余方程组，其中$p_i$两两互质

\[\begin{cases}x\equiv{a_1}\pmod{p_1}\\x\equiv{a_2}\pmod{p_2}\\\quad\vdots\\x\equiv{a_n}\pmod{p_n} \end{cases}\]

设$\displaystyle P=\prod_{i=1}^np_i,\ P_i=\frac{P}{p_i}$，则方程组有通解

\[x\equiv\sum_{i=1}^na_iP_i{\rm inv}(P_i)\pmod{P}\]

P2840

勒让德定理(Legendre's formula) (或者叫扩展Lucas)

考虑计算

\[\begin{pmatrix}n\\m\end{pmatrix}\mod{p}\]

对$p$进行唯一分解$p=\prod p_i^{c_i}$

我们想知道$n!$分解里$p_i$的最高指数，设$f(n)$表示$n!$分解里$p$的最高指数，我们这样考虑：先将$p$的倍数($\lfloor\frac{n}{p}\rfloor$个)全部除以$p$，再考虑除$p$后的子问题，有递推

\[f(n)=f(\lfloor\frac{n}{p}\rfloor)+\lfloor\frac{n}{p}\rfloor\]

勒让德定理：在正数$n!$的素因子标准分解式中，素数$p$的最高指数为 \[v_p(n!)=\displaystyle\sum_{i=1}^\infty\lfloor\frac{n}{p^i}\rfloor\]

一些应用

给定$n,m$输出$C_n^m$的后十位。其中$0<m\le n\le 30000$，输出时不足十位数也按十位输出，此时高位补0。
input：29999 27381
output：4531330240

将分子分母进行分解并进行约分，数组$c$记录重数

code

生成函数(Generating function)

对于有限数列$a_0,a_1,a_2,\cdots,a_n,$多项式$f(z)=\displaystyle\sum_{k=0}^na_kz^k$称为数列$\{a_k\}$的生成函数。无穷数列相关定义类似。

技巧

乘积

\[f(z)g(z)=\sum_{i>=0}a_iz^i\sum_{j>=0}b_jz^j\\=(a_0b_0)+(a_0b_1+a_1b_0)z+(a_0b_2+a_1b_1+a_2b_0)z^2\]

$f(z)g(z)$是$\{c_n\}$的生成函数，其中

\[c_n=\sum_{k=0}^na_kb_{n-k}\]

其中一个特例是

\[\frac{1}{1-z}f(z)=a_0+(a_0+a_1)z+(a_0+a_1+a_2)z^2+\cdots\]

三个函数乘积的生成函数遵循

\[d_n=\sum_{\begin{array}{c}i,j,k>0\\i+j+k=n\end{array} }a_ib_jc_k\]

一般地，任意函数乘积遵循

\[\prod_{j\geq0}\sum_{i\geq0}a_{ij}z^i=\sum_{n\geq0}\left(z^n\sum_{\begin{array}{c}i_0,i_1,\cdots\geq0\\i_0+i_1+\cdots=n\end{array} }a_{0i_0}a_{ai_1}\cdots\right)\]

$$$$

变换

\[\frac{1}{2}(f(z)+f(-z))=\sum_{n\geq0}a_{2n}z^{2n}\] \[\frac{1}{2}(f(z)-f(-z))=\sum_{n\geq0}a_{2n+1}z^{2n+1}\]

利用复数根$w=e^{\frac{2\pi i}{m} }=\cos{\frac{2\pi}{m} }+i\sin{\frac{2\pi}{m} }$，我们可以扩展得到

\[\sum_{n\geq0,n\bmod m=r}a_nz^n=\frac{1}{m}\sum_{0\leq k<m}w^{-kr}f(w^kz)\]

例如$m=3$，$w=-\frac{1}{2}+\frac{\sqrt{3}}{2}i$，有

\[a_1z+a_4z^4+a_7z^7+\cdots=\frac{1}{3}(f(z)+w^{-1}f(wz)+w^{-2}f(w^2z))\]

生成函数举例

\[(1+z)^n=\sum_{k\geq0}\begin{pmatrix}n\\k\end{pmatrix}z^k\]

\[\frac{1}{(1-z)^{n+1} }=\sum_{k\geq0}\begin{pmatrix}n+k\\n\end{pmatrix}z^k\]

\[e^z=\sum_{k\geq0}\frac{1}{k!}z^k\]

\[\ln{(1+z)}=z-\frac{1}{2}z^2+\cdots=\sum_{k\geq1}\frac{(-1)^{k+1} }{k}z^k\]

\[\frac{z}{e^z-1}=1-\frac{1}{2}z+\frac{1}{12}z^2+\cdots=\sum_{k\geq0}\frac{B_k}{k!}z^k\]

其中$B_k$为伯努利数，以下函数涉及到斯特林数

\[(e^z-1)^n=z^n+\frac{1}{n+1}\begin{Bmatrix}n+1\\n\end{Bmatrix}z^{n+1}+\cdots=n!\sum_{k}\begin{Bmatrix}k\\n\end{Bmatrix}\frac{z^k}{k!}\]

\[\left(\ln\frac{1}{1-z}\right)^n=z^n+\frac{1}{n+1}\begin{bmatrix}n+1\\n\end{bmatrix}z^{n+1}+\cdots=n!\sum_{k}\begin{bmatrix}k\\n\end{bmatrix}\frac{z^k}{k!}\]

\[z(z+1)\cdots(z+n-1)=\sum_{k}\begin{bmatrix}n\\k\end{bmatrix}z^k\]

\[\frac{z^n}{(1-z)(1-2z)\cdots(1-nz)}=\begin{Bmatrix}k\\n\end{Bmatrix}z^k\]

证明组合恒等式

\[(1)\sum_{k=1}^nC_n^kC_n^{n+1-k}=C_{2n}^{n+1}\]

proof

$\displaystyle\left(\sum_{i=0}^nC_n^iz^i\right)\left(\sum_{j=0}^nC_n^jz^j\right)=(1+z)^{2n}=\sum_{k=0}^{2n}C_{2n}^kz^k$, 两边$z^{n+1}$系数相等。

\[(2)\sum_{k=0}^{[\frac{n}{2}]}(-1)^kC_{n+1}^kC_{2n-2k}^n=n+1\]

proof

\[\displaystyle\sum_{k=0}^{n+1}C_{n+1}^kz^k=(1+z)^{n+1}\\=\frac{(1-z^2)^{n+1}}{(1-z)^{n+1}}=\left(\sum_{k=0}^{n+1}(-1)^kC_{n+1}^kz^{2k}\right)\left(\sum_{j=0}^\infty C_{n+j}^nz^j\right),\]

右边$z^n$系数$=\displaystyle\sum_{k=0}^{[\frac{n}{2}]}(-1)^kC_{n+1}^kC_{n+(n-2k)}^n=\sum_{k=0}^{[\frac{n}{2}]}(-1)^kC_{n+1}^kC_{2n-2k}^n=$左边$z^n$系数$=n+1$

\[(3)\sum_{k=p}^n(-1)^kC_n^kC_k^p=(-1)^n\delta_{pn},\text{其中}\delta_{ij}=\begin{cases}1\quad ,i=j\\0\quad ,i\neq j\end{cases}\]

proof

\[\displaystyle\because k\geq p\text{时}(1+z)^k=\sum_{i=0}^kC_k^iz^i\text{中}z^p\text{系数}C_k^p,0\leq k < p\text{时}(1+z)^k\text{中}z^p\text{系数}0\] $\displaystyle\therefore\sum_{k=0}^n(-1)^kC_n^k(1+z)^k中z^p系数为\sum_{k=p}^n(-1)^kC_n^kC_k^p$并且$\displaystyle\sum_{k=0}^n(-1)^kC_n^k(1+z)^k=[1-(1+z)]^n=(-1)^nz^n$中$z^p$系数为$(-1)\delta_{pn}$,即证。

实际应用

将一张$n$元的纸币全部兑换为1元和2元的纸币，问有多少种不同的兑换方法?

所求方法数为下列多项式中$z^n$的系数$a_n$ \[f(z)=\sum_{n=0}^\infty a_nz^n=\left(\sum_{i=0}^\infty z^i\right)\left(\sum_{j=0}^\infty z^{2j}\right)\\=\left(\frac{1}{1-z}\right)\left(\frac{1}{1-z^2}\right)=\frac{1}{4(1+z)}+\frac{1}{2(1-z^2)}+\frac{1}{4(1-z)}\\=\sum_{n=0}^\infty\left(\frac{n+1}{2}+\frac{1+(-1)^n}{4}\right)z^n\] 故所求方法数为$\displaystyle a_n=\frac{n+1}{2}+\frac{1+(-1)^n}{4}=\left[\frac{n+2}{2}\right]$

求$n$位十进制数中出现偶数个5的数的个数。

设$a_n$表示$n$位十进制数中出现偶数个5的个数，$b_n$表示$n$位十进制数中出现奇数个的个数，则：

\[\begin{cases} a_n=9a_{n-1}+b_{n-1}\\ b_n=9b_{n-1}+a_{n-1}\\ a_1=8,\ b_1=1 \end{cases}\]

设$\{a_n\}$，$\{b_n\}$生成函数分别为$f(z)$，$g(z)$则

\[(1-9z)f(z)-zg(z)=a_1=8\] \[(1-9z)g(z)-zf(z)=b_1=1\]

解得

\[f(z)=\frac{1}{2}\left(\frac{7}{1-8z}+\frac{9}{1-10z}\right)=\frac{1}{2}\left(\sum_{n=0}^\infty7*(8z)^n+\sum_{n=0}^\infty9*(10z)^n\right)\]

所以 \[a_n=\frac{7*8^{n-1}+9*10^{n-1}}{2}\]

P2563质数分解问题

构造生成函数

\[G(z)=\sum_{k=0}^{\infty}z^{2k}*\sum_{k=0}^{\infty}z^{3k}\sum_{k=0}^{\infty}z^{5k}*\cdots\]

则$z^n$的系数为所求方案数。

代码

组合数学基础

组合数学基础

组合数(Binomial coefficient)

性质

组合数的计算

直接算

利用性质3

预处理阶乘和阶乘逆元

费马小定理(Fermat's little theorem)

Lucas定理(Lucas's theorem)

Lucas定理+CRT合并

CRT合并

孙子定理(Chinese remainder theorem)

勒让德定理(Legendre's formula) (或者叫扩展Lucas)

一些应用

生成函数(Generating function)

技巧

生成函数举例

证明组合恒等式

实际应用