经典组合问题

最后更新于: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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N = 10004;
int fcnt[N][N]; //
void initFcnt(){
for(int i=1;i<N;++i) fcnt[1][i] = 1;
for(int i=2;i<N;++i){
int sn = sqrt(i+0.2);
for(int d = 1;d<=sn;++d){
if(i%d) continue;
for(int j = N-1;j>=d;--j) fcnt[i][j]+=fcnt[i/d][d];
for(int j=N-1;j>=i/d;--j) fcnt[i][j]+=fcnt[d][i/d];
}
if(sn*sn == i){
for(int j = N-1;j>=sn;--j) fcnt[i][j]-=fcnt[sn][sn];
}
}
}
int getFcnt(int n){
if(fcnt[1][1] != 1) initFcnt();
return fcnt[n][n];
}

int main(){
int n;
while(cin>>n){
time_t now = time(0);
cout<<getFcnt(n)<<endl;
cout<<"Time used: "<<difftime(time(0),now)<<endl;
}
return 0;
}
  • 递归(推荐复杂度不好分析)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int fcnt(int n,int m){
if(n == 1) return 1;
int sn = sqrt(n+0.2),ans = 0;
for(int d = 1;d<=sn;++d){
if(n%d) continue;
if(d<=m && d>1) ans += fcnt(n/d,d);
if(n/d<=m) ans+= fcnt(d,n/d);
}
if(sn*sn == n && sn<=m) ans-=fcnt(sn,sn);
return ans;
}

int main(){
int n;
while(cin>>n){ // n=98765432109876 = 9.8*10^13 用时 42s, N 大点,耗时会小点
time_t now = time(0);
cout<<fcnt(n,n)<<endl;
cout<<"Time used: "<<difftime(time(0),now)<<endl;
}
return 0;
}

\(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
2
3
for(int x = d[i]; x > c[i]; --x){
dp[i][j] += dp[i-1][j-x];
}

\(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
2
3
4
5
6
7
8
9
10
11
12
// \sum_{\sum c_i x_i = m} \frac{(\sum x_i)!}{\prod (x_i !)}
int sumNum(std::vector<int> c, int m, int M) {
std::vector<int> dp(m + 1);
dp[0] = 1;
for (int i = 1; i <= m; ++i) {
for (auto x : c) if (x <= i) {
dp[i] += dp[i - x];
if (dp[i] >= M) dp[i] -= M;
}
}
return dp[m];
}