常用计数技巧和方法(理论篇)

2020/06/07 13:03
阅读数 188

常用计数技巧和方法(理论篇)

文章较长且大量使用 \(\LaTeX\) 导致渲染较慢,因此分为两个部分

由于组合方面的知识非常的繁细,容易忘记,使用时不够熟练,这里总结一下

以下内容有所借鉴百度百科和大佬的 blog %%%

【瞎总结】组合模型及其组合意义的阐释

范德蒙德卷积以及一些二项式系数的推导

排列组合定义

排列:指从给定个数的元素中取出指定个数的元素进行排序

组合:组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序

\[A_n^m = \frac{fac[n]}{fac[n-m]}\\ C_n^m={n \choose m} = \frac{fac[n]}{fac[m]\cdot fac[n-m]} = \frac{A_n^m}{fac[m]} \]

加法原理

第一类办法中有 \(m_1\) 种不同的方法,在第二类办法中有 \(m_2\) 种不同的方法,……,在第 n 类办法中有 \(m_n\) 种不同的方法,那么完成这件事共有 \(N=m_1+m_2+m_3+…+m_n\) 种不同方法

乘法原理

做一件事,完成它需要分成 n 个步骤,做第一步有 \(m_1\) 种不同的方法,做第二步有 \(m_2\) 种不同的方法,……,做第n 步有 \(m_n\) 种不同的方法,那么完成这件事共有 \(N=m_1×m_2×m_3×…×m_n\) 种不同的方法。

二项式定理

\[\large{(a+b)^n=\sum_{i=0}^n{n\choose i}a^ib^{n-i}}\\ \]

很好理解,每个 \((a+b)\) 中可以选出 a 或 b,最终有 k 个 a 的方案数就是 \(n \choose k\)

其他变形,在部分题可以应用

\[\large{(a-b)^n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}a^ib^{n-i}}\\ \large{\frac{(a+b)^n+(a-b)^n}{2}=\sum_{i为偶数}^n{n \choose i}a_{n-i}b^i} \]

杨辉三角

杨辉三角

容易发现其与二项式系数有着对应关系

其他性质

  • \({n \choose i} = {n-1 \choose i}{n-1 \choose i-1}\) 选不选 n 号物品
  • \({n \choose i} = {n \choose n-i}\)
  • \(2^n=\sum_{i=0}^n {n\choose i}\)
  • \(\sum_{i为奇数}{n\choose i}=\sum_{i为偶数}{n\choose i}=2^{n-1}\)

组合数的奇偶(了解)

对组合数 \(n \choose k\):将 n,k 分别化为二进制,若某二进制位对应的 n 为 0,而 k 为 1,则 \(n \choose k\) 为偶数;否则为奇数。

快速计算组合数的方法

  • 预处理逆元,定义法计算 \(\Theta (N+T)\)
  • 将杨辉三角打表,\(\Theta(N^2+T)\)
  • 对于模数较小的情况可以使用 Lucas 定理和 exLucas 解决
  • 暴力处理上下的质因数消元

范德蒙德卷积

\(\sum_{i=0}^k{n \choose i}{m \choose k-i}= {n + m\choose k}\)

理解:从两堆共选 k 可表示为枚举第一堆选多少的方案数 * 第二堆的方案数

\(\sum_{i=1}^n{n \choose i}{n \choose i-1} = { 2n\choose n-1}\)

可以从第一个式子推来,将 \({n \choose i}\) 化为 \(n \choose n-i\) 即可

\(\sum_{i=0}^n{n\choose i}^2={2n \choose n}\)

\(\sum_{i=0}^m{n \choose i}{m \choose i}={n+m \choose m}\)

隔板法(重点)

问题形式一:将 n 个相同苹果放入 m 个不同的箱子里的方案数(可以限制是否为空)

问题形式二:解方程 \(x_1+x_2+ \cdots+x_m = n\) ,正整数解或自然数方案数

将 n 个苹果排成一列,发现有 n - 1 的空隙,在其中 m 个空隙中插上隔板,两个隔板中的苹果扔到同一个箱子里即可,如果可以为零就加上 m 个虚拟苹果

  • 解方程变形:\(x_1+x_2+ \cdots+x_m \le n\) 再加入一个变量即可
  • 个数限制:容斥枚举那些超出限制即可

可重组合

问题:有 m 种球每种球都是足够多的,有 n 个相同盒子,现在要把盒子塞满(一种球可以用多次),多少种方案?

\[H(n,m)={{m+n-1}\choose n} \]

理解一:隔板法

枚举每种球放入几个盒子,隔板法解决即可

理解二:构造

将 n 个盒子的球按编号排序,第 i 个变为 \(a_i+i\),这样可以保证每个盒子里的球编号互不相同了,发现任意从 \([2, n + m]\) 选出来 n 个数都可以还原到原来的数列

拓展一:盒子有编号(直接乘上 fac[n])

拓展二:盒子可以为空 (隔板法的解方程变形)

扩展三:球有个数限制,同隔板法

不相邻组合

问题:有 n 个球,m 个盒子,选出的球不能相邻(即i 和 i + 1 不可同时选择),有多少种组合方式?

\[H(n,m)={n-m+1 \choose n} \]

理解:构造

同可重集合将[1, n] 缩小到 [0, n-m],易证

格路模型

从坐标原点走到 \((n,m)\) 的方案数是

\[{{n+m}\choose n} \]

没啥好说的。。。

艾提艾斯提模型

以前从未听说QAQ

\[{{n+m+1}\choose m}=\sum_{i=0}^m {n+m-i\choose m-i} \]

从坐标 \((n+1,m)\) 开始,枚举第一步向下走多少步,且从左边走过来

画个图会很好理解

备胎模型

奇怪的名称增加了

\[{n \choose l}{l \choose r}={n \choose r}{n-r\choose l-r},l\in[r,n] \]

从 n 中选 l 个再从 l 中选 r 个等价于直接从 n 中选 r 个,再从剩下的选 \(l - r\)

直接走定义式也可证明

拓展形式

\[\prod_{i=1}^k{a_{i-1}\choose a_i}={a_0\choose a_k}\prod_{i=1}^{k-1}{a_0-a_i\choose a_i- a_{i+1}} \]

奇偶模型

\[\sum_{i为奇数}{n\choose i}=\sum_{i为偶数}{n\choose i}=2^{n-1} \]

二项式定理令 \(x = 1, y = -1\) 即可证明

组合解释

对于 x 元素来说,有一半的集合包含它,一半的集合不包含,包含它的奇子集将它去掉变为不包含它的偶子集,不包含它的奇子集加上它变为包含它的偶子集,得证!

两个恒等式

上定下动

\[\sum_{i=1}^n {n\choose i}=2^n \]

下定上动

\[\sum_{i=r}^n{i \choose r}={n+1\choose r+1} \]

理解:枚举选出来的最大编号

二项式反演

我的另一篇文章

莫比乌斯反演

我的另一篇文章

斯特林数和简单生成函数

我的另一篇文章

高等数学 OI 基础

我的另一篇文章

多项式全家桶

我的另一篇文章

min-max容斥

在计算期望时常用

巨佬的一篇blog

斯特林反演

巨佬的一篇blog

群论

巨佬的一篇blog

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部