←返回主页

组合数

先来说一说组合数的概念

$C^n_m \rightarrow$ 从 $m$ 个物品中选 $n$ 个物品，共有多少种方案

二项式系数

$(a + b)^1 = C^0_1a + C^1_1b$

$(a + b)^2 = C^0_2a^2 + C^1_2b + C^2_2b^2$

$(a + b)^3 = C^0_3a^3 + C^1_3a^2b + C^2_3ab^2 + C^3_3b^3$

$\cdots\cdots$

$\begin{aligned}(a + b)^n &= C^0_na^n + C^1_na^{n - 1}b + \cdots + C^{n - 1}_nab^{n - 1} + C^n_nb^n\\&=\sum_{i = 0}^nC^i_nx^{n - i}b^i\end{aligned}$

感性理解：

杨辉三角 & 递推求组合数

将其列成一个表:

于是我们可以递推求出 $C^n_m$

$C^n_m = C^{n - 1}_{m - 1} + C^{n}_{m-1}$

*这里要注意边界情况（

时间复杂度: $O(n^2)$

代码

xxxxxxxxxx
8
1
for i = 0 to n :
2
    C[i][0] = 1;
3
for i = 1 to n :
4
    C[i][i] = 1;
5
​
6
for i = 1 to n :
7
    for j = 1 to i :
8
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);

下面是一些十分有趣的性质

一些性质

$\sum_{i = 0}^nC_n^i=2^n$

这个直观来看就是杨辉三角第 $n$ 行的和

令 $f(n) = \sum_{i = 0}^nC_n^i$

$\begin{aligned}f(n)&=\sum_{i = 0}^nC_n^i\\&=\sum_{i =0}^n(C_{n-1}^{i-1}+C_{n-1}^{i})\end{aligned}$

注意到每个 $C_{n-1}$ 都被计算了两次

$\begin{aligned}f(n)&=\sum_{i =0}^n(C_{n-1}^{i-1}+C_{n-1}^{i})\\&=2\times \sum_{i = 0}^nC_{n-1}^i\\&=2 \times f (n-1) \end{aligned}$

$f(0) = 1 \Longrightarrow f(n) = 2^n$

$\sum_{i = 0}^kC^i_{n + i - 1} = C^{k}_{n + k}$

直接根据杨辉三角感性理解 /cy

快速求组合数

$C^k_n={n\times (n - 1) \times \cdots (n - k + 1) \over k\times (k-1)\times \cdots \times 1} = \prod_{i=1}^k{n-i+1\over i}$

可以保证每一步运算都是整数

可以单次 $O(n)$ 计算组合数模任意数

记录组合数因子出现次数 $\text{cnt}(x)$, 若知道每个数x的最小质因子 $\text{mnp}(x)$

从后往前扫 对于每个合数 将 $\text{cnt}({x\over\text{mnp}(x)})+=\text{cnt}(x),\text{ } \text{cnt}(\text{mnp}(x))+=\text{cnt}(x)$

最后可以得到质因数分解形式 由于质数个数$O({n \over \ln n})$ 最终复杂度 $O(n)$

$C_n^k={n!\over k!\times (n-k)!}$

对于质数 可以 $O(n)$ 预处理 $O(1)$ 求值

如果n太大了怎么办？

可以直接 Lucas定理 (注意模数必须是质数)

如果模数也很大怎么办？

比如 $n,m \le 10^9 ,P = 10^9+7$

分块打表

为了快速获得 $x!$

设置 $B$ 打表 $B!$ , $(2B)!$ , $(3B)!$ …

每次查询一个 $x!$ 只需要用表中最接近的值 $O(B)$

计算表的长度 $O({P\over B})$

如果模数不是定值怎么办？

不会（

例题 $1$

一个正 $n$ 边形 将其所有对角线连起来 一共有多少个交点

保证 $n$ 是奇数 不存在三条对角线共点

对于任意的四个点,可以确定两条对角线,有一个交点

所有答案 $C_n^4$

例题 $2$

给定 $a$, $b$ 两个数组, 求

$\sum_{i = 1}^n\sum_{j = i + 1}^nC_{a_i+a_j+b_i+b_j}^{a_i+a_j}$

$a_i,b_i\le 2000;n\le 2\times 10^5$

考虑 $C_{n+m}^n$的组合意义

$C_{n+m}^n \rightarrow$ 从 $(0,0)$ 走到 $(n,m)$ 的方案数

考虑 $C_{a_i+b_i+a_j+b_j}^{a_i+b_i}$ 的组合意义

$C_{a_i+b_i+a_j+b_j}^{a_i+b_i} \rightarrow$从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$ 的方案数

从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数

考虑计算任意 $(-a_i,-b_i)$ 到任意 $(a_i,b_i)$ 的方案数

减去重复计算的就好了

用 dp 可以做到 $O(\max(a_i,b_i)^2)$

例题 $3$

给你一棵 $n$ 个节点的有根树。你要给每个节点分配一个 $1\to n$ 的数字，使得每个节点分配的数字不同，并且每个节点分配的数字都是它子树内最小的。求方案数

考虑树形dp

$dp(x)$ 表示 $x$ 这个子树分配 $1\to sz(x)$ 的方案数

考虑状态转移

$dp(x)=C_{sz(x)-1}^{sz(u_1), sz(u_2),\cdots, sz(u_r)}\prod dp(u_i)$

进一步推导:

$\text{ans}=n!\prod{1\over sz(i)}$

基础组合问题

加法原理

要么 $A$ 要么 $B$ (A和B不相交)

