组合计数基础知识点简要整理
排列数
定义
(P_n^m) 为 (n) 个不同元素选出 (m) 个排成一列，可以得到不同的排列的数量：
[P_n^m = dfrac{n!}{(n-m)!} = prodlimits_{i=n-m+1}^n i
]
组合数
定义
(C_n^m) 表示从 (n) 个不同元素选出 (m) 个，组成不同的集合的数量（也可记作 ({nchoose m})）：
[C_n^m = dfrac{n!}{m!(n-m)!} = dfrac{prod_{i=n-m+1}^n i}{prod_{i=1}^m i}
]
性质
- (C_{n+m}^n = C_{n+m}^m)
- (C_n^m = C_{n-1}^m+C_{n-1}^{m-1})
- (sum_{i=0}^n C_n^i = 2^n)
- (C_n^k = C_n^{k-1} imes frac{n-k+1}{n})
求法
- 使用性质 (C_n^m = C_{n-1}^m+C_{n-1}^{m-1}) 递推，计算出 (n) 范围以内的所有组合数。复杂度 (O(n^2))。
- 递推出 (0 sim n) 的阶乘及其逆元，那么 (C_n^m = n! imes (m!)^{-1} imes [(n-m)!]^{-1})。复杂度 (O(n))。
- 使用 (C_n^k = C_n^{k-1} imes frac{n-k+1}{n}) 递推出 (C_n^0 sim C_n^n) 的值。复杂度 (O(n))。
- Lucas 定理。见下。
经典问题
多重集排列数
(n_1) 个 (a_1)，(n_2) 个 (a_2)，……，(n_k) 个 (a_k) 组成的多重集可得的本质不同的排列数为：
[dfrac{(sum_{i=1}^k n_i)!}{prod_{i=1}^k (n_i!)}
]
多重集组合数
(n_1) 个 (a_1)，(n_2) 个 (a_2)，……，(n_k) 个 (a_k) 组成的多重集选出 (R(le minlimits_{1le ile n} n_i)) 个元素，得到的本质不同的多重集数为：
[{{k-1}choose{k+R-1}}
]
二项式定理
((a+b)^n) 展开可得：
[(a+b)^n = sumlimits_{k=0}^n C_n^k a^k b^{n-k}
]
Lucas 定理
若 (p) 为质数，有：
[{nchoose m} equiv {{nmod p}choose {mmod p}} imes {{leftlfloor{n/p}
ight
floor} choose {leftlfloor{m/p}
ight
floor}} pmod p
]
在 (p) 不太大时，可以在 (O(p log_p n)) 的时间 求出组合数。
Catalan 数
定义
定义第 (n) 个 catalan 数为 (h(n))，定义式：
[h(n) = dfrac{C_{2n}^n}{n+1}
]
性质
-
递推式 1：
[h(n) = egin{cases}
1 & nle 1 \
sumlimits_{i=0}^{n-1} h(i) imes h(n-i - 1) & ext{otherwise.}
end{cases}
]
-
递推式 2：(h(n) = frac{4n-2}{n+1} imes h(n-1))
-
(h(n) = C_{2n}^n - C_{2n}^{n+1})
经典问题
容斥原理
定义
集合 (S_1, S_2, cdots ,S_n) 的并集为：
[left|{Largeoperatorname{cup}limits_{i=1}^n} S_i
ight| = sumlimits_{1le ile n} |S_i| - sumlimits_{1le ile jle n} |S_icap S_j| + sumlimits_{1le ile jle kle n} |S_icap S_jcap S_k| - cdots + (-1)^{n+1}|operatorname{cap}limits_{i=1}^n S_i|
]
经典问题
多重集组合数（拓展）
现在讨论上述该问题 (R) 无限制的问题。
不考虑 (n_i) 的限制，那么等价于从集合 ({inftycdot a_1, inftycdot a_2, cdots inftycdot a_k}) 中抽取 (R) 个的方案数，答案为 ({k+R-1choose k-1})。
若设 (f_i) 为限定 (n_i+1) 个元素选 (a_i)，剩下个元素任意选的方案数。那么方案数为 ({k+R-n_i-2choose k-1})。
设 (f_{i, j}) 为限定 (n_i +1, n_j+1) 个 (a_i, a_j) 选中，剩下任意选的方案数。那么即为 ({k+R-n_i-n_j-3 choose k-1})。
根据容斥原理，并用总方案数减去非法方案数，有：
[{k+R-1 choose k-1} - sumlimits_{1le ile k} {k+R-n_i-2 choose k-1} + sumlimits_{1le ile jle k} {k+R-n_i-n_j-3choose k-1} - cdots +(-1)^k {k+R-sum_{i=1}^k n_i-(k+1) choose k-1}
]
二项式反演
[g(i) = sumlimits_{j=1}^i {ichoose j} f(j) quad Leftrightarrow quad f(i) = sumlimits_{j=1}^i (-1)^{i-j} {ichoose j} g(j)
]
证明：
将第一个式子代入第二个中：
[f(i)=sumlimits_{j=1}^i (-1)^{i-j} {ichoose j} sumlimits_{k=1}^j {jchoose k} f(k)
]
设 (a(i)) 为 (f(i)) 的系数。那么：
[a(k) = sumlimits_{j=k}^i (-1)^{i-j} {ichoose j}{jchoose k} \
= sumlimits_{j=k}^i (-1)^{i-j} dfrac{i! j!} {j!(i-j)!k!(j-k)!}\
= sumlimits_{j=k}^i (-1)^{i-j} dfrac{i!} {(i-j)!k!(j-k)!}\
= sumlimits_{j=k}^i (-1)^{i-j} dfrac{(i-k)!} {(i-j)!(j-k)!} imes dfrac{i!}{k!(i-k)!}\
= sumlimits_{j=k}^i (-1)^{i-j} {i-kchoose j-k}{ichoose k}
]
对于 (sum_{j=k}^i (-1)^{i-j} {i-kchoose j-k}) 其实可以理解为第 (i-k) 行的组合数错位相减的结果。如果 (i-k=0) 那么这个式子就是 (1)，但否则由于 ({nchoose m} - {nchoose n-m} = 0)，所以两两抵消后结果为 (0)。所以：
[a(k) = [i=k] imes {ichoose k} = [i=k]\
f(i) = sumlimits_{k=1}^i a(k)f(k) = f(i)
]
于是该式得证。
第一类斯特林数
定义
(egin{bmatrix} n \ k end{bmatrix}) 把 (n) 个不同元素分成 (k) 个非空环排列的方案数。
递推式
考虑此时新插入第 (n) 个元素：
- 单独构成一个环：(egin{bmatrix} n-1 \ k-1 end{bmatrix})。
- 插入已有的 (k) 个环中。发现本质不同的位置有 (n-1) 个，那么方案数：((n-1)egin{bmatrix} n-1 \ k end{bmatrix})。
- 于是：
[egin{bmatrix}n \ kend{bmatrix} = egin{bmatrix}n-1\ k-1end{bmatrix} + (n-1)egin{bmatrix}n-1\ kend{bmatrix}
]
生成函数
设第 (n) 行的第一类斯特林数的生成函数为 (f(n) = sum_{i=0}^n egin{bmatrix} n \ i end{bmatrix} x^i)。
根据递推式，有：(f(n+1) = f(n) imes (n+x))。
于是：(f(n) = prodlimits_{i=0}^{n-1} (x+i) = x^{overline{n}})。
性质
根据生成函数，有：
[x^{overline{n}} = sum_{i=0}^{n} egin{bmatrix} n\i end{bmatrix} x^i
]
下降幂形式（(prod_{i-0}^{n-1}(x+i) o prod_{i-0}^{n-1}(x-i))）：
[x^{underline{n}} = sumlimits_{i=0}^n (-1)^{n-i}egin{bmatrix} n\i end{bmatrix} x^i
]
第二类斯特林数
定义
(egin{Bmatrix} n\k end{Bmatrix}) 表示把 (n) 个不同元素分成 (k) 个非空集合的方案数。
两种方案不同当且仅当存在一个集合仅在其中一种方案中出现。
递推式
考虑此时新插入第 (n) 个元素：
- 单独组成一个集合：(egin{Bmatrix} n-1\k-1 end{Bmatrix})。
- 插入原有的 (k) 个集合之一：(kegin{Bmatrix} n-1\k end{Bmatrix})
- 于是：
[egin{Bmatrix} n\k end{Bmatrix} = egin{Bmatrix} n-1\k-1 end{Bmatrix} + kegin{Bmatrix} n-1\k end{Bmatrix}
]
通项公式
我们在原定义上的非空集合加上标号，那么方案数为 (k! imesegin{Bmatrix} n\k end{Bmatrix})。
在上述定义上改为可空集，那么方案数 (k^n)。但是可以写成另一种写法——枚举所有集合中非空的个数：
[k^n = sum_{i=0}^k {k choose i} egin{Bmatrix} n\i end{Bmatrix} imes i!
]
二项式反演后：
[egin{Bmatrix} n\k end{Bmatrix} = dfrac{1}{k!}sum_{i=0}^k (-1)^{k-i} {kchoose i} imes i^n = sumlimits_{i=0}^k dfrac{(-1)^{k-i} imes i^n}{(k-i)! imes i!}
]
性质
与下降幂的关系：
[x^{n} = sumlimits_{i=0}^n egin{Bmatrix} n\i end{Bmatrix} x^{underline{i}}
]
证明：
显然 (n=0) 是成立的。对于其他情况，使用数学归纳法，假设 (n-1) 时该式成立——(x^{underline{n}} = xcdot x^{underline{n-1}} = sumlimits_{i=1}^{n-1} egin{Bmatrix} n-1\i end{Bmatrix} x cdot x^{underline{i}})。
由于 (x^{underline{n}} cdot x = icdot x^{underline{n}} + (x-i)cdot x^{underline{n}} = icdot x^{underline{n}}+x^{underline{n+1}})，那么：
[sumlimits_{i=1}^{n-1} egin{Bmatrix} n-1\i end{Bmatrix} xcdot x^{underline{i}} \
= sumlimits_{i=1}^{n-1}left(egin{Bmatrix} n-1\i end{Bmatrix} icdot x^{underline{i}} + egin{Bmatrix} n-1\i end{Bmatrix}x^{underline{i+1}}
ight)\
=sumlimits_{i=0}^n left(egin{Bmatrix}n - 1\ i - 1 end{Bmatrix} + i egin{Bmatrix}n- 1\ iend{Bmatrix}
ight)x^{underline i} \
= sumlimits_{i=0}^n egin{Bmatrix} n\i end{Bmatrix} x^{underline i}
]
转化为上降幂形式：
[x^n = sumlimits_{i=0}^n(-1)^{n-i} egin{Bmatrix} n\i end{Bmatrix} x^{overline i}
]
斯特林反演
反转公式
[sumlimits_{i=j}^n (-1)^{n-i} egin{bmatrix} n\i end{bmatrix} egin{Bmatrix} i\j end{Bmatrix} = sumlimits_{i=j}^n (-1)^{i-j} egin{Bmatrix} n\i end{Bmatrix} egin{bmatrix} i\j end{bmatrix} = [n=j]
]
证明：
由上文得：
[x^n = sumlimits_{i=0}^n egin{Bmatrix} n\i end{Bmatrix} x^{underline i}, quad x^{underline{n}} = sumlimits_{i=0}^n (-1)^{n-i}egin{bmatrix} n\i end{bmatrix} x^i
]
将第二个代到第一个式子里面：
[x^{underline{n}} =sumlimits_{i=0}^n (-1)^{n-i}egin{bmatrix} n\i end{bmatrix} left(sumlimits_{j=0}^i egin{Bmatrix} i\ j end{Bmatrix}x^{underline{j}}
ight)\
= sumlimits_{j=0}^n x_j left( sumlimits_{i=j}^n (-1)^{n-i} egin{bmatrix} n\i end{bmatrix} egin{Bmatrix} i\j end{Bmatrix}
ight)
]
把最后的式子和 (x^{underline{n}}) 比对一下，发现 (sumlimits_{i=j}^n (-1)^{n-i} egin{bmatrix} n\i end{bmatrix} egin{Bmatrix} i\j end{Bmatrix} = [n=j])。
同样的，将上面的式子从第一个代入第二个，会有：
[x^n = sumlimits_{j=0}^n x^j left(sumlimits_{i=j}^n (-1)^{i-j} egin{Bmatrix} n\j end{Bmatrix} egin{bmatrix} i\j end{bmatrix}
ight) = sumlimits_{j=0}^n x^j[n=j]
]
得到反转公式：
[sumlimits_{i=j}^n (-1)^{n-i} egin{bmatrix} n\i end{bmatrix} egin{Bmatrix} i\j end{Bmatrix} = sumlimits_{i=j}^n (-1)^{i-j} egin{Bmatrix} n\i end{Bmatrix} egin{bmatrix} i\j end{bmatrix} = [n=j]
]
反演公式
[g(n) = sumlimits_{i=0}^n egin{Bmatrix} n\ i end{Bmatrix} f(i) quad Leftrightarrow quad f(n)= sumlimits_{i=0}^n (-1)^{n-i}egin{bmatrix} n\ i end{bmatrix} g(i)
]
证明：
若已知：
[f(n)= sumlimits_{i=0}^n (-1)^{n-i}egin{bmatrix} n\ i end{bmatrix} g(i)
]
那么：
[g(n) = sumlimits_{i=0}^n[i=n] g(i)\
= sumlimits_{i=0}^n sumlimits_{j=i}^n (-1)^{j-i} egin{Bmatrix}n\ jend{Bmatrix} egin{bmatrix}j\ iend{bmatrix} g(i)\
= sumlimits_{j=0}^n egin{Bmatrix}n\ jend{Bmatrix} sumlimits_{i=0}^j (-1)^{j-i} egin{bmatrix}j\ iend{bmatrix} g(i)\
= sumlimits_{j=0}^n egin{Bmatrix} n\ j end{Bmatrix} f(j)
]
于是其中一个得证，另一个反着做即可。
后记