在此记录一些经典的组合问题，方便日后查阅。

卡特兰数，斯特林数，放球问题，这篇神作，包含了几乎所有能遇到的经典组合问题

卡特兰（Catalan ）数

$n$ 个 0 和 $n$ 个 1 组成的序列中始终要保持 任意前缀中 0 的个数不超过 1 的个数的序列个数为 $\frac{1}{n+1} {2n \choose n }$

这个问题跟括号合理性等一系列问题合理性有关。

$n$ 个 0 和 $m$ 个 1 组成的序列（$n \leq m$) 保持 任意前缀中 0 的个数不超过 1 的个数的序列个数为：

把 0 当 $x$-轴，1 当 $y$-轴，不合理的情况必然经过 $y = x+1$, 在第一次不合理时，后面的路径就开始与 $y = x +1$ 对称，最终结束点为 $(n-1, m+1)$

斯特林（Stirling）数

关于这个问题可以参考 这篇博客

第一类斯特林数：长度为 $n$ 的排列恰好可以写成 $m$ 个轮换的排列个数一般简记为 $\begin{bmatrix} n \\ m\end{bmatrix}$。递推关系式：

其它递推公式可以看我在知乎上的回答

第二类斯特林数： 将 $n$ 个不同的元素拆分成 $m$ 个非空集合的方案数 $S(n,m)$。一般简记为$\begin{Bmatrix} n \\ m\end{Bmatrix}$ 显然有递推关系式：

又我们知道：

将 $n$ 个任意的放在 $m$ 个不同盒子中。右边的枚举非空盒子数量 $i$，$i$ 个盒子因为是不同的所以要乘 $i!$ （不用担心算多了，因为一旦分配好了，盒子本身即使无区别，放了东西就有区别了）
从我的这篇博文 直接可知 (把 $n$ 看作常数）：

改写成卷积形式也就是：

补充：知乎上 Hongzy 写了一篇 斯特林数入门 的文章，写的甚好。包含了两类 Stirling 的关系以及上升幂和下降幂的关系。

正整数分拆数

将正整数 $n$ 拆分成 $m$ 个非负整数之和的方案数 $f(n,m)$：

完整分拆可以用生成函数取 ln 再取 exp $O(n \log n)$ 复杂度解决

正整数分拆成乘积数

记 $fcnt(n,m)$ 表示 $n$ 的乘法分解都不超过 $m$ 的数

  • 打表时间复杂度 $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$，我们分情况讨论可得

记 $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, 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];
}