鲜花:距离上一次整理数学知识还是在 2023 年,不知不觉已经过去了两年,真快啊…… 那个时候我还很菜,不过现在的我并没有成为之前想成为的样子。
组合数和基本组合数公式
-
(nm)=n!(n−m)!m!
更广义的定义为 nm‾m!m}}{m!},可在 n 为实数,m 为非负整数时定义。
-
(nm)=(nn−m)
组合意义:n 个选 m 个相当于从 n 个里面选择 m 个不选。
-
(nm)=(n−1m)+(n−1m−1)(加法公式)
组合意义:相当于枚举第一个选还是不选。
-
∑ni=0(ni)=2n
组合意义:n 个中任意选相当于选择不同数量的方案数之和。
-
(nm)=nm(n−1m−1) (吸收公式)
常用于 m(nm) 和 n(n−1m−1) 相互转换,使得前面那个系数变为定值提到外面去。
组合意义:从 n 个里选 m 个再选 1 个特殊的等价于先从 n 个里选出特殊的再从剩下 n−1 里选 m−1 个。是公式 6 的特殊形式。
-
(nm)(mk)=(nk)(n−km−k)
组合意义:从 n 个选 m 再选 k,从 n 个选 k 再从 n−k 个选 m−k,显然二者等价。
-
∑ni=0(im)=(n+1m+1) (上指标求和)
组合意义:有 n+1 个位置,从中选取 m+1 个,按照最后一个被选的位置统计。当最后一个位置为 i+1 时,选出 m+1 个位置的组合数就等价于从前 i 个位置选出 m 个位置的组合数之和。
-
∑mi=0(n+ii)=(n+m+1n)(平行求和)
代数解释:=∑mi=0(n+in),直接套上指标求和公式。
组合意义:我不知道。
-
∑mi=0(ni)(−1)i=(−1)k(n−1k) (下指标差求和)
-
∑ki=0(ni)(mk−i)=(n+mk)(范德蒙德卷积)
组合意义:从 n+m 种选 k 个相当于从前 n 个选 i 个,后 m 个选 k−i。
-
∑ni=0xiyn−i(ni)=(x+y)n(二项式定理)
组合意义:n 个球染色,每个球都可以染成 x 种暖色之一和 y 种冷色之一。
更多组合意义
-
插板法
若 m 个变量赋值为正整数和为 n 方案数为 (n−1m−1)。
组合意义:n 个小石子用 m−1 个板分成 m 个部分。
如果赋值成非负整数的方案数量为 (n+m−1m−1)。
组合意义:将所有数字 +1 最后 −1 即满足调前
-
捆绑法
如果集合 S 必须抱团取暖,把他们当成一个整体,最后乘上集合内部排列的方案数即 ∣S∣!。
入门题
[ARC144D] AND OR Equation
你并不用在意这个题讲的什么,我们来推式子,尝试化简:
n∑i=0k∑s=i(ni)2i(s−1i−1)(k−s+1)
要求 O(n) 计算。
=n∑i=0(ni)2ik∑s=i((k+1)(s−1i−1)−i(si))=n∑i=0(ni)2i((k+1)(ki)−i(k+1i+1))=n∑i=0(ni)2i((i+1)(k+1i+1)−i(k+1i+1))=n∑i=0(ni)2i(k+1i+1)
(1) 简单移项,(2) 上指标求和化简,(3) 吸收公式化简,(4) 简单整理。