一个整数可以属于 $[1,3]$ 或 $[4,6]$ 那么共有 $6$ 种可能

乘法原理

$A\times B$ $A$ 和 $B$ 中各选一个

第一个整数属于 $[1,3]$ 第二个整数属于 $[1,2]$ 共有 $6$ 种可能

栗子:

求有 $2n$ 个点的二分图最多有多少条边?

显然一边 $n$ 个点, 另一边 $n$ 个点

左边的每一个点可以于右面的 $n$ 个点相连

故 $\text{ans}=n\times n = n^2$

栗子 2:

$n$ 个未知数，给定每个数的上限 $a_i$ ，问你有多少种方法使得这些未知数都是正整数且互不相同。输出方案数模$10^9+7$

考虑将 $a_i$ 从小到大排序 依次确定未知数的值

$\text{ans} = a_1 \times (a_2-1) \times (a_3-2) \times \cdots \times (a_n - (n - 1))$

一个很有用的计数原则

一个由计数对象组成的集合 $S$ ，要计算它的大小 $|S|$，考虑如果我们找到一个集合 $T$ ，使得 $S$ 的元素与 $T$ 的元素一一对应，那么 $|S|=|T|$

一个推广

如果 $S$ 的每个元素对应到 $a$ 个 $T$ 中的元素， $T$ 的每个元素对应到 $b$ 个 $S$ 中的元素，那么有

$a|S|=b|T| ; |S|=|T|\times b/a$

接下来我们就要讲讲最重要的 $\text{Twelvefold way}$

Twelvefold way

$n$ 个有标号/无标号的球分给 $m$ 个有标号/无标号的盒子

盒子有三种限制： A. 无限制 B. 每个盒子至少有一个球 C. 每个盒子至多有一个球

共 $12$ 种问题

为了方便 将有标号记为 $\text{L(labelled)}$ 无标号记为 $\text{U(unlabelled)}$

那么一个问题可以用缩写代替 如 UUA

(LLA) $n$ 个有标号的球分给 $m$ 个有标号的盒子

$m^n.$

(ULA) $n$ 个无标号的球分给 $m$ 个有标号的盒子

等同于方程的整数解个数

$C_{n+m-1}^{m-1}$

(ULB) $n$ 个无标号的球划分给 $m$ 个有标号的盒子 不能有空盒

等同于方程的整数解个数

$C_{n-1}^{m-1}$

(LLC) $n$ 个有标号的球分给 $m$ 个有标号的盒子 每个盒子至多放一个球

$m!\over (m-n)!$

(ULC) $n$ 个无标号的球分给 $m$ 个有标号的盒子 每个盒子至多放一个球

$C_m^n$

(LUC) $n$ 个有标号的球分给 $m$ 个无标号的盒子 每个盒子至多放一个球

$[n\le m]$

(UUC) $n$ 个无标号的球分给 $m$ 个无标号的盒子 每个盒子至多放一个球

$[n\le m]$

中间插播一下容斥 (

$|A \cup B| = |A| + |B| - |A \cap B|$

$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

$\left|\bigcup_{i=1}^nA_i\right|=\sum_{i=1}^n|A_i|-\sum_{1\le i \le j\le n}|A_i\cap A_j|+\cdots+\sum_{1\le i\le j\le k}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{n-1}|A_1\cap \cdots \cap A_n|$

(LLB) $n$ 个有标号的球划分给 $m$ 个有标号的盒子 不能有空盒 使用容斥原理：

$\sum_{i = 0}^m(-1)^i n ^{m-i}C_m^i$

(LUB) $n$ 个有标号的球划分给 $m$ 个无标号的盒子 不能有空盒

(LLB) 的答案再除以m!

(LUB) 即 $n$ 个有标号的球划分给 $m$ 个无标号的盒子 不能有空盒

第二类斯特林数.

$S(n,k)={1\over k!}\sum_{j=0}^k(-1)^{k-j}C_k^j j^n$

(LLB) 即 $n$ 个有标号的球划分给 $m$ 个有标号的盒子 不能有空盒

$S(n,k)\times k!$

(LUA) $n$ 个有标号的球划分给 $m$ 个无标号的盒子

枚举有几个盒子被分配了

$\text{ans} = S(n,0)+S(n,1)+\cdots+S(n,m)$

插播 $\times 2$ : 划分数

$p(n,k)$ 划分数

$n=x_1+x_2+\cdots+x_k$

将 $n$ 划分为 $k$ 个正整数的方案数 方案与 $x$ 的顺序无关

xxxxxxxxxx
5
1
4 = 1 + 1 + 1 + 1
2
  = 2 + 1 + 1
3
  = 2 + 2
4
  = 3 + 1
5
  = 4

递推式

考虑最小的数是否为 $1$

$p(n,k)=p(n-k,k)+p(n-1,k-1)$

那么剩下的 UUA 和 UUB 就很好解决了

(UUB) $n$ 个无标号的球划分给 $m$ 个无标号的盒子 每个盒子至少有一个球

$p(n,m)$

(UUA) $n$ 个无标号的球划分给 $m$ 个无标号的盒子

枚举有几个盒子被分配了

$p(n,1)+p(n,2)+\cdots+p(n,m)$

$p(n+m,m)$

ABC三种限制的意义

A）无限制 (labelling)

将每个元素标号 放进第i个盒子就标为i号（当盒子有标号时 无标号时和B类似）

B）每个盒子至少有一个球 (grouping)

将所有元素分成m组 放进同一个盒子的是同一组

C）每个盒子至多有一个球 (selection)

为每个球选一个盒子