经典组合问题

最后更新于：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];
}