经典组合问题
最后更新于:2022年6月25日 下午
在此记录一些经典的组合问题,方便日后查阅。
卡特兰数,斯特林数,放球问题,这篇神作,包含了几乎所有能遇到的经典组合问题
卡特兰(Catalan )数
\(n\) 个 0 和 \(n\) 个 1 组成的序列中始终要保持 任意前缀中 0 的个数不超过 1 的个数的序列个数为 \(\frac{1}{n+1} {2n \choose n }\)
这个问题跟括号合理性等一系列问题合理性有关。
\(n\) 个 0 和 \(m\) 个 1 组成的序列(\(n \leq m\)) 保持 任意前缀中 0 的个数不超过 1 的个数的序列个数为: \[ {n+m \choose n} - {n+m \choose n-1} \]
把 0 当 \(x\)-轴,1 当 \(y\)-轴,不合理的情况必然经过 \(y = x+1\), 在第一次不合理时,后面的路径就开始与 \(y = x +1\) 对称,最终结束点为 \((n-1, m+1)\)
斯特林(Stirling)数
关于这个问题可以参考 这篇博客
第一类斯特林数:长度为 \(n\) 的排列恰好可以写成 \(m\) 个轮换的排列个数一般简记为 \(\begin{bmatrix} n \\ m\end{bmatrix}\)。递推关系式:
\[ \begin{bmatrix} n \\ m\end{bmatrix} = \begin{bmatrix} n - 1 \\ m - 1 \end{bmatrix} + (n - 1) \begin{bmatrix} n - 1 \\ m\end{bmatrix} \]
其它递推公式可以看我在知乎上的回答
第二类斯特林数: 将 \(n\) 个不同的元素拆分成 \(m\) 个非空集合的方案数 \(S(n,m)\)。一般简记为\(\begin{Bmatrix} n \\ m\end{Bmatrix}\) 显然有递推关系式: \[ S(n,m) = S(n-1,m-1)+mS(n-1,m) \] 又我们知道: \[ m^n = \sum _{i=0} ^ m S(n,i) \times i! \times {m \choose i} \] 将 \(n\) 个任意的放在 \(m\) 个不同盒子中。右边的枚举非空盒子数量 \(i\),\(i\) 个盒子因为是不同的所以要乘 \(i!\) (不用担心算多了,因为一旦分配好了,盒子本身即使无区别,放了东西就有区别了) 从我的这篇博文 直接可知 (把 \(n\) 看作常数): \[ S(n,m) m! = \sum_{i=0}^m (-1)^{m-i} {m \choose i} i^n \]
改写成卷积形式也就是:
\[ S(n,m) = \sum_{i=0}^m \frac{(-1)^{i}}{i!} \frac{(m - i)^n}{(m - i)!} \]
补充:知乎上 Hongzy 写了一篇 斯特林数入门 的文章,写的甚好。包含了两类 Stirling 的关系以及上升幂和下降幂的关系。
正整数分拆数
将正整数 \(n\) 拆分成 \(m\) 个非负整数之和的方案数 \(f(n,m)\): \[ f(n,m) = \left\{ \begin{array}{lr} 1 & n=m=1 \\ f(n,n) & n<m \\ 1+f(n,n-1) & n=m \\ f(n,m-1)+f(n-m,m) & n>m>1 \end{array} \right. \]
完整分拆可以用生成函数取 ln 再取 exp \(O(n \log n)\) 复杂度解决
正整数分拆成乘积数
记 \(fcnt(n,m)\) 表示 \(n\) 的乘法分解都不超过 \(m\) 的数 \[ fcnt(n,m) = \sum_{d|n} [d<=m] fcnt(\frac{n}{d},d) \]
- 打表时间复杂度 \(O(n^{\frac{5}{2}})\),空间复杂度 \(O(n^2)\) 不推荐!
1 |
|
- 递归(推荐复杂度不好分析)
1 |
|
\(n\) 个球放在 \(m\) 个盒子中
球有相同和不同两种情况,盒子也是,还有盒子能空和不能空,一共八种情况:
球同,盒同,非空
正整数拆分数之和 \(f(n,m) - f(n,m-1)\)
球同,盒同,能空
正整数拆分数 \(f(n,m)\)
球同,盒异,非空
等价于 \(x_1 + \cdots + x_m = n\) 的正整数解,插空法知道 \(n-1 \choose m-1\)
球同,盒异,能空
同上,\(n+m-1 \choose m-1\)
球异,盒同,非空
第二类斯特林数: \(S(n,m)\)
球异,盒同,能空
同上, \(\sum_{i=1} ^m S(n,i)\)
球异,盒异,非空:\(m!S(n,m)\)
球异,盒异,能空:\(m^n\)
有限制的线性方程组的解
\(x_1+ \cdots +x_n = m, c_i < x_i \leq d_i\) 的正整数解的个数?(通过平移不妨设 \(c_i = 0\))
\(m\) 较小时,动态规划直接做复杂度 \(O(m^2 n)\)
1 |
|
\(n\) 较小时,直接暴力做
首先化简为求解:\(x_1+ \cdots +x_n = m, 0 \leq x_i \leq a_i\) 的正整数解的个数记作 f(n)
我们先考虑 \(n = 2\) 的情形,并且不妨设 \(a_1 < a_2\),我们分情况讨论可得 \[ f(2) = \left\{ \begin{array}{ll} 1 + m & m \leq a_1 \\ 1 + a_1 & a_1 < m < a_2 \\ \max(1 + a_1 + a_2 - m, 0) & a_2 \leq m \end{array} \right. \] 记 \(g(m, x, y) = \max(0, 1 + \min(m, x) + \min(0, y - m)\) (定义域:\(x \leq y\)) 则显然此时有(不妨设 \(a_{2i + 1} < a_{2i}\)):
\(f(1) = 1\), \(f(2) = g(m, a_1, a_2)\), \(f(3) = \sum_{x_3 = 0}^{\min(k, a_3)} g(k - x_3, a_1, a_2)\), \(f(4) = \sum_{x = 0}^m g(x, a_1, a_2) \cdot g(m - x, a_3, a_4)\),可以一致这样搞下去(\(n = 5, 6\) 可以依然可以用此方法),但是此时还不如直接用动态规划做法来做。
\(d_i - c_i\) 为一个常数时,用包容排斥原理
不妨设 \(c_i = 0, d_i = k\)
\[ {m-1 \choose n-1} - {n \choose 1} {m-k-1 \choose n-1} + \cdots (-1)^n {n \choose n} {m-nk-1 \choose n-1} = \sum_{i=0} ^ n (-1)^i {n \choose i} {m-ik-1 \choose n-1} \]
求和式
\[ \sum_{\sum c_i x_i = m} \frac{(\sum x_i)!}{\prod (x_i !)} \]
其中 \(m, c_i\) 是正整数,\(x_i\) 是待定非负整数。考虑其组合意义如下:
- 首先特殊情况 \(c_i = 1\),此时可以理解为有 m 个洞,每个洞都要选择 n 个物体(每个物体占一个洞)中的一种的总方案数: \(n^m\)
- 一般情况,m 个洞,每个洞有且仅有一个物体覆盖(第 i 个物体的长度为 \(c_i\))的总方案数,直接 DP 即可(求和式表示洞中有 \(x_i\) 个 \(i\) 物体)
复杂度:\(O(nm)\)
1 |
|