轻松掌握 - 组合数学入门：组合数的基础与取模应用，以及中国剩余定理(CRT)详解

最编程 2024-07-20 16:45:33

...

1.组合数学基础

排列数 $A_n^m=\dfrac{n!}{(n-m)!}$ 相当于从 $A^n_n$ 中除去了 $A_{n-m}^{n-m}$
组合数 $\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}$ 相当于把 $A^m_n$ 除去了顺序，不再赘述

错位排列

它计数的是这样一类问题的答案:对于 $n$ 个小球,每个小球都有其不能放进的一个互不相同的盒子,求方案数

我们设对于 $n$ 个小球的方案数为 $D_n$
通过观察不难发现, $D_1=0,D_2=1$
我们对于第 $n$ 个小球分类讨论,寻找其规律
可以发现,所有球都放错的情况与有两个球放对的情况一一对应

1.如果第 $n$ 个小球放对了,那肯应有 $n-2$ 个小球放错了,有 $D_{n-1}$ 种情况,剩下的一个又有 $n-1$ 种情况,故为 $(n-1)D_{n-2}$ 种
2.如果第 $n$ 个小球放错了,那么剩下的同理,有 $(n-1)D_{n-2}$

所以它的递推公式为 $D_n=(n-1)(D_{n-1}+D_{n-2})$ 或 $D_n=nD_{n-1}+(-1)^n$

圆排列

这相对来说比较简单,问 $n$ 个人转圈排列的方案数,考虑把每种情况转一圈，正好有n种重复情况，所以情况数为 $(n-1)!$

二项式定理

一个式子:

\[(a+b)^n=\sum^n_{i=0}\dbinom{n}{i}a^ib^{n-i} \]

从组合意义考虑，选了 i 个 a 的情况数就是 $\dbinom n i$

一些问题

从 $1,2,3,...,n$ $n$ 个数字中选互不相邻的 $m$ 个数的方案数

\[\dbinom{n-m+1}{m} \]

考虑把 $m-1$ 个数拿出来,再从剩下的里面拿 $m$ 个数,用那 $m-1$ 个数隔开 $m$ 个数

从 $1,2,3,...,n$ $n$ 个数字中选可重复的 $m$ 个数的方案数

\[\dbinom{n+m-1}{n-1} \]

我们把 $m$ 个元素中插入 $n-1$ 个东西
我们从这 $n+m-1$ 个元素中选 $n-1$ 个元素作为隔板,第 $i-1$ 个隔板和第 $i$ 个隔板之间的元素个数即为第 $i$ 个数字所选的个数

$n$ 个小球放进 $m$ 个盒子里,每个盒子不同且必须有一个球

\[\dbinom{n-1}{m-1} \]

用 $m-1$ 个隔板插到 $n$ 个元素的空里,两个隔板之间就是一个盒子

2. 组合恒等式

\[\dbinom n m=\dbinom{n}{n-m}\tag{1} \]

组合推理:选 $m$ 的和选 $m$ 的补集的情况数是一样的

\[\dbinom n m=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\tag{2} \]

组合推理:考虑选不选第 $n$ 个，不选的情况为 $\dbinom{n-1}{m}$，选的情况为 $\dbinom{n-1}{m-1}$

\[k\dbinom nk=n\dbinom {n-1}{k-1}\tag{3} \]

吸收恒等式，组合意义为从 $n$ 个人中选 $k$ 个人，并指定一人成为队长，由组合数定义也可推出，作为组合数其中一种推导式使用，可以与这个恒等式相搭配：$(n−k)\dbinom nk=n\dbinom {n-1}k$，实现组合数上标下标的增减

\[\dbinom rm\dbinom mk=\dbinom rk \dbinom {r-k}{m-k}\tag{4} \]

组合推理：左式的组合意义是从 $r$ 个中选 $m$ 个，再从这 $m$ 个中选 $k$ 个，所以可以先从 $r$ 个中选 $k$ 个，再从剩下的 $r-k$ 个中选剩下的 $m-k$ 个

\[ \sum\limits_{k=0}^n \dbinom{m_1}{k} \dbinom{m_2}{n-k}=\dbinom{m_1+m_2}{n}\tag{5} \]

两种证明：

组合意义
把 $m_1+m_2$ 个东西分成个数分别为 $m_1$ 和 $m_2$ 的两份，然后从这两份中取总计 $n$ 份的东西
二项式定理

\[\begin{aligned} (1+x)^{m_1}(1+x)^{m_2} & = (1+x)^{m_1+m_2}\\ \sum\limits_{i=1}^{m_1}x^i\dbinom{m_1}{i}\sum\limits_{i=1}^{m_2}x^i\dbinom{m_2}{i} & = \sum\limits_{i=1}^{m_1+m_2}x^i\dbinom{m_1+m_2}{i} \end{aligned} \]

