离散数学与证明方法 · 小纸条

核心机制：排列、组合与多重集的核心是：排列关注次序，组合忽略次序，多重集需除去相同元素置换；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为排列、组合与多重集手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：重复元素和重复选择是两个不同模型。

核心机制：加法、乘法与补集原理的核心是：互斥选择用加法，连续独立阶段用乘法，补集把难事件转成总数减容易事件；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为加法、乘法与补集原理手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：阶段选择若依赖仍可乘条件数，但不能把变化因子当常数。

核心机制：鸽巢原理与极值保证的核心是：把对象映到盒子，平均负载向上取整给必然碰撞或下界；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为鸽巢原理与极值保证手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：必须明确鸽子、巢和映射；结论只给存在性不指定对象。

核心机制：二项式定理与组合恒等式的核心是：二项式系数既来自代数展开也来自子集计数，可用双计数证明恒等式；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为二项式定理与组合恒等式手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：代数验算不解释双计数对象为何相同。

核心机制：普通生成函数的核心是：序列编码为形式幂级数，乘法对应卷积，代数操作提取计数公式；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为普通生成函数手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：形式幂级数推导不必先讨论数值收敛，但系数操作要合法。

核心机制：容斥原理的核心是：交替加减非空交集修正重复计数，事件多时用子集索引统一表达；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为容斥原理手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：只减两两交会漏回三重交，符号取决于交集阶数。

核心机制：指数生成函数选讲的核心是：带标签对象用n!缩放的EGF，自然表达集合式组合构造；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为指数生成函数选讲手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：OGF与EGF不能只换符号，乘法对应的组合结构不同。