$\dbinom{m_1+m_2}{n}$ 就是 $x^{n}$ 的系数
因为 $x^n=x^{n-i}x^i$ (显然吧)
所以易得， $\dbinom{m_1+m_2}{n}$ 就等于 $\sum\limits_{i=0}^n \dbinom{m_1}{i} \dbinom{m_2}{n-i}$

\[\sum\limits^n_{i=1}\dbinom ni^2=\dbinom{2n}n\tag{6} \]

这是上式的特殊情况，取 $m_1=m_2$

\[\sum\limits^{n}_{i=1}i\dbinom ni=n2^{n-1}\tag{7} \]

证明：

\[(1+x)^n=\sum\limits^n_{i=0}\dbinom ni x^i \]

把此式两边求导，得到：

\[n(1+x)^{n-1}=\sum\limits^n_{i=1}i\dbinom ni x^{i-1} \]

将 $x=1$ 代入，即是原式

\[n(n+1)2^{n-2}=\sum^n_{i=1}i^2\dbinom ni\tag{8} \]

这个式子是对上式的进一步求导，不再赘述，其实只要可以的话，可以得到 $\sum\limits^n_{i=1}i^p\dbinom ni$ 对于任意正整数的恒等式，但求导也会越来越复杂

但是呢，据《组合数学》所言，这东西有组合意义，不会推，谁会证在评论说一下

\[\sum\limits^n_{i=1}i\dbinom ni^2=n\dbinom{2n-1}{n-1}\tag{9} \]

组合推理：考虑 $n$ 个男生和 $n$ 个女生，选取 $n$ 个人组成团队，一个男生是领导（其实在这种意义下 $\dbinom ni^2$ 应写作 $\dbinom ni\dbinom n{n-i}$）

\[\sum\limits^n_{i=0}(-1)^i\dbinom{n}{i}=[n=0]\tag{10} \]

二项式定理的特殊情况，取 $a=1,b=-1$，仅当 $n=0$ 时式子取值为 $1$，~~可以反演~~

有一个推论：$\sum\limits^{n}_{2\mid i}\dbinom{n}{i}=\sum\limits^{n}_{2\not\mid i}\dbinom{n}{i}$ 移项即可推出

\[\sum\limits^n_{i=0}(-1)^i\dbinom ni^2= \begin{cases} 0& n\ne 2m&(m\in \mathbb{Z})\\ (-1)^m\dbinom {2m} m& n=2m \end{cases}\tag{11} \]

证明：由 $(1-x^2)^n=(1+x)^n(1-x)^n$ 可推导

\[\begin{aligned} (1-x^2)^n&=(1+x)^n(1-x)^n\\ \sum\limits^n_{i=0}(-1)^i\dbinom nix^{2i}&=\sum\limits^n_{i=0}\dbinom nix^{i}\sum\limits^n_{i=0}(-1)^i\dbinom nix^{i} \end{aligned} \]

对着这个式子可以推出 $x^n$ 的系数，对于左边式子来说，只有 $n$ 为偶数时才有系数，对于 $n$ 为奇数，系数为 $(-1)^m\dbinom{2m}m$，而右边式子 $x^n$ 的系数为 $\sum\limits^n_{i=0}(-1)^i\dbinom{n}{n-i}\dbinom ni=\sum\limits^n_{i=0}(-1)^i\dbinom ni^2$，系数相等，由此得证

\[\sum\limits^n_{i=0}\dbinom ni =2^n\tag{12} \]

二项式定理特殊情况，$a=1,b=1$
组合意义：$\dbinom ni$ 表示 n 个元素中含 i 个元素的子集数量，求和即为 n 个元素的子集数量 $2^n$

\[\sum\limits^n_{i=0}\dbinom ik=\dbinom{n+1}{k+1}\tag{13} \]

组合推理：在 $n+1$ 个球里拿 $k+1$ 个，最后一个拿的是第 $i$ 个，则情况数为 $\dbinom ik$，累加即为总数——$\dbinom{n+1}{k+1}$

\[\sum\limits^n_{i=0}\dbinom {m+i}i=\dbinom{n+m+1}{n}\tag{14} \]

证明（会用到 $(13)$ ）：

\[\begin{aligned} \sum\limits^n_{i=0}\dbinom {m+i}i&=\sum\limits^n_{i=0}\dbinom {m+i}i\\ &=\sum\limits^{n+m}_{i=m}\dbinom {i}m+0\\ &=\sum\limits^{n+m}_{i=m}\dbinom {i}m+\sum\limits^{m-1}_{i=0}\dbinom {i}m\\ &=\sum\limits^{n+m}_{i=0}\dbinom im\\ &=\dbinom{n+m+1}{m+1}=\dbinom{n+m+1}{n} \end{aligned} \]

这个东西也可以进行扩展到上下均有值的情况

\[\begin{aligned} \sum\limits^n_{i=0}\dbinom {m+i}{s+i}&=\sum\limits^n_{i=0}\dbinom {m+i}{m-s}\\ &=\sum\limits^{n+m}_{i=0}\dbinom i{m-s}\\ &=\dbinom{n+m+1}{m-s+1}=\dbinom{n+m+1}{n+s} \end{aligned} \]

\[\sum\limits^{n}_{i=0}\dbinom nk r^k=(1+r)^n\tag{15} \]

又是二项式定理，$a=m,b=1$

\[\sum^n_{i=0}\dbinom {n-i}i=f_{n+1} \quad\texttt{（$f_i$ 为斐波那契数列第 $i$ 项）}\tag{16} \]

设原数列为 $g_i$ 则显然 $g_0=f_1,g_1=f_2$，只需要验证是否存在 $g_i=g_{i-1}+g_{i-2}$ 即可
然后我们把它放在杨辉三角里，结论就显而易见了：

这个表格最上面一行是 $g_i$ ，在杨辉三角中表现为对它所在斜线的数进行求和
又因为杨辉三角的递推式，观察表格，显然就能得出结论

我觉得这东西应该有一个巧妙的组合意义，但我想不出来（

3.组合数取模

$m!(n-m)!$ 逆元直接淦

适合非常水的题
杨辉三角递推式直接取模淦

适合 $nm\le1e7$
卢卡斯定理
一个式子： $\dbinom{n}{m}\equiv\dbinom{ \left\lfloor n/p \right\rfloor}{ \left\lfloor m/p \right\rfloor}\dbinom{n \bmod p}{m\bmod p}\pmod p$
证明：
首先可以推出一个性质： $(1+x)^p \equiv 1+x^p \pmod p$
由于 $(1+x)^p$ 的第 $i$ 项的系数为 $\dbinom pi=\dfrac{p!}{(p-i)!i!}$ 而显然当 $p\ne 1,p$ 时，这个式子永远是有 $p$ 这个因子，故模p为0，所以只剩下了第一项和最后一项

二项式系数 $\dbinom nm$ 显然可以看做是 $(1+x)^n$ 中 $x^m$ 的系数，然后我们对 $(1+x)^n$ 进行一些操作：
$ \begin{aligned} (1+x)^n&\equiv(1+x)^{\left\lfloor n/p\right\rfloor \cdot p}(1+x)^{n\bmod p}\\ &\equiv(1+x^p)^{\left\lfloor n/p \right\rfloor}(1+x)^{n\bmod p}\\ &\equiv\sum\limits^{\left\lfloor n/p \right\rfloor}_{i-1}\dbinom {\left\lfloor n/p \right\rfloor}{i} x^{ip}\sum^{n\bmod p}_{i=1} \dbinom{n\bmod p}{i} x^i \pmod p\\ \end{aligned} $
然后观察式子，可以把 $x^m$ 拆成 $x^{\left\lfloor m/p\right\rfloor \cdot p}\cdot x^{m\bmod p}$ ，可以发现，在模p意义下， $x^{\left\lfloor m/p\right\rfloor\cdot p}$ 的系数为 $\dbinom {\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}$，$x^{m\bmod p}$ 的系数为 $\dbinom{n\bmod p}{m\bmod p}$，则 $x^m$ 的系数为 $\dbinom{ \left\lfloor n/p \right\rfloor}{ \left\lfloor m/p \right\rfloor}\dbinom{n \bmod p}{m\bmod p}$ ，由此得证

4.中国剩余定理——孙子定理

中国剩余定理可解决以下问题（其中 $n_1,n_2,n_3,...,n_k$ 互质）:

\[\begin{cases} x \equiv a_1 \pmod {n_1}\\ x \equiv a_2 \pmod {n_2}\\ x \equiv a_3 \pmod {n_3}\\ ....\\ x \equiv a_k \pmod {n_k}\\ \end{cases}\]

答案为：

\[n=\prod^k_{i=1}n_i\quad m_i=\frac{n}{n_i} \]

\[ans=\sum^k_{i=1}a_im_im_i^{-1} \bmod n\text{ 其中 $m_i^{-1}$ 是模 $n_i$ 意义下的逆元} \]

我们观察式子，可以发现 $\forall i,j(i\ne j) n_j \mid m_i$ 所以 $a_im_im_i^{-1}$ 对于其他模数余数贡献为0
而 $a_im_im_i^{-1}\equiv a_i \pmod n_i$ 所以我们构造出了一个满足条件的数

原文地址：https://www.cnblogs.com/Rolling-star/p/16045094.html

上一篇：如何在二进制中表示负数：以补码方式对比正数的原码表示法

下一篇：理解数字逻辑基础：原码、反码与补码详解